数据结构第十章.ppt
《数据结构第十章.ppt》由会员分享,可在线阅读,更多相关《数据结构第十章.ppt(56页珍藏版)》请在三一办公上搜索。
1、数据结构课程的内容,1,排序:将一个数据元素(或记录)的任意序列,重新 排列成一个按关键字有序的序列内部排序:将待排记录存放在计算机随机存储器重进 行的排序过程。外部排序:由于待排记录的数量很大,以至内存一次 不能容纳全部记录,在排序过程中尚需要 对外存进行访问的排序过程。,2,第十章 内部排序,第10章 内部排序,3,10.1 概述10.2 插入排序10.3 交换排序10.4 选择排序10.5 归并排序10.6 基数排序,4,10.1 概述,1、排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“按关键字有序”的记录序列。,52,49,80,36,14,58,61,23
2、,97,75,14,23,36,49,52,58,61,75,80,97,一般情况下,假设含n个记录的序列为R1,R2,Rn其相应的关键字序列为 K1,K2,Kn,这些关键字相互之间可以进行比较,即在它们之间存在这样一个关系:Kp1=Kp2=Kpn按此固有关系将上式记录序列重新排列为Rp1,Rp2,Rpn的操作称作排序,5,2、关键字,数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可以用来区分对象,作为排序依据,称为关键字。,关键字与记录之间是一对一的关系 称主关键字关键字与记录之间是一对多的关系 称次关键字,6,3、排序的目的是什么?,便于查找,4、排序算法的好坏如何衡量?,时间
3、效率 排序速度(即排序所花费的全部比较次数)空间效率 占内存辅助空间的大小 稳定性 若两个记录A和B的关键字相等,但排序后A,B的先后次序保持不变,则称这种排序算法是稳定的。,7,5、什么叫内部排序?什么叫外部排序,若待排序记录都在内存中,称内部排序 若待排序记录一部分在内存,一部分在外存,则称为外部排序。注:外部排序时,要将数据分批掉入内存来排序,中间结果还要及时放入内存,显然外部排序要复杂得的多。,8,6、待排序记录在内存中怎样存储和处理,(1)顺序排序 排序时直接移动记录;(2)链表排序 排序时只移动指针;(3)地址排序 排序时先移动地址,最后再移动记录。,注:地址排序中可以增设一维数组
4、来专门存放记录的地址。,9,6.顺序存储(顺序表)的抽象数据类型如何表示?,注:大多数排序算法都是针对顺序表结构的(便于直接移动元素),Typedef struct/定义每个记录(数据元素)的结构 KeyType key;/关键字 InfoType otherinfo;/其它数据项RecordType;,Typedef struct/定义顺序表的结构 RecordType r MAXSIZE+1;/存储顺序表的向量/r0一般作哨兵或缓冲区 int length;/顺序表的长度SqList;,#define MAXSIZE 20/设记录不超过20个typedef int KeyType;/设关键
5、字为整型量(int型),7.内部排序的算法有哪些?,10,按排序的规则不同,可分为5类:插入排序交换排序(重点是快速排序)选择排序归并排序基数排序,d关键字的位数(长度),按排序算法的时间复杂度不同,可分为3类:简单的排序算法:时间效率低,O(n2)先进的排序算法:时间效率高,O(nlog2n)基数排序算算法:时间效率高,O(dn),11,10.2 插入排序,插入排序的基本思想是:,插入排序有多种具体实现算法:1)直接插入排序 2)折半插入排序 3)表插入排序 4)希尔排序,每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。,简言之,边插
6、入边排序,保证子序列中随时都是排好序的。,12,(1)直接插入排序,基本思想:假定前面m 个元素已经排序;取第(m+1)个元素,插入到前面的适当位置;一直重复,到m=n 为止。(初始情况下,m=1),13,例1:关键字序列T=(13,6,3,31,9,27,5,11),请写出直接插入排序的中间过程序列。,【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13,31】,9,27,5,11【3,6,9,13,31】,27,5,11【3,6,9,13,27,31】,5,11【3,5,6,9,13,27,31】,11
7、【3,5,6,9,11,13,27,31】,14,void InsertSort(SqList/插入到正确位置/InsertSort,15,例2:关键字序列T=(21,25,49,25*,16,08),请写出直接插入排序的具体实现过程。,*表示后一个25,i=1,21,i=2,i=3,i=5,i=4,i=6,25,25,25,49,49,49,25*,49,16,16,08,49,解:假设该序列已存入一维数组V7中,将V0作为缓冲或暂存单元(Temp)。则程序执行过程为:,初态:,16,25,21,16,完成!,时间效率:O(n2)因为在最坏情况下,所有元素的比较次数总和为(02n)O(n2)
8、。其他情况下还要加上移动元素的次数。空间效率:O(1)因为仅占用1个缓冲单元算法的稳定性:稳定因为25*排序后仍然在25的后面。,特点:因为R1i-1是一个按关键字有序的有序序列,则可以利用折半查找实现在R1i-1中查找Ri的插入位置,如此实现的插入排序为折半插入排序。限制:必须采用顺序存储方式。,16,2)折半插入排序,17,(highlow,查找结束,插入位置为low 或high+1),(4236),(4253),18,2)折半插入排序,优点:比较的次数大大减少,全部元素比较次数仅为O(nlog2n)。时间效率:虽然比较次数大大减少,可惜移动次数并未减少,所以排序效率仍为O(n2)。空间效
9、率:O(1)稳定性:稳定,讨论:若记录是链表结构,用直接插入排序行否?折半插入排序呢?答:直接插入不仅可行,而且还无需移动元素,时间效率更高!,但链表无法“折半”!,19,设待排序的关键码分别为 28,13,72,85,39,41,6,20。按二分法插入排序算法已使前七个记录有序,中间结果如下:,试在此基础上,沿用上述表达方式,给出继续采用二分法插入第八个记录的比较过程。在一些特殊情况下,二分法插入排序比直接插入排序要执行更多的比较。这句话对吗?,6 13 28 39 41 72 85 20,r=7,i=1,m=4,3)希尔(shell)排序(又称缩小增量排序),20,基本思想:先将整个待排记
10、录序列分割成若干子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。技巧:子序列的构成不是简单地“逐段分割”,而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短(例如依次取5,3,1),直到dk1为止。优点:让关键字值小的元素能很快前移,且序列若基本有序时,再用直接插入排序处理,时间效率会高很多。,例:关键字序列 T=(49,38,65,97,76,13,27,49*,55,04),请写出希尔排序的具体实现过程。,21,38,初 态:,第1趟(dk=5),第2趟(dk=3),第3趟(dk=1),49,13,13,49,38,27,65,
11、49*,97,55,76,04,27,38,65,49*,97,55,13,55,76,04,55,13,27,04,27,04,49,49*,49,49*,76,38,76,65,65,97,97,13,27,04,49*,76,97,算法分析:开始时dk 的值较大,子序列中的对象较少,排序速度较快;随着排序进展,dk 值逐渐变小,子序列中对象个数逐渐变多,由于前面工作的基础,大多数对象已基本有序,所以排序速度仍然很快。,ri,时间效率:,22,空间效率:O(1)因为仅占用1个缓冲单元算法的稳定性:不稳定因为49*排序后却到了49的前面,O(n1.25)O(1.6n1.25)经验公式,23,
12、写出采用SHELL排序算法排序的每一趟的结果,并标出数据移动情况。(125,11,22,34,15,44,76,100,8,14,20,2,5),9.3 交换排序,24,两两比较待排序记录的关键码,如果发生逆序(即排列顺序与排序后的次序正好相反),则交换之,直到所有记录都排好序为止。,交换排序的主要算法有:1)冒泡排序 2)快速排序,交换排序的基本思想是:,1)冒泡排序,25,基本思路:每趟不断将记录两两比较,并按“前小后大”(或“前大后小”)规则交换。优点:每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素;一旦下趟没有交换发生,还可以提前结束排序。前提:顺序存储结构,例
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第十
链接地址:https://www.31ppt.com/p-5058968.html