算法导论-第七章-快速排序.ppt
- 文档编号:18814657
- 上传时间:2023-12-05
- 格式:PPT
- 页数:20
- 大小:1.26MB
算法导论-第七章-快速排序.ppt
《算法导论-第七章-快速排序.ppt》由会员分享,可在线阅读,更多相关《算法导论-第七章-快速排序.ppt(20页珍藏版)》请在冰点文库上搜索。
Quicksort(快速排序),(一种算法设计技术),主要内容,Quicksort快速排序Randomizedquicksortalgorithm随机版本快速排序算法,Quicksort快速排序,Efficientsortingalgorithm-ProposedbyC.A.R.Hoarein1962-Divide-and-Conqueralgorithm-Sorts“inplace”(likeinsertionsort,butnotlikemergesort)-Verypractical(withtuning)-CanbeviewedasarandomizedLasVegasalgorithm-Worst-caserunningtime:
(n2)-Expectedrunningtime:
(nlogn)-Constanthiddenin(nlogn)aresmall.,Quicksortsidea-DivideandConquer,Quicksortann-elementarray:
-Divide:
Partitionthearrayintotwosubarraysaroundapivotxsuchthatelementsinlowersubarrayxelementsinuppersubarray-Conquer:
Recursivelysortthesubarrays.-Combine:
Trivial.,Keypoint:
Linear-timepartitioningsubroutine.,Quicksortsidea-DivideandConquer,InitialcallQuicksort(A,1,n),Partitioningsubroutine划分子程序,ExampleofPartitioning,TheoperationofPartitiononasamplearray.Lightlyshadedarrayelementsareallwithvaluesnogreaterthanx(thepivot).Heavilyshadedarrayelementsareallwithvaluesgreaterthanx.,Analysisofquicksort,Assumeallinputelementsaredistinct,Inpractice,therearebetterpartitioningalgorithmsforwhenduplicateinputelementsmayexist,LetT(n)=worst-caserunningtimeonanarrayofnelements,Worst-caseofquicksort,Inputsortedorreversesorted已有序,Partitionaroundminormaxelement,Onesideofpartitionalwayshasnoelements,T(n)=T(n-1)+T(0)+(n)=T(n-1)+
(1)+(n)=T(n-1)+(n)=(n2)(算法级数),Worst-caserecursivetree,T(n)=T(n-1)+T(0)+(n),ArecursiontreeforQUICKSORTinwhichthePartitionprocedurealwaysputsonlyasingleelementononesideofthepartition(theworstcase).Theresultingrunningtimeis(n2),BestCasePartitioning对等划分,ArecursiontreeforQUICKSORTinwhichthePartitionalwaysbalancesthetwosidesofthepartitionequally(thebestcase).Theresultingrunningtimeis(nlgn),(nlgn),Best-caseanalysis,Ifwerelucky,PARTITIONsplitsthearrayevenly:
-T(n)=2T(n/2)+(n)=(nlogn).,Whatifthesplitisalways1/10:
9/10?
平衡划分-T(n)T(9n/10)+T(n/10)+(n)-Whatisthesolutiontothisrecurrence?
ARecursiontree,ArecursiontreeforQUICKSORTinwhichPARTITIONalwaysproducesa9-to-1split,yieldingarunningtimeofO(nlgn),Worstcase(n2),whywepreferQuicksorttoMergesort,QuicksortVS.Mergesort,Whichisbetter?
Testenvironment:
IBM370/158ProgramminginPL/1Inputconsistsofrandomintegersrangein(0,10000),Quicksort平均时间分析,Quicksort平均时间分析,Quicksort平均时间分析,Randomize-Partitioning,Randomizedquicksortalgorithm,Partitionaroundarandomelement,i.e.,aroundAt,wheretchosenuniformlyatrandomfrompr,expectedtimeisO(nlgn),思考题,7.2-2,37.4-2,3,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 导论 第七 快速 排序