数据结构和算法14 之归并排序

  归并算法的中心是归并两个已经有序的数组。归并两个有序数组A和B，就生成了第三个数组C，数组C包含数组A和B的所有数据项，并且使它们有序的排列在数组C中。首先我们来看看归并的过程，然后看它是如何在排序中使用的。

        假设有两个有序数组，不要求有相同的大小。设数组A有4个数据项，数组B有6个数据项，它们要被归并到数组C中，开始时数组C有10个存储空间，归并过程如下图所示：

        归并排序的思想是把一个数组分成两半，排序每一半。然后用merge方法将数组的两半归并成一个有序的数组。被分的每一半使用递归，再次划分排序，直到得到的子数组只含有一个数据项为止。正如上面所说的，归并排序需要额外的一个和AB两个数组总和相等的空间，如果初始数组几乎沾满了整个存储器，那么归并排序就不能工作了。

        归并排序的思想很简单，下面我们来看看具体实现：

[java]  view plain  copy

 

1. public void mergeSort(int[] source) {  
2.     int[] workSpace = new int[source.length];  
3.     recMergeSort(source,workSpace, 0, source.length-1);  
4. }  
5.   
6. private void recMergeSort(int[] source, int[] workSpace, int lowerBound, int upperBound) {  
7.     if(lowerBound == upperBound) {  
8.         return;  
9.     }  
10.     else {  
11.         int mid = (lowerBound + upperBound) / 2;  
12.         recMergeSort(source, workSpace, lowerBound, mid); //左边排  
13.         recMergeSort(source, workSpace, mid+1, upperBound); //右边排  
14.         merge(source, workSpace, lowerBound, mid+1, upperBound);//归并  
15.     }  
16. }  
17.   
18. private void merge(int[] a, int[] workSpace, int lowPtr, int highPtr, int upperBound) {  
19.     int j = 0;  
20.     int lowerBound = lowPtr;  
21.     int mid = highPtr - 1;  
22.     int n = upperBound - lowerBound + 1;  
23.     while(lowPtr <= mid && highPtr <= upperBound) {  
24.         if(a[lowPtr] < a[highPtr]) {  
25.             workSpace[j++] = a[lowPtr++];  
26.         }  
27.         else {  
28.             workSpace[j++] = a[highPtr++];  
29.         }  
30.     }  
31.     while(lowPtr <= mid) {  
32.         workSpace[j++] = a[lowPtr++];  
33.     }  
34.       
35.     while(highPtr <= upperBound) {  
36.         workSpace[j++] = a[highPtr++];  
37.     }  
38.       
39.     for(j = 0; j < n; j++) {  
40.         a[lowerBound + j] = workSpace[j];  
41.     }  
42. }  

        算法分析：归并排序的运行时间最差、最好和平均都是O(NlogN)，但是它需要额外的存储空间，这在某些内存紧张的机器上会受到限制。归并算法是由分割和归并两部分组成的，对于分各部分，如果我们使用二分查找，时间是O(NlogN)，在最后归并的时候时间是O(N)，所以总时间是O(NlogN)。空间复杂度为O(N)。

        归并排序是稳定的，由于没有发生数据交换，所有当a=b的时候，a一开始如果在b前面，则其每一次合并后仍然在b前面，故该排序算法是稳定的。

        归并排序就写这么多，如有错误之处，欢迎留言指正~

转载：http://blog.csdn.net/eson_15/article/details/51193139