第九章内部排序-数据结构DATASTRUCTURE.ppt
《第九章内部排序-数据结构DATASTRUCTURE.ppt》由会员分享,可在线阅读,更多相关《第九章内部排序-数据结构DATASTRUCTURE.ppt(49页珍藏版)》请在三一文库上搜索。
1、,数据结构 (DATA STRUCTURE),计算机科学与技术学院,2,第十章 排序,概述 插入排序 交换排序 选择排序 归并排序 基数排序,3,10.1 概述,1) 基本概念 排序:将一组记录按相应关键字的值递增或递减次序重新排列的过程。 关键字(key): 通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为关键字。 排序算法的稳定性: 如果在对象序列中有两个对象ri和rj,它们的关键字 ki = kj,且在排序之前,对象ri排在rj前面。如果在排序之后,对象ri仍在对象rj的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。,4
2、,2)排序方法的分类 根据排序时使用的存储器不同,分为: 内部排序: 在内存实现,数据对象全部存放在内存,无内外存数据交换;适合少量数据,速度快。 外部排序: 排序期间全部对象太多,不能同时存放在内存,必须根据排序过程的要求,不断在内外存之间移动;适合大量数据,速度慢。 按实现策略,内排序分五大类: 插入排序: 直接插入、shell排序 交换排序:冒泡、快速排序 选择排序:简单选择、树型选择、堆排序 归并排序: 基数排序:,5,按排序所需工作量,内排序分为: 简单排序方法: O(n2) 简单排序 先进排序方法: O(nlogn) 堆排序、快速排序 基数排序方法: O(dn) 基数排序 3)排序
3、算法的评价标准 时间复杂度: 排序的时间开销用算法执行中的数据比较次数与数据移动次数来衡量。 空间复杂度: 算法执行时所需的附加空间。 稳定性: 简单性:,6,4)本书中待排序数据表的数据类型描述 # define Maxsize 50 /待排序序列中记录的最大个数 待排序表中每个数据元素的数据类型定义 typedef struct int key; /表示排序关键字 elemtype otherinfo; /排序记录中的其他所有数据项 Snode; 待排序数据表的数据类型定义 typedef struct Snode RMaxsize+1; /存放待排序全体记录 int length; /排
4、序记录个数 SList;,7,10.2 插入排序 (Insert Sorting),1) 基本思想:将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。 将顺序存储的 n 个待排序记录划分为两个区间:一个有序区,一个无序区; 初始时:有序区为R1,无序区为R2.Rn,令 i 指向无序区中第一个记录,初值 i =2。 当in时,重复执行: 将当前无序区中第一个记录 Ri 插入到有序区的适当位置,使有序区变为:R1.Ri,无序区变为Ri+1.Rn。 当in时,有序区变为R1.Rn,排序结束。,10.2.1 直接插入排序,8,2)逐步求精:将 Ri 插入到有序区R1.Ri-1中
5、适当位置,即保持仍然有序。 具体做法:当插入第 i 个对象时,前面的 R1, R2.Ri-1已经排好序。这时,用 Ri 的关键字与Ri-1, Ri-2, 的关键字顺序进行比较,若比 Ri 的关键字大,就后移一个位置,如此重复,直到找到适当的插入位置,即将Ri插入。,9,排序过程演示:,10,3)算法实现: void InsertSort(SqList &L) for(i=2;i=L.length;i+) if(L.Ri.key L.Ri-1.key) /小于时,将Ri插入有序表 L.R0 =L.Ri; / R0作监测哨兵 for( j=i-1;L.R0.key L.Rj.key;j-) L.R
6、j+1=L.Rj; /*记录后移*/ L.Rj+1=L.R0; /*插入到正确位置*/ ,11,4) 算法分析,时间复杂度:设待排序对象个数为 n,则共需n-1 趟插入排序。每趟排序过程中关键字比较次数和对象移动次数与对象的初始排列有关。 最好情况(正序): 最坏情况(逆序): 空间复杂度:使用了一个临时空间 O(1) 稳定性:直接插入排序是一种稳定的排序方法。,12,10.2.2 希尔排序 (缩小增量法),1)基本思想:先将整个待排序记录序列分割成若干子序列分别进行直接插入排序,待整个序列“基本有序”时,再对全体记录进行一次直接插入排序。排序过程: 先将整个待排序记录以d1为步长分成若干子序
7、列,把所有相隔为d1的记录放在同一组内; 在每个分组内进行直接插入排序; 在将整个待排序记录序列以d2(d2d1n)为步长重新分组和在每组内进行直接插入排序; 重复上步,直至dt=1,即所有记录放进一个组中进行直接插入排序。,13,排序过程演示:,14,4) 算法分析,时间复杂度: Knuth利用大量的实验统计资料得出,当n 很大时,关键字平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 范围内。 空间复杂度:O(1) 稳定性:不稳定,15,10.3 交换排序 ( Exchange Sort ),交换排序的基本思想是两两比较待排序对象的关键字, 如果发生逆序, 则交换之,
8、 直到所有对象都排好序为止。,16,10.3.1 起泡排序 (Bubble Sort),1)起泡排序的基本方法: 将第一个记录的关键字与第二个记录的关键字进行比较,若为逆序r1.keyr2.key,则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作”为止,17,2)算法实现 void bubble_Sort (int a, int n ) /起泡排序算法
9、 for ( int i = n-1, change =1; i=1 /做“发生了交换”标志 ,18,排序过程演示:,19,3)算法分析,时间复杂度: 最好情况(正序):算法只执行一趟排序,做 n-1 次关键字比较,不移动对象。 最坏情况(逆序): 算法执行了n-1趟起泡,第 i 趟 (1 i n) 做了 n- i 次关键字比较,执行了n-i 次对象交换。 总的关键字比较次数: 总的对象移动次数为: 空间复杂度:O(1) 稳定性:稳定,20,10.3.2 快速排序 (Quick Sort),1)基本思想:通过一趟排序,将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键
10、字小,则可分别对这两部分记录进行排序,以达到整个序列有序。,21,排序过程演示:,22,2)算法分析:,时间复杂度:平均时间复杂度是O(nlog2n)。实验结果表明:就平均计算时间而言,快速排序是我们所讨论所有内排序方法中最好的一个。 空间复杂度: 快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数。 最大递归调用层次数与递归树的深度一致,理想情况为 log2(n+1) 。因此,要求存储开销为 O(log2n)。最坏情况将达到O(n)。 稳定性:快速排序是一种不稳定的排序方法。,23,10.4 选择排序,基本思想: 每一趟排序 (如第 i 趟,i = 1, 2, , n-1) 在 n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九 内部 排序 数据结构 DATASTRUCTURE
链接地址:https://www.31doc.com/p-3322286.html