数据结构第十章

1、排序：排序：将一个数据元素（或记录）的任意序列，重新将一个数据元素（或记录）的任意序列，重新 排列成一个按关键字有序的序列排列成一个按关键字有序的序列内部排序：内部排序：将待排记录存放在计算机随机存储器重进将待排记录存放在计算机随机存储器重进 行的排序过程。行的排序过程。外部排序：外部排序：由于待排记录的数量很大，以至内存一次由于待排记录的数量很大，以至内存一次 不能容纳全部记录，在排序过程中尚需要不能容纳全部记录，在排序过程中尚需要 对外存进行访问的排序过程。对外存进行访问的排序过程。1第十章第十章 内部排序内部排序210.1 10.1 概述概述10.2 10.2 插入排序插入排序10.3

2、10.3 交换排序交换排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.6 10.6 基数排序基数排序310.1 10.1 概述概述1 1、排序是计算机内经常进行的一种操作，其目的是将一、排序是计算机内经常进行的一种操作，其目的是将一组组“无序无序”的记录序列调整为的记录序列调整为“按关键字有序按关键字有序”的记录序的记录序列。列。52，49，80，36，14，58，61，23，97，7514，23，36，49，52，58，61，75，80，97一般情况下，一般情况下，假设含假设含n n个记录的序列为个记录的序列为R1R1，R2R2，RnRn其相应的关键字序列为

3、其相应的关键字序列为 K1K1，K2K2，KnKn这些关键字相互之间可以进行比较，这些关键字相互之间可以进行比较，即在它们之间存在这样一个关系：即在它们之间存在这样一个关系：Kp1=Kp2=Kp1=Kp2=Kpn=Kpn按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为Rp1,Rp2,Rp1,Rp2,Rpn,Rpn的操作称作排序的操作称作排序42 2、关键字、关键字数据对象有多个属性域，即多个数据成员组成，其中有一个数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可以用来区分对象，作为排序依据，称为属性域可以用来区分对象，作为排序依据，称为关键字关键字。关键字与

4、记录之间是一对一的关系关键字与记录之间是一对一的关系 称称主关键字主关键字关键字与记录之间是一对多的关系关键字与记录之间是一对多的关系 称称次关键字次关键字53、排序的目的是什么？、排序的目的是什么？ 便于查找便于查找4、排序算法的好坏如何衡量？、排序算法的好坏如何衡量？v 时间效率时间效率 排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比较次数）v 空间效率空间效率 占内存辅助空间的大小占内存辅助空间的大小v 稳定性稳定性 若两个记录若两个记录A和和B的关键字相等，但排序后的关键字相等，但排序后A， B的先后次序保持不变，则称这种排序算法是稳定的。的先后次序保持不变，则称

5、这种排序算法是稳定的。65 5、什么叫内部排序？什么叫外部排序、什么叫内部排序？什么叫外部排序 若待排序记录都在内存中，称内部排序若待排序记录都在内存中，称内部排序 若待排序记录一部分在内存，一部分在外存，则称为外若待排序记录一部分在内存，一部分在外存，则称为外部排序。部排序。注：外部排序时，要将数据分批掉入内存来排序，中间结果注：外部排序时，要将数据分批掉入内存来排序，中间结果还要及时放入内存，显然外部排序要复杂得的多。还要及时放入内存，显然外部排序要复杂得的多。76 6、待排序记录在内存中怎样存储和处理、待排序记录在内存中怎样存储和处理（1 1） 顺序排序顺序排序 排序时直接移动记录；排序

6、时直接移动记录；（2 2）链表排序）链表排序 排序时只移动指针；排序时只移动指针；（3 3）地址排序）地址排序 排序时先移动地址，最后再移动记录。排序时先移动地址，最后再移动记录。注：地址排序中可以增设一维数组来专门存放记录的地址。注：地址排序中可以增设一维数组来专门存放记录的地址。8注：注：大多数排序算法都是针对顺序表结构的大多数排序算法都是针对顺序表结构的( (便于直接移动元素便于直接移动元素) )Typedef struct /定义每个记录（数据元素）的结构定义每个记录（数据元素）的结构 KeyType key ; /关键字关键字 InfoType otherinfo; /其它数据项其它

7、数据项RecordType ;Typedef struct /定义顺序表的结构定义顺序表的结构 RecordType r MAXSIZE +1 ; /存储顺序表的向量存储顺序表的向量 /r0/r0一般作哨兵或缓冲区一般作哨兵或缓冲区 int length ; /顺序表的长度顺序表的长度SqList ;# define MAXSIZE 20 /设记录不超过设记录不超过2020个个typedef int KeyType ; /设关键字为整型量（设关键字为整型量（intint型）型）9按排序的规则不同，可分为按排序的规则不同，可分为5类：类：插入排序插入排序交换排序（重点是快速排序）交换排序（重点是

8、快速排序）选择排序选择排序归并排序归并排序基数排序基数排序d关键字的位数关键字的位数(长度长度)按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3类：类：简单的排序算法：时间效率低，简单的排序算法：时间效率低，O(n2)先进的排序算法先进的排序算法: 时间效率高，时间效率高，O( nlog2n )基数排序算算法：时间效率高，基数排序算算法：时间效率高，O( dn)10插入排序的基本思想是：插入排序的基本思想是：插入排序有多种具体实现算法：插入排序有多种具体实现算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 3) 表插入排序表插入排序 4) 希尔排序希

9、尔排序 每步将一个待排序的对象，每步将一个待排序的对象，按其关键码大小，按其关键码大小，插入到前面插入到前面已经排好序的一组对已经排好序的一组对象的适当位置象的适当位置上上，直到对象全部插入为止。，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。11基本思想： 假定前面m 个元素已经排序； 取第(m+1) 个元素，插入到前面的适当位置； 一直重复，到m=n 为止。 （初始情况下，m = 1）12例例1 1：关键字序列关键字序列T=（13，6，3，31，9，27，5，11），）， 请写出直接插入排序的中间过程序列。请写

10、出直接插入排序的中间过程序列。【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【3, 5, 6, 9, 11，13，27, 31】 13void InsertSort(SqList &L) / 对顺序表L作直接插入排序。 int i, j; for (i=2; i

11、=L.length; +i) if (LT(L.ri.key, L.ri-1.key) / 时，需将L.ri插入有序子表 L.r0 = L.ri; / 复制为哨兵 for (j=i-2; LT(L.r0.key, L.rj.key); -j) L.rj+1 = L.rj; / 记录后移 L.rj+1 = L.r0; / 插入到正确位置 / InsertSort14* *表示后一个表示后一个25250 1 2 3 4 5 6252525494949252525* * *161616080808解：解：假设该序列已存入一维数组假设该序列已存入一维数组V7V7中，将中，将V0V0作为缓冲或作为缓冲或

12、暂存单元（暂存单元（TempTemp）。则程序执行过程为：）。则程序执行过程为：初态：初态：时间效率：时间效率： 因为在最坏情况下，所有元素的比较因为在最坏情况下，所有元素的比较次数总和为（次数总和为（0 02 2n)O(nn)O(n2 2) )。其他情况下。其他情况下还要加上移动元素的次数。还要加上移动元素的次数。 空间效率：空间效率：因为仅占用因为仅占用1 1个缓冲单元个缓冲单元算法的稳定性：算法的稳定性：因为因为2525* *排序后仍然在排序后仍然在2525的后面。的后面。特点：因为特点：因为R1R1i-1i-1是一个按关键字有序的有序是一个按关键字有序的有序序列，则可以利用折半查找实现

13、在序列，则可以利用折半查找实现在R1R1i-1i-1中查中查找找RiRi的插入位置，如此实现的插入排序为折半插的插入位置，如此实现的插入排序为折半插入排序。入排序。限制：必须采用顺序存储方式。限制：必须采用顺序存储方式。1516例：有例：有6个记录，前个记录，前5 个已排序的基础上，对第个已排序的基础上，对第6个记录排序。个记录排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 (high36 )( 42n/2时，表示结点时，

14、表示结点i为叶子结点。为叶子结点。44234561（大根堆）（大根堆）2345617有序列有序列T1=（08, 25, 49, 46, 58, 67）和序列）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判断它们是否判断它们是否 “堆堆”？（小根堆）（小根堆）（小顶堆）（小顶堆） （最小堆）（最小堆）（大顶堆）（大顶堆）（最大堆）（最大堆）45非终端结点非终端结点123456例：例：关键字序列关键字序列T= (21，25，49，25*，16，08），请建），请建大根堆大根堆。解：解：为便于理解，先将原始序列画成完全二叉树的形式：为便于理解，先将原始序列画成完全二叉树的形

15、式：注：注：终端结点（即叶子）没有任何子女，无需单独调整。终端结点（即叶子）没有任何子女，无需单独调整。 49大于大于08，不必调整；，不必调整； 25大于大于25*和和16，也不必调整；，也不必调整； 21小于小于25和和49，要调整！，要调整！而且而且21还应当向下比较！还应当向下比较！46471234561365424812345613654249123456136542501234561365425112345613654252归并排序的基本思想是：归并排序的基本思想是：将两个（或以上）的有序将两个（或以上）的有序表组成新的有序表。表组成新的有序表。更实际的意义：更实际的意义：可以把一

16、个长度为可以把一个长度为n 的无序序列看成是的无序序列看成是 n 个长度为个长度为 1 的有序子序列的有序子序列 ，首先做两两归并，得到，首先做两两归并，得到 n / 2 个长度为个长度为 2 的子序列的子序列 ；再做两两归并，；再做两两归并，如此重复，直，如此重复，直到最后得到一个长度为到最后得到一个长度为 n 的有序序列。的有序序列。例：例：关键字序列关键字序列T= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实），请给出归并排序的具体实现过程。现过程。53然后对这个有序表进行归并，如何进行？然后对这个有序表进行归并，如何进行？可以进行两两归

17、并，设置两个指针，分别指向可以进行两两归并，设置两个指针，分别指向2121，和，和2525，然，然后把后把2121与与2525进行比较，如果进行比较，如果2121较小则把较小则把2121调出来，指针往后调出来，指针往后移，把移，把2525与与2525* *进行比较，进行比较，2525较小，调出来，指针后移至到较小，调出来，指针后移至到结束，然后把第二部分的数据调出来，则排序完成，然后再结束，然后把第二部分的数据调出来，则排序完成，然后再次进行归并，直到所有的数排序成功为止。次进行归并，直到所有的数排序成功为止。54各种内部排序方法的比较各种内部排序方法的比较 (教材教材P289）55快速排序快

18、速排序O(nlgn )O(nlgn) O(n2) O(lgn) 不稳定不稳定 堆排序堆排序 O(nlgn )O(nlgn ) O(nlgn) O(1）不稳定不稳定 归并排序归并排序 O(nlgn ) O(nlgn ) O(nlgn) O(n）稳定稳定基数排序基数排序O(d(n+rd) O(d(n+rd) O(d(n+rd) O(rd)稳定稳定 简单选择简单选择 O(n2) O(n2) O(n2) O(1） 不稳定不稳定 直接插入直接插入 O(n) O(n2) O(n2) O(1）稳定稳定 折半插入折半插入O(nlgn )O(nlgn )O(nlgn )O(1）稳定稳定冒泡冒泡 O(n) O(n

19、2) O(n2) O(1）稳定稳定 7. 内部排序的算法有哪些？56按排序的规则不同，可分为按排序的规则不同，可分为5类：类：插入排序插入排序交换排序（重点是快速排序）交换排序（重点是快速排序）选择排序选择排序归并排序归并排序基数排序基数排序d关键字的位数关键字的位数(长度长度)按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3类：类：简单的排序算法：时间效率低，简单的排序算法：时间效率低，O(n2)先进的排序算法先进的排序算法: 时间效率高，时间效率高，O( nlog2n )基数排序算算法：时间效率高，基数排序算算法：时间效率高，O( dn)57例：有例：有6个记录，前个记录，前5 个已排序的基础上，对第个已排序的基础上，对第6个记录排序。个记录排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42