Java中的排序问题

总结几种排序方法。 冒泡排序，选择排序，插入排序，Quick Sort,Merge Sort（continue..）...

Simple sorting

Bubble Sort

慢，但是简单。 Time complexity: O(N^2)

步骤:

1. 每次只比较两个值。
2. 如果左边的值大，就交换两个值。
3. 移动大的值到右边。

举例:

原数组: [4,7, 2, 5, 3]
Round 1:
  -> [4,7,2,5,3]
  -> [4,2,7,5,3]
  -> [4,2,5,7,3]
  -> [4,2,5,3,7]
Round 2:
  -> [2,4,5,3,7]
  -> [2,4,5,3,7]
  -> [2,4,3,5,7]
Round 3:
  -> [2,4,3,5,7]
  -> [2,3,4,5,7]
Round 4:
  -> [2,3,4,5,7]

Code:

int[ ] data = {4, 7, 2, 5, 3}

Swap Method

// a helper method that swaps two values in an int array
private static void swap(int[] data, int one, int two) {
    int temp = data[one];
    data[one] = data[two];
    data[two] = temp;
}

Bubble Sort:

public static void bubbleSort(int[] data) {
       // move backward from the last index
       for (int out = data.length - 1; out >= 1; out--) {
           // move forward from the beginning
           // bubble up the largest value to the right
           for (int in = 0; in < out; in++) {
               if (data[in] > data[in + 1]) {
                   swap(data, in, in + 1);
               }
           }
       }
   }

Selection Sort

比冒泡排序快但是依旧不够快。 Time complexity: O(N^2) 比冒泡排序少了很多swap的过程，所以稍微快一些。

步骤:

1. 选出最小的值。
2. 移动到最左边。

举例:

原数组: [4,7, 2, 5, 3]
Round1:
  最小的是2：
  [2,7,4,5,3]
Round2:
  最小的是3
  [2,3,4,5,7]
Round3:
  最小的是4
  [2,3,4,5,7]
Round4:
  最小的是5：
  [2,3,4,5,7]

Code:

for (int out = 0; out<data.length; out++) {
  min = out;
  for (int in = out+1; in < data.length; in ++) {
    if (data[in] < min) {
      min = in;
    }
  }
  if (out != min) {
    swap(data, out, min);
  }
}

Insertion Sort:

最直观的排序法。 Time complexity: O(N^2)

步骤:

想象数组中有一个分割线。
1. 左手边的是排好序的。
2. 线的右边的第一个元素需要被插入到左边的相应位置中。

举例:

原数组: [4,7, 2, 5, 3]
-> [4,|7,2,5,3]
-> [4,7,|2,5,3]
-> [2,4,7,|5,3]
-> [2,4,5,7,|3]
-> [2,3,4,5,7]

Code:

public static void insertionSort(int[] data) {
   // start from the 1st index till the last index
  for (int out = 1; out<data.length; out++) {
    int in = out;
    int temp = data[out];
    /*
    * loop to check the sorted section going backward
    * but not necessarily all the way to the 0th
    * On average, look halfway through the sorted section
    */
    while (in>0 && data[in-1]>=temp) {
      data[in] = data[in-1];
      in --;
    }
    if (out != in) {
      data[in] = temp;
    }
  }

}

##Quick Sort## Time complexity: O(NlogN)

步骤: 是一种对冒泡排序的一种改进。通过一趟把数据分成独立的两部分，其中所有的数据都比另一份数据小。然后再继续排序。递归直到整个数据变成更有序序列。

举例

原数组: [4,7, 2, 5, 3]
-> [4,|7,2,5,3]
-> [4,7,|2,5,3]
-> [2,4,7,|5,3]
-> [2,4,5,7,|3]
-> [2,3,4,5,7]

代码

static void quicksort(int n[], int left, int right) {
    int dp;
    if (left < right) {
        dp = partition(n, left, right);
        quicksort(n, left, dp - 1);
        quicksort(n, dp + 1, right);
    }
}

static int partition(int n[], int left, int right) {
    int pivot = n[left];
    while (left < right) {
        while (left < right && n[right] >= pivot)
            right--;
        if (left < right)
            n[left++] = n[right];
        while (left < right && n[left] <= pivot)
            left++;
        if (left < right)
            n[right--] = n[left];
    }
    n[left] = pivot;
    return left;
}

##Merge Sort## Time complexity: O(NlogN)

Code

public  void sort(int[] A) {
  int[] tmp = new int[A.length];
  mergeSort(A, 0, A.length -1 , tmp);
}

public void mergeSort(int[] A, int start, int end, int[] tmp) {
  if (start >= end) return;
  int left = start, right = end;
  int mid = (start+end)/2;
  mergeSort(A, start, mid, tmp);
  mergeSort(A, mid+1, end,tmp);
  merge(A, start, mid, end, tmp);
}

public void merge(int[] A, int start, int mid, int end, int[] tmp) {
  int left = start;
  int right = mid + 1;
  int index = start;
  while(left <= mid && right <= end) {
    if (A[left] < A[right]) {
      tmp[index++] = A[left++];
    } else {
      tmp[index++] = A[right++];
    }
  }
  while(left <= mid) {
    tmp[index++] = A[left++];
  }
  while(right <= end) {
    tmp[index+++] = A[right++];
  }
  for(index = start; index <= end; index++) {
    A[index] = tmp[index];
  }
}