第九章内部排序-数据结构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

11、-i+1 个待排序对象中选出关键字最小的对象, 作为有序序列的第 i 个对象。 待第 n-1 趟排序后，待排序对象只剩下1个，就不用再选了。,24,1）基本思想：直接选择排序是一种简单的排序方法，它的基本步骤是： 把顺序存储的 n 个待排序的记录看成由一个有序区和一个无序区组成。初始时，有序区为空，无序区为 (R1,R2,Rn)； 在一趟选择排序中，从无序区选出一个关键字最小的记录，把它放到有序区的表尾； 经过 n-1 趟选择和插入后，n个记录变为递增有序。,10.4.1 直接选择排序,25,排序过程演示：,26,2）算法分析,时间复杂度： 记录移动次数 最好情况：0 最坏情况：3(n-1)

12、比较次数：直接选择排序的关键字比较次数与对象的初始排列无关。 第 i 趟选择具有最小关键字对象所需的比较次数总是 n-i次； 因此，总的关键字比较次数为: 空间复杂度：O(1) 稳定性：不稳定,27,10.4.2 树型选择排序,1）锦标赛排序 (Tournament Tree Sort) 它的思想与体育比赛时的淘汰赛类似。首先取得 n 个对象的关键字，进行两两比较，得到 n/2 个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来。然后对这 n/2 个对象再进行关键字的两两比较，如此重复，直到选出一个关键字最小的对象为止。 在图例中，最下面是对象排列的初始状态，相当于一棵满二叉树的叶结点

13、，它存放的是所有参加排序的对象的关键字。,28,如果 n 不是2的 k 次幂，则让叶结点数补足到满足 2k-1 n 2k 的2k个。叶结点上面一层的非叶结点是叶结点关键字两两比较的结果。最顶层是树的根。,29,10.4.3 堆排序,1）堆的定义：n个元素的序列(R1,R2,Rn),对应的关键字序列为(k1,k2,kn)，若此关键字序列满足下列关系，则称该元素序列为堆。,例 (96,83,27,38,11,9）,例 (13,38,27,50,76,65,49,97),可将堆序列看成完全二叉树，则堆顶 元素（完全二叉树的根）必为序列中 n个元素的最小值或最大值,30,堆排序在排序过程中，利用完全二

14、叉树双亲与孩子结点的关系来选择关键字最小（或最大）的记录。 基本思想： 将整个待排序记录分为有序区和无序区，初始时有序区为空，无序区为R1,R2,Rn 将无序区中记录看作一棵顺序存放的完全二叉树上的结点，对该完全二叉树按照堆定义要求进行调整，使关键字最小(大)的记录成为二叉树的根(存在R1中) 初建堆 将根结点中记录与无序区中最后一个结点交换，并将无序区中最后一个记录划入有序区内。 无序区中记录所构成的二叉树中，根结点的左、右子树均满足堆定义，故经过适当调整后可将无序区中记录重建成堆，无序区当前最小(大)成为根。 堆调整 重复上述过程，直到无序区为空(即执行n-1次)。,2) 堆排序基本思想,

15、31,堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“堆筛选”,32,第一个问题解决方法 方法：依次对无序序列的第 n/2， n/2-1, ,直至第1个元素作为根的子树进行堆调整。 因为无序序列所对应完全二叉树的最后一个非终端结点是第 n/2 个元素，所以筛选要从第 n/2 个元素开始向上进行。,4）初建堆 自下

16、而上,3）堆调整 自上而下,33,排序过程演示：,34,5) 算法分析,时间复杂度：O(nlog2n)。 空间复杂度：O(1) 稳定性：堆排序是一个不稳定的排序方法。,35,10.5 归并排序 (Merge Sort),1）归并：是将两个或两个以上的有序表合并成一个新的有序表。 两路归并 多路归并 归并方法：设两个有序表A和B 的对象个数(表长)分别为 al 和 bl，变量 i 和 j 分别是表A和表B的当前检测指针。设表C是归并后的新有序表，变量 k 是它的当前存放指针。,36,2）归并排序,归并排序算法就是利用两路归并过程进行排序。其基本思想是： 设初始待排序序列含有n个记录，则可看成n个

17、有序的子序列，每个子序列长度为1。把这n个记录两两二路归并，得到 n/2 个有序子序列，每个子序列的长度为2或1(n为奇数)。一趟归并排序 再对n/2个有序子序列进行两两二路归并，如此重复，直至得到一个长度为n的有序序列为止。,37,例,初始关键字： 49 38 65 97 76 13 27,一趟归并后： 38 49 65 97 13 76 27,二趟归并后： 38 49 65 97 13 27 76,三趟归并后： 13 27 38 49 65 76 97,38,排序过程演示：,39,3）算法分析,时间复杂度：O(nlog2n) 空间复杂度：O(n) 归并排序占用附加存储较多，需要另外一个与原

18、待排序对象数组同样大小的辅助数组。这是这个算法的缺点。 稳定性：归并排序是一种稳定的排序方法。,40,10.6 基数排序 (分配排序),1）基本概念 基数：若任一记录的关键字 ki 可以看成由d个分量 ki1,ki2,kid 组成，且每个分量的取值范围相同：C1 kij Crd (1 j d)，则称rd为基数。 十进制数 rd=10 C1=0, C10=9 小写字母 rd=26 C1=a, C10=z 基数排序是采用“分配”与“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。,41,多关键字排序 以扑克牌排序为例。每张扑克牌有两个“关键字”：花色和面值。其有序关系为： 花

19、色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 如果我们把所有扑克牌排成以下次序： 2, , A, 2, , A, 2, , A, 2, , A 这就是多关键字排序。排序后形成的有序序列叫做词典有序序列。,2）基数排序,42,对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。 一般情况下，假定一个序列有n 个对象 R1, R2, , Rn ，且每个对象Ri 中含有 d 个关键字 如果对于序列中任意两个对象 Ri 和 Rj ( 0 i j n-1 ) 都满足： 则称序列对关键字 (K1, K2, , Kd) 有序。其中，K1 称为最高

20、位关键字，Kd 称为最低位关键字。,43,设置 rd 个箱子 首先按 分量的取值，将记录“分配”到不同箱子中去。然后扫描n 个纪录，按箱子的序号依次将各非空箱子中的记录“收集”起来，这样所有对象按取值 排序完成。一趟箱排序 依次按 Kid-1, Kid-2, , Ki1 的值重复上步，直到最后一趟对Ki1 “分配”、“收集” 完成后，所有对象就按其关键字的值从小到大排好序了。,基数排序基本思想,44,3）算法分析,时间复杂度：若每个关键字有d 位，需要重复执行d 趟“分配”与“收集”。每趟对 n 个对象进行“分配”，对rd个箱子进行“收集”。总时间复杂度为O ( d ( n+rd ) )。 若

21、基数rd 相同，对于对象个数较多而关键字位数较少的情况，使用链式基数排序较好。 空间复杂度：基数排序需要增加n+2rd个附加链接指针。O(n+2rd) 稳定性：基数排序是稳定的排序方法。,45,10.7 各种排序方法的比较,46,本章小结 需要复习的知识点,排序的基本概念 排序的基本概念 关键字、初始关键字排列 关键字比较次数、数据移动次数 稳定性 插入排序 直接插入排序、Shell排序的过程 直接插入排序的算法 排序的性能分析 当待排序的关键字序列已经基本有序时，用直接插入排序最快,47,选择排序 直接选择排序、堆排序的过程 直接选择排序的算法 性能分析 用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，不是顺次后移。这导致方法不稳定。 在堆排序中将待排序的数据组织成完全二叉树的顺序存储。,48,交换排序 用事例表明起泡排序和快速排序的过程 起泡排序算法，快速排序的递归算法和非递归算法 二路归并排序 二路归并排序的过程 二路归并排序的非递归算法 该算法的性能分析 基数排序 基数排序的思想、方法,49,谢谢大家！,