数据结构课件10.优秀PPT.ppt
《数据结构课件10.优秀PPT.ppt》由会员分享,可在线阅读,更多相关《数据结构课件10.优秀PPT.ppt(65页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第十章 内部排序10.1 概述10.2 插入排序10.3 交换排序10.4 选择排序10.5 归并排序10.6 基数排序10.7 各种内部排序方法比较10.8 例题解析1数据结构-第十章 内部排序10.1 概述概述10.1.1 什么是排序什么是排序 是依据记录关键字的值的递增是依据记录关键字的值的递增(递减递减)的关系将多的关系将多个记录的次序重新排列。个记录的次序重新排列。定义:定义:设有含设有含n个记录的文件个记录的文件 R1,R2,.,Rn,对应的关键字序列为对应的关键字序列为 K1,K2,.,Kn,求一个置换求一个置换 p1,p2,.,pn 使文件按关键字有序使文件按关键字有序 Rp1
2、,Rp2,.,Rpn,满足满足 Kp1 Kp2.Kpn 或或 Kp1 Kp2 .Kpn2数据结构-第十章 内部排序10.1.2 排序的分类排序的分类依据排序时文件记录的存放位置:依据排序时文件记录的存放位置:内部排序:排序过程中将全部记录放在内存中处理。内部排序:排序过程中将全部记录放在内存中处理。外部排序:排序过程中需在内外存之间交换信息。外部排序:排序过程中需在内外存之间交换信息。依据排序前后相同关键字记录的相对次序:依据排序前后相同关键字记录的相对次序:稳定排序:设文件中随意两个记录的关键字值相同,稳定排序:设文件中随意两个记录的关键字值相同,即即Ki=Kj(i j),若排序之前记录,若
3、排序之前记录Ri领先于记录领先于记录Rj,排序,排序后这种关系不变后这种关系不变(对全部输入实例而言对全部输入实例而言)。不稳定排序:只要有一个实例使排序算法不满足稳不稳定排序:只要有一个实例使排序算法不满足稳定性要求。定性要求。3数据结构-第十章 内部排序依据文件的存储结构划分排序的种类依据文件的存储结构划分排序的种类 连续依次文件排序连续依次文件排序 链表排序链表排序 地址排序地址排序:待排记录依次存储,排序时只对协助待排记录依次存储,排序时只对协助 表表(关键字关键字+指针指针)的表目进行物理重排。的表目进行物理重排。依据排序中运用的主要方法依据排序中运用的主要方法 插入排序插入排序 交
4、换排序交换排序 选择排序选择排序 归并排序归并排序 基数排序基数排序依据排序算法所需的协助空间依据排序算法所需的协助空间 就地排序:就地排序:O(1)非就地排序:非就地排序:O(n)或与或与n有关有关 4数据结构-第十章 内部排序10.1.3 评价排序算法的主要标准评价排序算法的主要标准 时间开销时间开销 考察算法的两个基本操作的次数:考察算法的两个基本操作的次数:比较关键字比较关键字移动记录移动记录 算法时间还与输入实例的初试状态有关时,分状况:算法时间还与输入实例的初试状态有关时,分状况:最好最好最坏最坏平均平均空间开销空间开销 所需的协助空间所需的协助空间探讨约定:探讨约定:(1)连续依
5、次文件连续依次文件 (2)关键字非递减关键字非递减TYPE list=ARRAY 0.maxn OF RECORD key:keytype;.END;var r:list5数据结构-第十章 内部排序10.2 插入排序插入排序10.2.1 干脆插入排序(增量法)干脆插入排序(增量法)示例示例 R(0)R(-4)R(8)R(1)R(-4)R(-6)n=6 i=1 0 -4 8 1 -4 -6 i=2 -4 0 8 1 -4 -6 i=3 -4 0 8 1 -4 -6 i=4 -4 0 1 8 -4 -6 i=5 -4 -4 0 1 8 -6 i=6 -6 -4 -4 0 1 8 算法思想算法思想
6、每次使有序区增加一个记录每次使有序区增加一个记录稳定排序6数据结构-第十章 内部排序算法步骤算法步骤 0 1 i-1 i i+1 nr0.n ri (有序区)(无序区)循环(n-1)次,初值 i=21)把第i个记录用出保存在r0中,j=i-1 2)若r0 rj,则rj后移一位,j=j-1,转2);否则r0放在rj+1处,i=i+1,转1)7数据结构-第十章 内部排序哨兵哨兵/监视哨的作用监视哨的作用 简化边界条件的测试,提高算法时间效率。性能分析最好状况(原始数据按正序即非递减序排列)Cmin=n-1 Mmin=2(n-1)最坏状况(原始数据按逆序即非递增序排列)Cmax=(n+2)(n-1)
7、/2 Mmax=(n+4)(n-1)/2随机状况 Cavg=(Cmin+Cmax)/2n2/4 Mavg n2/4时间困难度O(n2)协助空间困难度O(1)8数据结构-第十章 内部排序改进措施改进措施折半插入排序折半插入排序 O(n2)算法思想:将循环中每一次在区间算法思想:将循环中每一次在区间 1,i-1 上上为确定插入位置的依次查找操作改为折半查找操作。为确定插入位置的依次查找操作改为折半查找操作。效果:削减关键字间的比较次数。效果:削减关键字间的比较次数。2-路插入排序路插入排序 O(n2)算法思想:设置与算法思想:设置与r同样大小的协助空间同样大小的协助空间d,将,将r1赋值给赋值给d
8、1,将,将d看作循环向量。对于看作循环向量。对于ri(2 i n),若若ri d1,则插入,则插入d1之后的有序序列中,反之则之后的有序序列中,反之则插入插入d1之前的有序序列中。之前的有序序列中。(避开避开r1关键字最小关键字最小/最最大大)效果:削减记录的移动次数。效果:削减记录的移动次数。表插入排序表插入排序 O(n2)算法思想:接受静态链表作为存储结构。算法思想:接受静态链表作为存储结构。若要利用折半查找,需将记录按序重排。若要利用折半查找,需将记录按序重排。9数据结构-第十章 内部排序算法要点算法要点是稳定排序更适合于原始记录基本呈正序的状况算法思想也适用于链式存储结构10数据结构-
9、第十章 内部排序10.2.2 希尔排序希尔排序(渐减渐减/缩小增量排序缩小增量排序)算法思想的动身点算法思想的动身点干脆插入排序在待排序列的关键字基本有序时,效率较干脆插入排序在待排序列的关键字基本有序时,效率较高高在待排序的记录个数较少时,效率较高在待排序的记录个数较少时,效率较高算法思想算法思想 先选定一个记录下标的增量先选定一个记录下标的增量d,将整个记录序列按,将整个记录序列按增量增量d从第一个记录起先划分为若干组,对每组运用干从第一个记录起先划分为若干组,对每组运用干脆插入排序的方法;然后减小增量脆插入排序的方法;然后减小增量d,不断重复上述过,不断重复上述过程,如此下去,直到程,如
10、此下去,直到d=1(此时整个序列是一组此时整个序列是一组)。11数据结构-第十章 内部排序 示例示例 46 82 52 40 67 31 40 73 d1=4 46 67 31 82 40 52 40 73 46 31 40 40 67 82 52 73 d2=2 40 46 52 67 31 40 73 82 40 31 46 40 52 73 67 82 d3=1 31 40 40 46 52 67 73 82 31 40 40 46 52 67 73 82不稳定排序4组2组1组12数据结构-第十章 内部排序性能分析性能分析时间困难度是n和d的函数试验结果:当n较大时,比较和移动次数约在n
11、1.25到1.6n1.25。就地排序算法要点是不稳定排序算法的时间性能优于干脆插入排序如何选择最佳d序列,目前尚未解决最终一个增量值必需为1避开增量序列中的值(尤其是相邻的值)有公因子不宜在链式存储结构上实现13数据结构-第十章 内部排序10.3 交换排序交换排序10.3.1 起泡排序起泡排序(冒泡排序冒泡排序)算法思想算法思想 将两个相邻记录的关键字进行比较,若为逆序则交换两者位置,小者往上浮,大者往下沉。算法步骤算法步骤 记录1和2、2和3、(n-1)和n的关键字比较(交换);记录1和2、2和3、(n-2)和(n-1)的关键字比较(交换);直到某一趟不出现交换操作为止。14数据结构-第十章
12、 内部排序 示例示例 0 -4 -4 -6 -6 -4 0 -6 -4 -4 8 -6 -4 -4 -4 -6 -4 0 0 0 -4 1 1 1 1 1 8 8 8 8 sorted F F F T稳定排序15数据结构-第十章 内部排序性能分析性能分析最好状况(原始数据按正序即非递减序排列)Cmin=n-1 Mmin=0最坏状况(原始数据按逆序即非递增序排列)Cmax=n(n-1)/2 Mmax=3n(n-1)/2时间困难度O(n2)协助空间困难度O(1)算法的改进每趟排序中,记录最终一次发生交换的位置双向交替扫描,下上,最轻升顶;上下,最重沉底算法要点是稳定排序移动记录次数较多,平均时间性
13、能比干脆插入排序差也可用于链式存储结构16数据结构-第十章 内部排序10.3.2 快速排序快速排序(分划交换排序分划交换排序/分治法分治法)分治算法原理分治算法原理1)分解:将原问题分解为若干子问题分解:将原问题分解为若干子问题2)求解:递归地解各子问题,若子问题的规模足够小,则求解:递归地解各子问题,若子问题的规模足够小,则干脆求解干脆求解3)组合:将各子问题的解组合成原问题的解组合:将各子问题的解组合成原问题的解快速排序算法思想快速排序算法思想 指定枢轴指定枢轴/支点支点/基准记录基准记录rp(通常为第一个记录通常为第一个记录),通过一趟排序将其放在正确的位置上,它把待排记录通过一趟排序将
14、其放在正确的位置上,它把待排记录分割为独立的两部分,使得分割为独立的两部分,使得 左边记录的关键字左边记录的关键字 rp.key 右边记录的关键字右边记录的关键字 对左右两部分记录序列重复上述过程,依次类推,直对左右两部分记录序列重复上述过程,依次类推,直到子序列中只剩下一个记录或不含记录为止。到子序列中只剩下一个记录或不含记录为止。(可以用可以用递归方法实现递归方法实现)17数据结构-第十章 内部排序 示例示例 (49)38 65 97 76 13 27 49 x=49 i j 27 38 65 97 76 13 ()49 i j 27 38 ()97 76 13 65 49 i j 27
15、38 13 97 76 ()65 49 i j 27 38 13 ()76 97 65 49 i j 27 38 13 49 76 97 65 49(i=j)18数据结构-第十章 内部排序性能分析性能分析最坏状况(原始数据正/逆序排列)Cmax=n(n-1)/2 Mmax Cmax O(n2)最好状况:每次划分的结果是基准的左、右两个无序子区间的长度大致相等 Cmin O(nlog2n)Mmin Cmin O(nlog2n)平均时间性能 Tavg(n)=kn ln(n)k:某个常数;n:待排序序列中记录个数协助空间困难度 取决于递归深度 最好状况 O(log2 n)最坏状况 O(n)19数据结
16、构-第十章 内部排序算法要点算法要点非稳定排序 反例 2,2,1:1 2 2 就平均时间而言,快速排序是目前被认为最好的一种内部排序方法。枢轴记录的合理选择可改善性能。例如,三者取中随机产生难于在单向链表结构上实现20数据结构-第十章 内部排序10.4 选择排序选择排序10.4.1 简洁选择排序简洁选择排序(干脆选择排序干脆选择排序)算法步骤算法步骤 第第1趟:从趟:从n个记录中选关键字最小的记录,与个记录中选关键字最小的记录,与 第第1个记录交换;个记录交换;第第2趟:从剩余的趟:从剩余的n-1个记录中选关键字最小的个记录中选关键字最小的 记录,与第记录,与第2个记录交换;个记录交换;第第i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件 10. 优秀 PPT
限制150内