转载

归并排序

归并排序基本的操作是合并两个已排序的数组，如下面的例子：

A ： {1,2,4,7}

B ： {2,2,5,9}

第一步：

比较 A[0] 和 B[0] ， A[0]<B[0] ，将 A[0] 复制到 C[0] 中，得到

C{0}

第二步：

比较 A[1] 和 B[0] ， A[1]=B[0] ，将 A[1] 复制到 C[0] 中，得到

C{1,2} 。

循环以上步骤，即得到排序后的序列：

C{1,2,2,2,4,5,7,9} 。

这就是归并排序的基本原理，那么我们可以先给出合并两个已经有序的数组的代码：

public void merge(Integer[]a,Integer low,Integer mid,Integer high) {  Integer i = low; /* 这里为什么不能用mid，因为之前在递归时是以mid+1分割的：    [1,2,8,3,4]    low=0 mid=2 high=4    i=0 j=2    [1]    i=1 j=2    [1,2]    i=2 j=2    [1,2,8,3,4]*/  Integer j = mid + 1;  Integer[] b = new Integer[high + 1];  for(int k=low;k<=high;k++) {   b[k] = a[k];  }  print("b",b);  for(int k=low;k<=high;k++) {   //第一个有序子数组已经遍历完   if(i > mid)    a[k] = b[j++];   //第二个有序子数组已经遍历完   else if(j > high)     a[k] = b[i++];   else if(b[i] < b[j])    a[k] = b[i++];   else     a[k] = b[j++];  } }

这段代码实现了合并两个已经有序的数组到一个新数组。只不过在这里我们使用一个数组代替了两个有序数组，如下：

A’[1,2,4,7,2,2,5,9] 是把上面提到的两个有序数组 A 和 B 放在一个数组 A ’中，用 mid=3 来分割。

最后在代码中新建一个数组 B[], 将 A ’中的元素复制到 B 。

再用循环依次将元素排序放回 A 中。

但是现在这段代码只能将两个已经有序的数组，归并后到一个新数组，让这个新数组编程有序的。

如果是一个无序的数组呢？

这里就需要用到一下的思想：

归并排序

我们可以先将一个无序数组 A ，按照 2 位单位，分成诸多长度为 2 的子数组：

如下：

假如有数组 A ： [2 ,1 ,5 ,9 ,0 ,6 ,8 ,7 ,3]

可以分成以下长度为 1 的子数组：

{2} 、 {1} 、 {5} 、 {9} 、 {0} 、 {6} 、 {8} 、 {7} 、 {3}

那么对这 9 个子数组进行归并排序，也即使用上面提到的代码进行排序，那么就可以得到

{1,2} 、 {5,9} 、 {0,6} 、 {7,8} 、 {3}

这样我们就有 5 个有序的子数组了，再讲这五个子数组两两归并，即得到：

{1,2,5,9} 、 {0,6,7,8} 、 {3}

就这样依次归并下去，即得到一个有序的数组 B

{0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9}

在这里，很明显能感觉到一丝递归的意味，那么先直接给出代码：

//递归实现，自顶向下 public void mergeSort(Integer[] a,Integer low,Integer high) {  if(low >= high)   return;  Integer mid = (low + high)/2;  mergeSort(a,low,mid);  mergeSort(a,mid+1,high);  merge(a,low,mid,high); }

相信如果理解了以上所说的递归排序的原理，这段代码应该非常好懂，用递归的好处就是逻辑简单，符合人的直观思维，只需要将一个待排序的数组依次分成 2,4,8... 等若干个数组，直到得到 A.length 个长度为 1 的子数组，依次归并后得到若干个长度为 2 的有序子数组，再进行归并，得到若干个长度为 4 的子数组（当然，有可能最后一个子数组长度不一定刚好为 2 或 4 ，即数组的长度不一定为 2 的倍数）。

这样一直归并下去，即得到有序的数组。

这是使用递归来实现，那么应该还有一种不使用递归的实现，如下：

//非递归，自底向上 public void mergeSortNonRecursion(Integer[] a) {  //第一层循环 表示归并排序子数组的长度 从1 , 2 , 4 ,8 .....  for(int i=1;i<a.length;i *= 2) {   //第二层循环表示每两个自数组之间归并排序，确定起始和终止INDEX   for(int low=0;low<a.length;low += 2*i) {    merge(a, low, low + i- 1, Math.min(low + 2*i - 1, a.length - 1));   }  } }

第一层循环表示归并的次数，

第一次分成 n 个长度为 1 的子数组，进行归并

第二次分成 n/2 个长度为 2 的子数组 ....

结论就是，一个长度为 n 的数组需要归并 logn 次。

第二层循环表示把两个子数组进行归并

效率：归并排序的时间复杂度为 NlogN

完整代码如下：

public class MergeSort extends SortBase {  @Override  public Integer[] sort(Integer[] a) {   // TODO Auto-generated method stub   print("init",a);   //mergeSort(a,0,a.length-1);   mergeSortNonRecursion(a);   print("result",a);   return a;  }  //递归实现，自顶向下  public void mergeSort(Integer[] a,Integer low,Integer high) {   if(low >= high)    return;   Integer mid = (low + high)/2;   mergeSort(a,low,mid);   mergeSort(a,mid+1,high);   merge(a,low,mid,high);  }  public void merge(Integer[]a,Integer low,Integer mid,Integer high) {   Integer i = low;  /* 这里为什么不能用mid，因为之前在递归时是以mid+1分割的：     [1,2,8,3,4]     low=0 mid=2 high=4     i=0 j=2     [1]     i=1 j=2     [1,2]     i=2 j=2     [1,2,8,3,4]*/   Integer j = mid + 1;   Integer[] b = new Integer[high + 1];   for(int k=low;k<=high;k++) {    b[k] = a[k];   }   print("b",b);   for(int k=low;k<=high;k++) {    //第一个有序子数组已经遍历完    if(i > mid)     a[k] = b[j++];    //第二个有序子数组已经遍历完    else if(j > high)      a[k] = b[i++];    else if(b[i] < b[j])     a[k] = b[i++];    else      a[k] = b[j++];   }  }  //非递归，自底向上  public void mergeSortNonRecursion(Integer[] a) {   //第一层循环 表示归并排序子数组的长度 从1 , 2 , 4 ,8 .....   for(int i=1;i<a.length;i *= 2) {    //第二层循环表示每两个自数组之间归并排序，确定起始和终止INDEX    for(int low=0;low<a.length;low += 2*i) {     merge(a, low, low + i- 1, Math.min(low + 2*i - 1, a.length - 1));    }   }  }  public static void main(String[] args) {   Integer[] a = {2,1,5,9,0,6,8,7,3};   (new MergeSort()).sort(a);  } }