




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 弹性考勤管理办法
- 特色农产品品牌建设与2025年农产品品牌农产品品牌投资策略研究报告
- 抵押等级管理办法
- 历史文化街区保护与开发中的城市规划与文化遗产保护技术应用创新路径研究报告
- 汽车零部件再制造产业绿色制造与可持续发展研究报告
- 杭州用工管理办法
- 施救车辆管理办法
- 改革台账管理办法
- 村级大棚管理办法
- 来电来函管理办法
- 2025年R1快开门式压力容器操作考试100题及答案
- 2025年中国离心式冷水中央空调行业市场深度分析及发展前景预测报告
- 滴灌通收入分成协议合同
- 园区建设保障房管理办法
- 2025入党培训考试题库及答案
- 2025至2030机场运营行业市场深度调研及前景趋势与投资报告
- 遂宁市射洪市招聘社区专职工作者考试真题2024
- 智慧工会平台管理办法
- 特应性皮炎的护理查房
- 2025至2030年中国智能炒菜机(炒菜机器人)行业市场现状调查及前景战略研判报告
- 宫腔镜手术围手术期护理
评论
0/150
提交评论