1、 归并排序 归并排序“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。利用归并的思想实现排序假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到 n/2 个长度为2或1的有序子序列;再两两归并,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2-路归并排序。例题初始关键字:49 38 65 97 76 13 27一趟归并后:38 49 65 97 13 76 27二趟归并后:38 49 65 97 13 27 76三趟归并后:13 27 38 49 65 76 97 算法思想2-路归并排序将Rlow.high中的记录归并排序后
2、放入Tlow.high中。当序列长度等于1时,递归结束,否则:(1)将当前序列一分为二,求出分裂点mid=(low+high)/2;(2)对子序列Rlow.mid递归,进行归并排序,结果放入Slow.mid中;算法思想(3)对子序列Rmid+1.high递归,进行归并排序,结果放入Smid+1.high中;(4)调用算法Merge,将有序的两个子序列Slow.mid和Smid+1.high归并为一个有序的序列Tlow.high。算法描述void Msort(RedType R,RedType&T,int s,int t)/将Rs.t 归并排序为 Ts.t if(s=t)Ts=Rs;else m
3、=(s+t)/2;/将Rs.t平分为Rs.m和Rm+1.t Msort(R,TR2,s,m);/递归地将Rs.m归并为有序的TR2s.m Msort(R,TR2,m+1,t);/递归地Rm+1.t归并为有序的TR2m+1.t Merge(TR2,T,s,m,t);/将TR2s.m和TR2m+1.t归并到Ts.t /Msort 算法描述 void MergeSort(SqList&L)/对顺序表 L 作2-路归并排序 MSort(L.r,L.r,1,L.length);/MergeSort 将两个有序表归并为一个新的有序表的算法 void Merge(RedType R,RedType&T,in
4、t i,int m,int n)/将有序的记录序列Ri.m 和Rm+1.n 归并为有序的记录序列Ti.n int j,k;for(j=m+1,k=i;i=m&j=n;+k)/将SR中记录由小到大地并入TR if LQ(SRi.key,SRj.key)TRk=SRi+;else TRk=SRj+;if(i=m)/TRk.n=SRi.m;将剩余的SRi.m复制到TR while(k=n&i=m)TRk+=SRi+;if(j=n)/将剩余的SRj.n复制到TR while(k=n&j=n)TRk+=SRj+;/Merge 例 题52,23,80,36,68,14 (s=1,t=6)52,23,80 36,68,14 52,23 80 52 23,52 23,52,8036,68 14 36 6836,6814,36,68 14,23,36,52,68,80 23 算法的效率时间复杂度方面,由于每趟归并的时间复杂度O(n),而对于有n个记录的序列来说,一共需要进行 log2n 趟归并。因此归并排序的时间复杂度是O(n log2n)。空间复杂度方面,用顺序表实现归并排序时,需要和待排序记录个数相等的辅助存储空间,所以空间复杂度为O(n)。总 结归并排序很显然是一种稳定的排序方法。它也可用于链式存储结构存储的记录序列,并且不需要辅助的记录存储空间,但递归实现时仍然需要开辟相应的递归工作栈。