第18讲归并与基数排序ppt课件.ppt

《第18讲归并与基数排序ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序归并排序与基数排序归并排序TheMergeAlgorithmThemergealgorithmtakesasequenceofelementsinavectorvhavingindexrange[first,last).Thesequenceconsistsoftwoorderedsublistsseparatedbyanintermediateindex,calledmid.TheMergeAlgorithm…(Cont…)TheMergeAlgorithm…(Cont…)Mergesort归并排序[49][38][65][97]

2、[76][13][27][3849][6597][1376][27][38496597][132776][13273849657697]归并排序的非递归算法mergesort(intsr[],intn){inti,s=1;inttr[20];while(s

3、;while(i+2*s-1

4、等长的两组数据合并*/merge(sr,tr,i,i+s-1,n-1);elsewhile(i

5、t–recursivedefinition(自学)Definition:Asortalgorithmthatsplitstheitemstobesortedintotwogroups,recursivelysortseachgroup,andmergesthemintoafinal,sortedsequence.RuntimeisO(nlogn).MergeSort–Divide-and-ConquerDivide-and-conquerisageneralalgorithmdesignparadigm:Divide:dividethei

6、nputdataSintwodisjointsubsetsS1andS2Recur:solvethesub-problemsassociatedwithS1andS2Conquer:combinethesolutionsforS1andS2intoasolutionforSThebasecasefortherecursionaresub-problemsofsize0or1归并排序的递归算法msort(intx[],intaux[],ints,intt)/*将x[s..t]归并排序为aux[s..t]*/{if(s==t)aux[s]=x

7、[s];else{m=(s+t)/2;msort(x,aux,s,m);msort(x,aux,m+1,t);merge(aux,x,s,m,t);}}MergeSort-example7294

8、3861PartitionMergeSort-example7294

9、386172

10、94Recursivecall,partitionMergeSort-example7294

11、386172

12、947

13、2Recursivecall,partitionMergeSort-example7294

14、386172

15、947

16、277Recursivecall

17、,basecaseMergeSort-example7294

18、386172

19、947

20、27722Recursivecall,basecaseMergeSort-example7294

21、386