归并排序

浏览数：19 / 时间：2015年06月08日

　　归并排序算法是用分治策略实现对n个元素进行排序的算法。

　　其基本思想是：将待排序的元素分成大小大致相同的两个子集合，分别对2个子集合进行排序，最终将排序好的子集合合并成为所要求的排好序的集合。

递归版本算法(不完全版本)：

1 public static void mergeSort(Comparable a[],int left,int right){
2         if(left<right){//至少有两个元素
3             int i=(left+right)/2;    //取中点
4             mergeSort(a,left,i);
5             mergeSort(a, i+1, right);
6             merge(a,b,left,right);   //合并到数组b
7             copy(a,b,left,right);    //复制回数组a
8         }
9 }

非递归版本实现：

　　可以看出，算法mergeSort的递归过程只是将待排序集合一分为二，直至待排序的集合只剩下一个元素为止。然后不断合并2个排序好的子集合。

　　由此可以想到，我们可以先将数组a中相邻元素两两配对。用合并算法将他们排序，构成n/2组长度为2的排好序的子集合，然后将它们排序成长度为4

的子集合，如此继续下去，直至整个数组排好序。

　　这样一来就可以消除递归了。

 1 public class MergeSort {
 2     
 3     // 非递归版本归并排序
 4     @SuppressWarnings("rawtypes")
 5     public static void mergeSort(Comparable[] a) {
 6         Comparable b[] = new Comparable[a.length];
 7         int s = 1;
 8         while (s < a.length) {
 9             // a,b交替保证了a一直是有序的
10             mergePass(a, b, s);
11             s = s * 2;
12             mergePass(b, a, s);
13             s = s * 2;
14         }
15     }
16 
17     @SuppressWarnings("rawtypes")
18     private static void mergePass(Comparable[] x, Comparable[] y, int s) {
19         // 合并大小为s的相邻子数组
20         int i = 0;
21         while (i + 2 * s <= x.length) {
22             // 合并大小为s的相邻2段子数组，x[i,i+s-1]，x[i+s-1,i+2*s-1]
23             merge(x, y, i, i + s - 1, i + 2 * s - 1);
24             i = i + 2 * s;
25         }
26 
27         if (i + s < x.length) {
28             // 剩下的元素个数大于s小于2s,仍然要合并
29             merge(x, y, i, i + s - 1, i + 2 * s - 1);
30         } else {
31             // i+s>=x.length的时候，此时剩余的元素个数小于s， 当小于s的时候已经是有序的，直接把剩余元素添加到y的末尾
32             for (; i < y.length; i++)
33                 y[i] = x[i];
34         }
35     }
36 
37     @SuppressWarnings({ "rawtypes", "unchecked" })
38     private static void merge(Comparable[] copy, Comparable[] to, int left,
39             int middle, int right) {
40         // 合并copy[left,middle]和to[middle+1,right]到to[left,right]
41         int i = left, j = middle + 1, k = left;
42 
43         while (i <= middle && j <= right) {
44             if (copy[i].compareTo(copy[j]) <= 0) // 由小到大排序
45                 to[k++] = copy[i++];
46             else
47                 to[k++] = copy[j++];
48         }
49 
50         /*
51          * 以下两个循环用于将剩下已经有序的元素添加到to的末尾， 其中一个数组最大的元素n已经在to中，另外一个数组的元素肯定大于等于n，
52          * 因此直接添加就行
53          */
54         while (i <= middle)
55             to[k++] = copy[i++];
56         while (j <= right)
57             to[k++] = copy[j++];
58     }
59 
60     @SuppressWarnings("rawtypes")
61     public static void main(String[] args) {
62         Comparable a[] = { 4, 6, 7, 1, 2, 5, 9, 0 };
63         mergeSort(a);
64         for (int i = 0; i < a.length; i++)
65             System.out.print(" "+a[i]);
66     }
67 
68 }