合并排序

合并排序：把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

效率：⊙(nlogn)

伪代码：

 1 Mergesort(A[0..n-1])
 2 //递归调用mergesort来对数组A[0..n-1]排序
 3 //输入：一个可排序数组A[0..n-1]
 4 //输出：非降序排列的数组A[0..n-1]
 5 if n>1
 6     copy A[0..[n/2]-1] to B[0..[n/2]-1]
 7     copy A[[n/2]..n-1] to C[0..[n/2]-1]
 8     Mergesort(B[0..[n/2]-1]
 9     Mergesort(C[0..[n/2]-1]
10     Merge(B,C,A)

 1 Merge(B[0..p-1],C[0..q-1],A[0..p+q-1])
 2 //将两个有序数组合并为一个有序数组
 3 //输入：两个有序数组B[0..P-1]和C[0..q-1]
 4 //输出：A[0..p+q-1]中已经有序存放了B和C中的元素
 5 i<-0;j<-0;k<-0
 6 while i<p and j<q do
 7     if B[i]<=C[j]
 8     else A[k]<-C[j];j<-j+1
 9     k<-k+1;
10     if i=p
11          copy C[j..q-1] to A[k..p+1-1]
12     else copy B[i..p-1] to A[k..p+q-1]

合并排序代码实现：

 1 result mergeSort(int *intArray,int n){
 2     if(intArray==NULL||n<0){
 3         return fail;
 4     }
 5     if(n==1){
 6         return success;
 7     }
 8     //分离
 9     int leftLength=n/2;
10     int rightLength=n-leftLength;
11 
12     int *leftArray=(int *)malloc(leftLength*sizeof(int *));
13     int *rightArray=(int *)malloc(rightLength*sizeof(int *));
14 
15     copy(intArray,leftArray,0,0,leftLength);
16     copy(intArray,rightArray,leftLength,0,rightLength);
17 
18 
19     //子数组排序
20     mergeSort(leftArray,leftLength);
21     mergeSort(rightArray,rightLength);
22 
23     //合并
24     merge(leftArray,rightArray,intArray,n);
25     return success;
26 }
27 
28 result merge(int *leftArray,int *rightArray,int *intArray,int n){
29     if(leftArray==NULL||rightArray==NULL||intArray==NULL||n<2){
30         return fail;
31     }
32     int leftLength=n/2;
33     int rightLength=n-leftLength;
34 
35     int leftIndex=0;
36     int rightIndex=0;
37     int intIndex=0;
38 
39     while(leftIndex<leftLength&&rightIndex<rightLength){
40         if(leftArray[leftIndex]<=rightArray[rightIndex]){
41             intArray[intIndex]=leftArray[leftIndex];
42             leftIndex++;
43         }else{
44             intArray[intIndex]=rightArray[rightIndex];
45             rightIndex++;
46         }
47         intIndex++;
48     }
49     if(leftIndex==leftLength){
50         copy(rightArray,intArray,rightIndex,intIndex,n-intIndex);
51     }else{
52         copy(leftArray,intArray,leftIndex,intIndex,n-intIndex);
53     }
54     return success;
55 }
56 
57 void copy(int *sourceArray,int *distArray,int sourceStart,int distStart,int length){
58     for(int i=0;i<length;i++){
59         distArray[distStart+i]=sourceArray[sourceStart+i];
60     }
61 }

完整代码：

View Code

 1 result mergeSort(int *intArray,int n){
 2      if(intArray==NULL||n<0){
 3          return fail;
 4      }
 5      if(n==1){
 6          return success;
 7      }
 8      //分离
 9      int leftLength=n/2;
10      int rightLength=n-leftLength;
11  
12      int *leftArray=(int *)malloc(leftLength*sizeof(int *));
13      int *rightArray=(int *)malloc(rightLength*sizeof(int *));
14  
15      copy(intArray,leftArray,0,0,leftLength);
16      copy(intArray,rightArray,leftLength,0,rightLength);
17  
18  
19      //子数组排序
20      mergeSort(leftArray,leftLength);
21      mergeSort(rightArray,rightLength);
22  
23      //合并
24      merge(leftArray,rightArray,intArray,n);
25      return success;
26  }
27  
28  result merge(int *leftArray,int *rightArray,int *intArray,int n){
29      if(leftArray==NULL||rightArray==NULL||intArray==NULL||n<2){
30          return fail;
31      }
32      int leftLength=n/2;
33      int rightLength=n-leftLength;
34  
35      int leftIndex=0;
36      int rightIndex=0;
37      int intIndex=0;
38  
39      while(leftIndex<leftLength&&rightIndex<rightLength){
40          if(leftArray[leftIndex]<=rightArray[rightIndex]){
41              intArray[intIndex]=leftArray[leftIndex];
42              leftIndex++;
43          }else{
44              intArray[intIndex]=rightArray[rightIndex];
45              rightIndex++;
46          }
47          intIndex++;
48      }
49      if(leftIndex==leftLength){
50          copy(rightArray,intArray,rightIndex,intIndex,n-intIndex);
51      }else{
52          copy(leftArray,intArray,leftIndex,intIndex,n-intIndex);
53      }
54      return success;
55  }
56  
57  void copy(int *sourceArray,int *distArray,int sourceStart,int distStart,int length){
58      for(int i=0;i<length;i++){
59          distArray[distStart+i]=sourceArray[sourceStart+i];
60      }
61  }

参考：算法设计与分析基础