1 / 7
文档名称:

基于分治法的快速排序.doc

格式:doc   大小:150KB   页数:7页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

基于分治法的快速排序.doc

上传人:漫山花海 2019/5/26 文件大小:150 KB

下载得到文件列表

基于分治法的快速排序.doc

相关文档

文档介绍

文档介绍:Forpersonaluseonlyinstudyandresearch;(即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试),针对快速排序算法从实践中理解分治法的思想、求解策略及步骤。蚁实验目的衿理解分治法的核心思想以及分治法求解过程;袆从算法分析与设计的角度,对快速排序算法有更进一步的理解。莆环境要求莂 对于环境没有特别要求。对于算法实现,可以自由选择C,C++,Java,甚至于其他程序设计语言。袀实验步骤艿步骤1:理解问题,给出问题的描述。螅步骤2:算法设计,包括策略与数据结构的选择膂步骤3:描述算法。希望采用源代码以外的形式,如伪代码、流程图等;羂步骤4:算法的正确性证明。需要这个环节,在理解的基础上对算法的正确性给予证明;莇步骤5:算法复杂性分析,包括时间复杂性和空间复杂性;膅步骤6:算法实现与测试。附上代码或以附件的形式提交,同时贴上算法运行结果截图;袃步骤7:技术上、分析过程中等各种心得体会与备忘,需要言之有物。蝿 说明:步骤1-6在“实验结果”一节中描述,步骤7在“实验总结”一节中描述。蝿实验结果蚄问题描述蚃螀快速排序是一种划分交换排序,其基本思想是:通过一趟扫描将待排序的元素分割成独立的三个序列:第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置,因此需要再按此方法对第一个序列和第三个序列分别进行排序,整个排序过程可以递归进行,最终可使整个序列变成有序序列。袈算法设计芇快速排序采用分治策略莃快速排序的基本思想是基于分治策略的,利用分治法可将快速排序的基本思想描述如下:设当前排序的序列为R【low:high】,其中low<=high,如果序列的规模足够小则直接进行排序,否则分三步处理:袂A分解B求解子问题C合并羆描述算法螇void QuickSort(int R[],int low,int high)肄{ 虿 int pivotpos; //划分后的基准元素所对应的位置莈 if(low<high)//仅当区间长度大于1时才须排序膆{袄 pivotpos=Partition(R,low,high); 螀 QuickSort(R,low,pivotpos-1); 蒇//对左区间递归排序薆QuickSort(R,pivotpos+1,high); 薅//对右区间递归排序螂 }蝿} 肅正确性证明莅原始序列:49386597761327蕿第一次扫描:袈[273813]49[769765]蒄以27为基准元素螁得到的序列:[13]27[38]蚀以76为基准元素肆得到的序列:[65]76[97]袄最终序列为:薂 13、27、38、49、65、76、97蚂莈算法复杂性分析薇最坏情况O(n2)节葿蒇最好情况O(nlogn)羆肂平均情况:O(nlogn)薁衿空间复杂性:蒆由于快速排序算法是递归执行,需要一个栈来存放每一层递归调用的必要信息,其最大容量应与递归调用的深度一致。最好情况下

最近更新

2025年度农村土地买卖合同系列:农村土地征收.. 8页

2025年度农副产品电商平台数据分析服务合同 9页

高血压的护理查房ppt课件 24页

2025年性用品项目发展计划 62页

高考散文阅读用 45页

2025年己二酸二甲酯合作协议书 66页

2025年彩涂板(卷)合作协议书 48页

虚拟现实与增强现实在游戏设计中的应用-第1篇.. 26页

基于深度学习的物联网故障预测方法-全面剖析 27页

本合同有买卖双方订立 4页

社区封闭管理工作方案范文(29篇) 134页

一步摄影正片银颗粒结构与分布的超高压电子显.. 2页

读书的快乐三分钟演讲稿【汇编三篇】 4页

酒店年会致辞稿(6篇) 17页

销售月计划集锦(25篇) 57页

《金属压延孔板波纹填料技术交流会》在无锡召.. 2页

《电力技术》1980年总目录 2页

《大西洋Ⅰ—Ⅳ》氦氮氧饱和潜水减压的分析 2页

《兰州医学院学报》引文分析及文献利用评估 2页

“非电导爆系统的研究与应用技术交流会”论文.. 2页

“我国高技术R&D管理体制研究”项目研究方案 2页

“ZX-88煮茧法”新工艺在无锡县缫丝厂中试成功.. 2页

μ—Petri网多微处理机实现的设计方法论 2页

X射线能谱分析中谱线重叠问题 2页

2025年吕梁职业技术学院单招职业适应性测试题.. 74页

高清地图中国31省市区最全河流水系分布地图建.. 25页

2023年北京市事业单位统考真题及答案 11页

计算能手苏教版四年级下册电子版-94页 7页

2025届高考模拟作文“时间管理”升格导写 5页

剑桥雅思原版真题4 114页