数据结构0409归并排序课件.ppt

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)。总 结归并排序很显然是一种稳定的排序方法。它也可用于链式存储结构存储的记录序列，并且不需要辅助的记录存储空间，但递归实现时仍然需要开辟相应的递归工作栈。