电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

数据结构-10 内部排序

74页
  • 卖家[上传人]:ldj****22
  • 文档编号:57189857
  • 上传时间:2018-10-19
  • 文档格式:PPT
  • 文档大小:1.19MB
  • / 74 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、第10章 内部排序,10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较讨论,排序就是将一组杂乱无章的数据按一定的规律顺次排列起来。 排序的目的是为了方便以后的查找。,10.1 概述,排序(Sorting):简单地说,就是将一组记录按关键字域递增(由小到大)或递减(由大到小)的次序重新排列。 排序码(Sort Key):作为排序依据的关键字。,有序表:排序后的结果。 无序表:排序前的状态。,升序表正序表:按排序码升序排列的有序表。 降序表逆序表:按排序码降序排列的有序表。,一、概念:,稳定排序:键值相同的记录,排序后相对次序总能保持不变。 不稳定排序:键值相同记录排序前后相对次序不能保持不变。,待排序列: 49,38,65,97,76,13,27,49 排序后:13,27,38,49,49,65,76,97 稳定 排序后:13,27,38,49,49,65,76,97不稳定,内排序:排序过程全部在内存中进行。 外排序:排序过程需要进行内存和外存之间的数据交换。,内排序,插入排序(直插排序、二

      2、分排序、希尔排序) 交换排序(冒泡排序、快速排序) 选择排序 (直选排序、树型排序、堆排序) 归并排序(二路归并排序、多路归并排序) 分配排序 (多关键字排序、基数排序),无序区,有序区增长法:排序表可分成有序区和无序区,随着排序过程的进行,有序区逐渐增长,无序区逐渐缩小,最后全部为有序区,排序结束。初始有序区可为空或仅含一个元素,其余为无序区。,一趟排序,有序区,有序区,无序区,有序度增长法:排序表不能分成明显的有序区和无序区,但排序过程的每一步,整个排序表的有序程度都提高一点,最后变得完全有序。,评价标准: 1)时间; 2)附加空间。 3)算法的稳定性、复杂程度等 附加空间一般不大,排序经常执行,时间开销是最重标志。 两种基本操作: 1)比较:比较关键字的大小 2)移动:将记录从一个位置移动到另一个位置。 时间开销主要指关键字的比较次数和记录的移动次数。 当键值是字串时,比较要占用较多的时间;当记录很大时,交换记录时移动要占较多时间。 比较一般都需要,但移动可改变存储方式来避免。,二、时空分析:,1)顺序存储。对记录本身进行物理重排,移到合适的位置。 2)链式存储。无需移动记录,仅

      3、修改指针。(链)表排序。 3)索引顺序存储。对索引表物理重排,不移动原始记录本身。,三、存储方式,const int maxsize=100; /排序表容量,假设为100 typedef int datatype; /假设关键字为int typedef struct datatype key; /关键字域 othertype other; /其它域 rectype; /记录类型 typedef rectype listmaxsize+1; /排序表类型,0号单元不用(或作它用,如“监视哨”),为简单起见,本章以数组作存储结构:,10.2 插入排序,基本思想 依次将待排记录插入到有序区适当位置,直到全部记录插入完毕; 初始有序区只有一个元素。,一、基本思想,每次将无序区第1条记录插入到有序区适当位置。初始取第1条记录为有序区,其它记录为无序区。随着排序进行,有序区不断扩大,无序区不断缩小。最终无序区为空,有序区包含了全部记录,排序结束。 有序区也可从排序表的尾部生成 。,10.2.1 直接插入排序 (Straight Insertion Sort),例1:对(49 38 13 76 65

      4、 97 27 49 )直接插入排序。 初始:(49)38 13 76 27 49,(13 38 49 49 65 97),(13 27 38 49 65 )49,(13 38 49 76)27 49,(13 38 49 )76 27 49,(38 49)13 76 27 49,为提高插入时的查找 效率,可以采用 折半查找 称为 折半插入排序,void InsertSort(list R,int n) /无监视哨 int i,j; NODE x; /x为中间结点变量 for(i=2;i=Ri-1.key) continue; x=Ri; /把待排记录赋给 x j=i-1; do /顺序比较和移动 Rj+1=Rj;j-; while(j0 /插入Ri ,二、算法实现,无序区第一记录Ri 插入有序区R1Ri1,找插入位置和移动记录交替进行:从有序区的后部j开始,如果该位置记录大于待插记录,则后移一位;待插记录插入到最后空出的位置上。,void InsertSort(list R,int n) /有监视哨 int i,j; for(i=2;i=Ri-1.key) continue; R0=Ri

      5、; /R0是监视哨 j=i-1; do /顺序比较和移动 Rj+1=Rj;j-; while(R0.keyRj.key); Rj+1=R0; /插入Ri ,R0为监视哨(Sentinel),省略下标越界检查“j0”:一旦越界,j=01,循环条件R0.keyRj.key不成立,自动控制while循环的结束。,初始:,i=3:,j=2:,j=1:,j=0:,例 有监视哨,第3趟,三、效率分析,时间: 最好:正序,n-1趟插入,每趟比较1次,移动0次: Cmin=n-1=O(n),Mmin=0 最坏:逆序,每趟比较i-1次,移动i-1+2次。 平均: O(n2) 空间:一个辅助空间,用于交换(或监视哨) 。 稳定:相邻元素比较和移动 可用于链表 适用于基本(正向)有序或n较少的情况,一、基本思想,排序表分成若干组,相隔为某个“增量”的记录为一组,各组内直接插入排序;初始增量d1较大,分组较多(每组的记录数少),以后增量逐渐减少,分组减少(每组的记录数增多),直到最后增量为1(d1d2dt=1),所有记录放为同一组,再整体进行一次直接插入排序。 又称“缩小增量排序”(Diminishing I

      6、ncrement Sort) 。,10.2.2 希尔排序,例如,对(49,38,65,97,76,13,27,49)希尔排序。,初始关键字,d1=5,例如,对(49,38,65,97,76,13,27,49)希尔排序。,8,7,6,5,4,3,2,1,一趟排序结果,d1=3,例如,对(49,38,65,97,76,13,27,49)希尔排序。,8,7,6,5,4,3,2,1,二趟排序结果,d1=1,例如,对(49,38,65,97,76,13,27,49)希尔排序。,一趟排序结果,二趟排序结果,三趟排序结果,初始关键字,二、算法实现,void ShellInsert(list R,int n,int h) /一趟插入排序,h为本趟增量 int i,j,k; for(i=1;i=Rjh.key) continue; R0=Rj; /R0保存待插记录,但不是监视哨 k=jh; /待插记录的前一个记录 do /查找插入位置 Rk+h=Rk;k=kh;/后移记录,继续向前搜索 while(k0 /插入Rj ,两个for循环可合并为一个:for(j=1+h;j=n;j+),相当于对每组交替直接插

      7、入排序。,void ShellSort(list R,int n,int d,int t) /d为增量序列,t为增量序列长度 int i; for(i=0;it;i+) /各趟插入排序 ShellInsert(R,n,di); ,希尔排序就是调用若干趟插入排序:,三、效率分析,时间:O(nlog2n)和O(n2)之间,大致O(n1.3) ,优于直接插入 其一,加速原理。相隔为增量的记录一组,组内移动一位,对原序列则移动若干位,加速向目标位置移动。开始时无序程度大,增量大,加速快;以后每个增量排序后,有序度提高一些,增量缩小,加速减缓。 其二,基本有序和小规模原理。开始时增量大,分组多,组内记录少,组内直接插入快;后来增量缩小,分组少,组内记录多,但有序性提高了,排序也较快。 不稳定:组内“相邻”移动,原序列则跳跃移动,10.3 交换排序,基本思想: 每次比较两个待排序的记录,如果关键字的次序与排序要求相反时就交换两者的位置,直到没有反序的记录为止。 特点: 键值较大的记录向排序表的一端移动,键值较小的记录向另一端移动。,一、基本思想,设排序表垂直放置,每个记录看作重量为键值的气泡;根据

      8、轻上重下原则,从下往上扫描,违反本原则的轻气泡,向上“飘浮”,如此反复,直到任何两个气泡都是轻上重下为止。 每一趟一个“最轻”的气泡冒到顶部上升法。 也可从上向下扫描,这时每一趟是一个“最重”的气泡沉到底部下沉法。 每次交换时,其中一个总沿着最终方向,另一个则未必(取决于上升法还是下降法)。,起泡排序(Bubble Sort),例:对(49,38,65,97,76,13,27,49)冒泡排序。,void BubbleSort(list R,int n) /上升法冒泡排序 int i,j,flag; for(i=1;i=i+1;j) /从下向上扫描 if(Rj.keyRj1.key) /交换记录 flag=1; R0=Rj;Rj=Rj1;Rj1=R0; /交换,R0作辅助量 if(!flag) break; /本趟未交换过,排序结束 ,二、算法实现,排序中各元素不断接近自己的位置,如果一趟下来没有交换,则序列已经有序,可设一个标志flag判断,提前结束。,时间: 最好:初始正序,一趟排序,比较n-1次,移动0: Cmin=n-1=O(n),Mmin=0: 最坏:初始逆序,n-1趟排序,每

      9、趟比较ni次,每次比较3次移动: 平均: O(n2) 辅助空间1,用于交换(用R0代替)。 稳定:只对相邻记录顺序比较和交换。 可用于链表(下沉法),三、效率分析,例 链表起泡排序下沉法,15,35,25,h,45,q,p,15,35,h,25,45,end,end,h,15,25,35,45,end,NULL,搜索结束条件:p-next=end end初值为NULL,以后指向每趟最后点。,一、基本思想,任选一记录作基准,其它记录与之比较,小于等于放基准前面;大于等于放基准后面。 一趟排序后,左子序列小于等于基准,右子序列大于等于基准。对两子序列进行同样处理,直至每组只有1个记录,全部记录有序。 又称划分交换排序 可看成冒泡排序的改进:记录的比较和交换从两端向中间进行,较大的记录每次交换到较后位置,较小的交换到较前位置,每次移动距离较远,总的比较和移动次数较少。 是目前为止所有内排序中速度最快的一种。,快速排序(Quick Sorting),1)一趟划分:,二、算法实现,设划分区间RpRq,指针i、j分别指向p、q。第1记录作基准 j从右向左扫描,找1个小于基准的记录Rj,移到位置i; i自i+1起从左向右扫描,找1个大于基准的记录Ri,移到位置j 再令j自j1起向左扫描, 如此交替改变扫描方向,从两端往中间靠拢,直至i=j时,i便是基准的最终位置,将它放在该处。,

      《数据结构-10 内部排序》由会员ldj****22分享,可在线阅读,更多相关《数据结构-10 内部排序》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.