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页

2025年度土地平整与城市生态修复合同 8页

2025年度国际艺术展冠名赞助合同 9页

2025年度国有企业房产转让合同 9页

2025年度团队旅行活动行程安排协议 9页

2025年度商铺租赁管理协议书(包括品牌入驻、.. 8页

2025年度商铺出租与租赁期限合同范本 8页

2025年度商业综合体地下车库车位租赁合同模板.. 7页

2025年度员工股权分红与激励相结合的协议书模.. 7页

2025年度员工分红股份分红权分配与调整协议 9页

2025年度吊车租赁合同简易版应急处理方案 8页

2025年度合同法在新能源项目投资合作协议 8页

2025年度合伙经营足浴店项目合作协议书 7页

2025年度合伙人企业股权转让及后续支持协议 7页

发布证券研究报告业务-《发布证券研究报告业务.. 38页

2025年度叉车租赁安全协议责任书(矿业开采).. 8页

2025年度单位临时租用个人车辆保障及责任划分.. 9页

2025年度医院急诊科耗材采购合同 9页

2025年度医药供应链管理与采购合作协议 9页

2025年度医疗机构消毒用品耗材长期供应协议 9页

2025年度医疗养老一体化服务项目合作协议 9页

2025年度区块链技术应用合伙经营合同书 9页

2025年度化妆品绿色环保原料采购销售合同 9页

2025年度劳动合同电子台账系统定制开发与实施.. 9页

2025年度劳务合同详细电子版:文化旅游景区餐.. 8页

2025年度办公楼转租合同附带企业内部网络搭建.. 8页

2025年度办公室室内装饰装潢设计合同 9页

2025年度创意工艺品代理购销合同范本 9页

2025年度出租车租赁与安全监控服务合同 9页