《数据结构与算法设计PPT (48).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (48).pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第9章 归并排序9.7 归并排序2021/2/2412采用分治技术的排序算法归并排序快速排序归并算法思想 将初始数组重复分成两半直到剩下仅一个元素（长度为1的有序序列）重复将相邻的两个有序序列归并成一个有序序列直到所有的元素都在一个有序序列中-将两个有序的数组合并为一个序列放入另外一个数组中-通过将数组中两个元素中较小的一个复制到新数组中的方式进行合并有序序列4有序序列的归并算法11324262152738AptrBptrCptr113242621527381AptrBptrCptr1132426215273812AptrBptrCptr113242621527381213AptrBptrCp
2、tr两路归并排序(Merge Sort)对象序列 initList 中有两个有序表Vl Vm和Vm+1 Vn。它们可归并成一个有序表，存于另一对象序列 mergedList 的Vl Vn中。其基本思想是：-设两个有序表A和B的对象个数(表长)分别为 al 和 bl，-变量 i 和 j 分别是表A和表B的当前检测指针-设表C是归并后的新有序表，变量 k 是它的当前存放指针。08 21 25 25*49 62 72 93 16 37 54 l m m+1ninitListij08 16 21 25 25*37 49 54 62 72 93 l nmergeList相邻的两个有序表的归并过程k 当i
3、和j都在两个表的表长内变化时，根据Ai与Bj的关键码的大小，依次把关键码小的对象排放到新表Ck中；当i与j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表Ck中。此算法的关键码比较次数和对象移动次数均为(m-l+1)+(n-m)=n-l+1。两路归并排序(Merge Sort)迭代的归并排序算法 迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：假设初始对象序列有n 个对象，首先把它看成是n 个长度为 1 的有序子序列(归并项)先做两两归并，得到 n/2 个长度为 2 的归并项(如果n 为奇数，则最后一个有序子序列的长度为1)再做两两归并 如此重复，最后得到一个长度为
4、n 的有序序列。两路归并算法的实现template voidmerge(datalist&initList,datalist&mergedList,const intl,const intm,const intn)inti=0,j=m+1,k=0;while(i=m&j=n)/两两比较if(initList.Vectori.getKey()=initList.Vectorj.getKey()mergedList.Vectork=initList.Vectori;i+;k+;else 2021/2/2410mergedList.Vectork=initList.Vectorj;j+;k+;if(
5、i=m)for(intn1=k,n2=i;n1=n&n2=m;n1+,n2+)mergedList.Vectorn1=initList.Vectorn2;elsefor(intn1=k,n2=j;n1=n&n2=n;n1+,n2+)mergedList.Vectorn1=initList.Vectorn2;两路归并算法的实现一趟归并排序的过程 设数组initList.Vector1到initList.Vectorn中的 n个对象已经分为一些长度为len的归并项，将这些归并项两两归并，归并成一些长度为 2len的归并项，结果放到mergedList.Vector中。如果n不是2len的整数倍，则
6、一趟归并到最后，可能遇到两种情形：剩下一个长度为len的归并项和另一个长度不足len的归并项，可用一次merge算法，将它们归并成一个长度小于2len的归并项。只剩下一个归并项，其长度小于或等于len，可将它直接抄到数组MergedList.Vector中。template voidMergePass(datalist&initList,datalist&mergedList,const intlen)inti=0;while(i+2*len=initList.CurrentSize-1)merge(initList,mergedList,i,i+len-1,i+2*len-1);i+=2*l
7、en;if(i+len=initList.CurrentSize-1)merge(initList,mergedList,i,i+len-1,initList.CurrentSize-1);else for(intj=i;j=initList.CurrentSize-1;j+)mergedList.Vectorj=initList.Vectorj;两路归并算法的实现迭代的归并排序算法212525*25*936272083716544921 254962 9308 7216 375421 25 25*4908 62 72 9316 37 5408082116252125*254925*62377
8、249935416 37 5462 72 93len=1len=2len=4len=8len=16两路归并的主算法2021/2/2414template voidMergeSort(datalist&list)/按对象关键码非递减的顺序对表list中对象排序datalist&tempList(list.MaxSize);intlen=1;while(lenlist.CurrentSize)MergePass(list,tempList,len);len*=2;MergePass(tempList,list,len);len*=2;delete tempList;两路归并算法的性能分析 在迭代的
9、归并排序算法中，函数 MergePass()做一趟两路归并排序，要调用merge()函数n/(2*len)O(n/len)次，函数MergeSort()调用MergePass()正好log2n 次，而每次merge()要执行比较O(len)次，所以算法总的时间复杂度为O(nlog2n)。归并排序占用附加存储较多，需要另外一个与原待排序对象数组同样大小的辅助数组。归并排序是一个稳定的排序方法。递归的表归并排序 与快速排序类似，归并排序也可以利用划分为子序列的方法递归实现。在递归的归并排序方法中，首先要把整个待排序序列划分为两个长度大致相等的部分，分别称之为左子表和右子表。对这些子表分别递归地进行排序，然后再把排好序的两个子表进行归并。图示：待排序对象序列的关键码为 21,25,49,25*,16,08，先是进行子表划分，待到子表中只有一个对象时递归到底。再是实施归并，逐步退出递归调用的过程。21 25 49 25*16 0821 25 4925*16 0821 25 49 25 4921 25*16 0825*16 08 21 25 49 25*16 0825*16 0821 25 4916 0825*25 4921 21 25*16 08 49 25 递归回推