第七章 快速排序

Quicksort（快速排序）

（一种算法设计技术）主要内容

Quick

sort快速排序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.Quicksort’sidea--DivideandConquer

Quicksortann-elementarray:--Divide:Partitionthearrayintotwosubarraysaroundapivotxsuchthatelementsinlowersubarray≤x≤elementsinuppersubarray

--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]:notyetexaminedA[r]:pivotExampleofPartitioningTheoperationofPartitiononasamplearray.Lightlyshadedarrayelementsareallwithvaluesnogreaterthanx(thepivot).Heavilyshadedarrayelementsareallwithvaluesgreaterthanx.Analysisofquicksort

AssumeallinputelementsaredistinctInpractice,therearebetterpartitioningalgorithmsforwhenduplicateinputelementsmayexistLetT(n)=worst-caserunningtimeonanarrayofnelementsWorst-caseofquicksort

Inputsortedorreversesorted已有序PartitionaroundminormaxelementOnesideofpartitionalwayshasnoelements

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

Ifwe’relucky,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(n

lgn)Worstcase

Θ(n2),whywepreferQuicksorttoMergesortQuicksortVS.MergesortWhichisbetter?Testenvironment:IBM370/158ProgramminginPL/1Inputconsistsofrandomintegersrangein(0,10000)n10001500200025003000350040004500MERGESORT500750105014001650200022502650QUICKSORT40060085010501300155018002050n50005500600065007000750080008500MERGESORT29003450350038504250455049505200QUICKSORT23002650280030003350370039004100Quicksort平均时间分析Quicksort平均时间分析Quicksort平均时间分析Randomize-PartitioningRandomizedquicks