算法导论 第七章 快速排序课件.ppt

《算法导论 第七章 快速排序课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Quicksort（快速排序）（一种算法设计技术）主要内容Quicksort快速排序Randomizedquicksortalgorithm随机版本快速排序算法Quicksort快速排序Efficientsortingalgorithm--ProposedbyC.A.R.Hoarein1962--Divide-and-Conqueralgorithm--Sorts“inplace”(likeinsertionsort,butnotlikemergesort)--Verypractical(withtuning)--Canbeviewedas

2、arandomizedLasVegasalgorithm--Worst-caserunningtime:Θ(n2)--Expectedrunningtime:Θ(nlogn)--ConstanthiddeninΘ(nlogn)aresmall.Quicksort’sidea--DivideandConquerQuicksortann-elementarray:--Divide:Partitionthearrayintotwosubarraysaroundapivotxsuchthatelementsinlowersubarray≤x≤ele

3、mentsinuppersubarray--Conquer:Recursivelysortthesubarrays.--Combine:Trivial.Keypoint:Linear-timepartitioningsubroutine.Quicksort’sidea--DivideandConquerInitialcallQuicksort(A,1,n)Partitioningsubroutine划分子程序A[p,…,i]:knowntobe≤pivotA[i+1,…,j-1]:knowntobe>pivotA[j…r-1]:notyet

4、examinedA[r]:pivotExampleofPartitioningTheoperationofPartitiononasamplearray.Lightlyshadedarrayelementsareallwithvaluesnogreaterthanx(thepivot).Heavilyshadedarrayelementsareallwithvaluesgreaterthanx.AnalysisofquicksortAssumeallinputelementsaredistinctInpractice,therearebet

5、terpartitioningalgorithmsforwhenduplicateinputelementsmayexistLetT(n)=worst-caserunningtimeonanarrayofnelementsWorst-caseofquicksortInputsortedorreversesorted已有序PartitionaroundminormaxelementOnesideofpartitionalwayshasnoelementsT(n)=T(n-1)+T(0)+Θ(n)=T(n-1)+Θ(1)+Θ(n)=T(n-1)

6、+Θ(n)=Θ(n2)(算法级数)Worst-caserecursivetreeT(n)=T(n-1)+T(0)+Θ(n)ArecursiontreeforQUICKSORTinwhichthePartitionprocedurealwaysputsonlyasingleelementononesideofthepartition(theworstcase).TheresultingrunningtimeisΘ(n2)BestCasePartitioning对等划分ArecursiontreeforQUICKSORTinwhichthePa

7、rtitionalwaysbalancesthetwosidesofthepartitionequally(thebestcase).TheresultingrunningtimeisΘ(nlgn)Θ(nlgn)Best-caseanalysisIfwe’relucky,PARTITIONsplitsthearrayevenly:--T(n)=2T(n/2)+Θ(n)=Θ(nlogn).Whatifthesplitisalways1/10:9/10?平衡划分--T(n)≤T(9n/10)+T(n/10)+Θ(n)--Whatisthesol

8、utiontothisrecurrence?ARecursiontreeArecursiontreeforQUICKSORTinwhichPARTITIONalwaysprodu