1 / 15
文档名称:

-快速排序.ppt

格式:ppt   页数:15页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

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

分享

预览

-快速排序.ppt

上传人:875845154 2016/3/25 文件大小:0 KB

下载得到文件列表

-快速排序.ppt

相关文档

文档介绍

文档介绍:第第 10 10 章章排序排序数据结构讲义 - 快速排序 交换排序交换排序两两比较待排序记录的关键两两比较待排序记录的关键码,如果发生逆序(即排列顺序与排序后的次序正好码,如果发生逆序(即排列顺序与排序后的次序正好相反),则交换之,直到所有记录都排好序为止。相反),则交换之,直到所有记录都排好序为止。交换排序的主要算法有: 1) 冒泡排序 2) 快速排序交换排序的基本思想是: 交换排序的基本思想是: 1) 1) 冒泡排序冒泡排序基本思路: 每趟不断将记录两两比较,并按“前小后大”(或“前大后小”)规则交换。优点: 每趟结束时,不仅能挤出一个最大值到最后面位置, 还能同时部分理顺其他元素;一旦下趟没有交换发生,还可以提前结束排序。前提: 顺序存储结构例: 关键字序列 T=(21 ,25,49,25*,16,08),请写出冒泡排序的具体实现过程。 21,25,49, 25 *,16, 08 21,25,25*,16, 08 ,49 21,25,16, 08 ,25*,49 21,16, 08 ,25,25*,49 16,08 ,21,25,25*,49 08,16,21,25,25*,49 初态: 第1趟第2趟第3趟第4趟第5趟冒泡排序练习冒泡排序练习?设要将序列( Q, H, C, Y, P, A, M, S, R, D, F, X )中的关键码按字母序的升序重新排列。冒泡排序一趟扫描的结果是。?( H, C, Q, P, A, M, S, R, D, F, X , Y ) void bubble_sort(SqList *L) { int m,i,j,flag=1; RecordType x; m=n-1; while((m>0)&&(flag==1)) { flag=0; for(j=1;j<=m;j++) if(L->r[j].key>L->r[j+1].key) { flag=1; x=L->r[j]; L->r[j]=L->r[j+1]; L->r[j+1]=x; } m--; }} 冒泡排序的算法分析冒泡排序的算法分析时间效率: 时间效率: O O( (n n 2 2) ) ——因为要考虑最坏情况因为要考虑最坏情况空间效率: 空间效率: O O( (1 1) )——只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳定定性: 性: 稳定稳定——25 25和和25 25 * *在排序前后的次序未改变在排序前后的次序未改变详细分析: ?最好情况: 初始排列已经有序,只执行一趟起泡,做 n-1 次关键码比较,不移动对象。?最坏情形: 初始排列逆序, 算法要执行 n-1趟起泡,第 i趟(1?i?n)做了 n- i 次关键码比较,执行了 n-i 次对象交换。此时的比较总次数 KCN 和记录移动次数 RMN 为: ?????????????? 11 1112 33 12 1 ni ninnin RMN nnin KCN )()( )()( 2 2) )快速排序快速排序从待排序列中任取一个元素从待排序列中任取一个元素 ( (例如取第一例如取第一个个) ) 作为中心,所有比它小的元素一律前放,所作为中心,所有比它小的元素一律前放,所有比它大的元素一律后放,形成左右两个子表; 有比它大的元素一律后放,形成左右两个子表; 然后再对各子表重新选择中心元素并依此规则调然后再对各子表重新选择中心元素并依此规则调整,直到每个子表的元素只剩一个。此时便为有整,直到每个子表的元素只剩一个。此时便为有序序列了。序序列了。基本思想: 基本思想: 优点: 优点: 因为每趟可以确定不止一个元素的位置,而且因为每趟可以确定不止一个元素的位置,而且呈指数增加,所以特别快! 呈指数增加,所以特别快! 前提: 前提: 顺序存储结构顺序存储结构( ) , 设以首元素为枢轴中心例例1 1: :关键字序列关键字序列 T=(21 T=(21 , , 25 25 , , 49 49 , , 25 25 * *, , 16 16 , , 08 08 ), ), 请写出快速排序的算法步骤。请写出快速排序的算法步骤。 21, 25 , 49 , 25 *,16, 08 初态: 第1趟: 第2趟: 第3趟: 问题: 问题: 1. 1. 这种不断划分子表的过程,计算机如何自动实现? 这种不断划分子表的过程,计算机如何自动实现? 2. 2. ““快速排序快速排序””是否真的比任何排序算法都快? 是否真的比任何排序算法都快? 08,16,21,25,2

最近更新

芪参虫草酒传统工艺现代化-全面剖析 35页

影视制作伦理探讨-全面剖析 35页

连续流动分析仪测定水环境中挥发酚的研究 3页

进一步加强基层央行专业技术人才队伍建设的思.. 3页

数据加密与安全策略-全面剖析 33页

过程能力指数在化探样品分析质量评估中的应用.. 3页

高尔夫专卖店出租合同(3篇) 7页

辅助器材在篮球训练中的应用现状及发展对策探.. 3页

车铣加工中心铣螺纹宏程序的应用 3页

记忆原理及方法 69页

议论文巧设分论点llh 64页

超声多普勒水连续油水分散流流速测量方法 4页

资产重组的市场反应——1997 年沪市资产重组实.. 3页

认知升级第一原理part1刻意练习(一) 78页

负荷预测在县级电网规划中的应用 4页

语言经济学视域下理工类研究生外语复合型人才.. 5页

试油过程中的油气层保护技术研究 3页

论仿射不变特征和空间技术特点的图像检索分析.. 3页

计算机智能仿真技术在印制电路板镀铜工艺中的.. 4页

解决细纱机长车龙筋变形方法浅析 3页

装备制造业三维作业指导应用研究 3页

行政事业单位会计内部控制的现状及其完善对策.. 3页

蝴蝶式多层悬臂梁压电发电装置研究 3页

薄板烘丝机自动控制系统中的PLC技术分析 3页

营改增对港口企业的影响与对策 3页

茶多酚对运动员健康体适能的影响研究 3页

节能材料在房屋建筑工程施工中的应用研究 4页

2025年度个人住宅水电安装与安全风险评估承包.. 8页

2025年度专业保洁团队保洁员劳动合同 7页

2025年家长学校学生安全教育与责任协议 7页