Merge sort

今天学习merge sort

这个排序算法的思想就是，不停的将数组二分，再将两个子数组不停归并。其中有一个操作叫merge如下图所示。左右两边两个部分是有序的，然后思想也很简单有两个指针i和j，i指向lo，j指向mid+1，然后比较两个指针所指的大小，如果小就选出来排到数组中，如果i大于mid了直接将j指针所指内容一直放入数组，反之亦然。

下面是merge操作的java implementation

 1 public class MergeSort{
 2 
 3         private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi){           // 把item复制到aux数组里面
 4                      for(int i = lo;i <= hi,i++) aux[i] = a[i];
 5                      
 6                      int i = lo, j = mid+1;
 7                      for(int k = lo;k <= hi;k++){
 8 
 9                         if(i > mid) a[k] = aux[j++];
10                         else if (j > hi) a[k] = aux[i++];
11                         else if (less(a[i], a[j]))  a[k] = a[i++];
12                         else  a[k] = a[j++];
13 
14 }
15 
16 
17 }
18 
19 }

这段代码应该很好理解

下面是merge sort的完整java implementation

 1 public class MergeSort{
 2            private static void merge(...){// as before}
 3            private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi){
 4 
 5                        if(hi <= lo) return;
 6                        int mid = lo + (hi - lo)/2;
 7                        sort(a, aux, lo, mid);
 8                        sort(a, aux, mid+1, hi);
 9                        merge(a,aux,lo, mid, hi);
10 }
11           public static void sort(Comparable[] a){
12                      Comparable[] aux = new Comparable[a.length];
13                      sort(a, aux, 0, a.length - 1);
14 
15 
16 }
17 
18 }