排序算法之归并排序

归并的含义是将两个或两个以上的有序表组合成一个新的有序表。

假定待排序表中含有n个记录，则可以看成是n个有序的字表，每个表的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序表；再两两归并，......如此重复，直到合并成一个长度为n的有序表为止，这种方法称为2-路归并排序。

算法实现：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 //构建一个辅助数组B
 5 int *B = (int*)malloc((8+1)*sizeof(int));
 6 //两段有序表A[low...mid],A[mid+1...high]放在同一顺序表中相邻的位置上
 7 void Merge(int A[],int low,int mid, int high)
 8 {
 9     int i,j,k;
10     for(int k=low;k<=high;k++)
11         B[k] = A[k];  //将A中的所有元素复制到B中
12     for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)
13     {
14         if(B[i]>B[j])
15             A[k]=B[j++];//将较小值复制到A中
16         else
17             A[k]=B[i++];
18 
19     }
20     //如果其中一个表检测完毕，将另一端的剩余部分直接复制到A中，下面两个while只会执行一个
21     while(i<=mid) A[k++]=B[i++];
22     while(j<=high) A[k++]=B[j++];
23 }
24 //归并排序的实现是基于分治的。
25 void MergeSort(int A[],int low,int high)
26 {
27     if(low<high)
28     {
29         int mid = (low+high)/2;
30         //对字表进行排序，然后合并
31         MergeSort(A,low,mid);
32         MergeSort(A,mid+1,high);
33         Merge(A,low,mid,high);
34     }
35 
36 }
37 void main()
38 {
39     int A[8] = {21,45,67,23,76,42,12,54};
40     MergeSort(A,0,7);
41     for(int i=0;i<8;i++)
42     {
43         cout<<"result: "<<A[i]<<endl;
44     }
45 }

算法分析：

平均时间复杂度：O(nlog2n)

空间复杂度：O(n) (用于存储有序子序列合并后有序序列)

稳定性：稳定