欢迎来到天天文库
浏览记录
ID:58713018
大小:672.50 KB
页数:42页
时间:2020-10-04
《第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(s3、;while(i+2*s-14、等长的两组数据合并*/merge(sr,tr,i,i+s-1,n-1);elsewhile(i5、t–recursivedefinition(自学)Definition:Asortalgorithmthatsplitstheitemstobesortedintotwogroups,recursivelysortseachgroup,andmergesthemintoafinal,sortedsequence.RuntimeisO(nlogn).MergeSort–Divide-and-ConquerDivide-and-conquerisageneralalgorithmdesignparadigm:Divide:dividethei6、nputdataSintwodisjointsubsetsS1andS2Recur:solvethesub-problemsassociatedwithS1andS2Conquer:combinethesolutionsforS1andS2intoasolutionforSThebasecasefortherecursionaresub-problemsofsize0or1归并排序的递归算法msort(intx[],intaux[],ints,intt)/*将x[s..t]归并排序为aux[s..t]*/{if(s==t)aux[s]=x7、[s];else{m=(s+t)/2;msort(x,aux,s,m);msort(x,aux,m+1,t);merge(aux,x,s,m,t);}}MergeSort-example72948、3861PartitionMergeSort-example72949、38617210、94Recursivecall,partitionMergeSort-example729411、38617212、94713、2Recursivecall,partitionMergeSort-example729414、38617215、94716、277Recursivecall17、,basecaseMergeSort-example729418、38617219、94720、27722Recursivecall,basecaseMergeSort-example729421、386
3、;while(i+2*s-14、等长的两组数据合并*/merge(sr,tr,i,i+s-1,n-1);elsewhile(i5、t–recursivedefinition(自学)Definition:Asortalgorithmthatsplitstheitemstobesortedintotwogroups,recursivelysortseachgroup,andmergesthemintoafinal,sortedsequence.RuntimeisO(nlogn).MergeSort–Divide-and-ConquerDivide-and-conquerisageneralalgorithmdesignparadigm:Divide:dividethei6、nputdataSintwodisjointsubsetsS1andS2Recur:solvethesub-problemsassociatedwithS1andS2Conquer:combinethesolutionsforS1andS2intoasolutionforSThebasecasefortherecursionaresub-problemsofsize0or1归并排序的递归算法msort(intx[],intaux[],ints,intt)/*将x[s..t]归并排序为aux[s..t]*/{if(s==t)aux[s]=x7、[s];else{m=(s+t)/2;msort(x,aux,s,m);msort(x,aux,m+1,t);merge(aux,x,s,m,t);}}MergeSort-example72948、3861PartitionMergeSort-example72949、38617210、94Recursivecall,partitionMergeSort-example729411、38617212、94713、2Recursivecall,partitionMergeSort-example729414、38617215、94716、277Recursivecall17、,basecaseMergeSort-example729418、38617219、94720、27722Recursivecall,basecaseMergeSort-example729421、386
4、等长的两组数据合并*/merge(sr,tr,i,i+s-1,n-1);elsewhile(i5、t–recursivedefinition(自学)Definition:Asortalgorithmthatsplitstheitemstobesortedintotwogroups,recursivelysortseachgroup,andmergesthemintoafinal,sortedsequence.RuntimeisO(nlogn).MergeSort–Divide-and-ConquerDivide-and-conquerisageneralalgorithmdesignparadigm:Divide:dividethei6、nputdataSintwodisjointsubsetsS1andS2Recur:solvethesub-problemsassociatedwithS1andS2Conquer:combinethesolutionsforS1andS2intoasolutionforSThebasecasefortherecursionaresub-problemsofsize0or1归并排序的递归算法msort(intx[],intaux[],ints,intt)/*将x[s..t]归并排序为aux[s..t]*/{if(s==t)aux[s]=x7、[s];else{m=(s+t)/2;msort(x,aux,s,m);msort(x,aux,m+1,t);merge(aux,x,s,m,t);}}MergeSort-example72948、3861PartitionMergeSort-example72949、38617210、94Recursivecall,partitionMergeSort-example729411、38617212、94713、2Recursivecall,partitionMergeSort-example729414、38617215、94716、277Recursivecall17、,basecaseMergeSort-example729418、38617219、94720、27722Recursivecall,basecaseMergeSort-example729421、386
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、277Recursivecall
17、,basecaseMergeSort-example7294
18、386172
19、947
20、27722Recursivecall,basecaseMergeSort-example7294
21、386
此文档下载收益归作者所有