数据结构教学课件：第10章_排序A

1、1数据结构课程的内容数据结构课程的内容210.1 10.1 概述概述10.2 10.2 插入排序插入排序10.3 10.3 交换排序交换排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.6 10.6 基数排序基数排序10.1 10.6 10.8 10.25 10.4210.1 10.6 10.8 10.25 10.42 31. 1. 什么是排序？什么是排序？ 将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来。顺次排列起来。2. 2. 排序的目的是什么？排序的目的是什么？存放在数据表中存放在数据表中按关键字排序按关键字排序3.3.排序算

2、法的好坏如何衡量？排序算法的好坏如何衡量？ 时间效率时间效率排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比较次数） 空间效率空间效率占内存辅助空间的大占内存辅助空间的大小小 稳定性稳定性若两个记录若两个记录A A和和B B的关键字值相等，但排序后的关键字值相等，但排序后A A、B B的的先后次序保持不变，则称这种排序算法是稳定的。先后次序保持不变，则称这种排序算法是稳定的。 便于查找！便于查找！稳定排序与不稳定排序稳定排序与不稳定排序假设假设 Ki = Kj ，且排序前序列中，且排序前序列中 Ri 领先于领先于 Rj稳定排序稳定排序：若在排序后的序列中若在排序后的序列中

3、Ri 仍领先于仍领先于 Rj ，则称排序方法是，则称排序方法是稳定的稳定的。不稳定排序不稳定排序：若在排序后的序列中若在排序后的序列中 Rj 领先于领先于 Ri ，则称排序方法是，则称排序方法是不稳定的不稳定的。例，例，序列序列 3 15 8 8 6 9若排序后得若排序后得 3 6 8 8 9 15若排序后得若排序后得 3 6 8 8 9 15454. 4. 什么叫内部排序？什么叫外部排序？什么叫内部排序？什么叫外部排序？ 若待排序记录都在内存中，称为内部排序；若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则若待排序记录一部分在内存，一部分在外存，则称为外部排序

4、。称为外部排序。注：注：外部排序时，要将数据分批调入内存来排序，中外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多间结果还要及时放入外存，显然外部排序要复杂得多。 5.5.待排序记录在内存中怎样存储和处理？待排序记录在内存中怎样存储和处理？ 顺序顺序排序排序排序时直接移动记录；排序时直接移动记录； 链表链表排序排序排序时只移动指针排序时只移动指针； 地址地址排序排序排序时先移动地址，最后再移动记录。排序时先移动地址，最后再移动记录。注：地址排序注：地址排序中可以增设一维数组来专门存放记录中可以增设一维数组来专门存放记录的地址。的地址。6注：注：大多数排序

5、算法都是针对顺序表结构的大多数排序算法都是针对顺序表结构的( (便于直接移动元素便于直接移动元素) )6. 6. 顺序存储（顺序表）的抽象数据类型如何表示？顺序存储（顺序表）的抽象数据类型如何表示？Typedef struct /定义每个记录定义每个记录（数据元素）的结构（数据元素）的结构 KeyType key ; /关键字关键字 InfoType otherinfo; /其它数据项其它数据项RecordType，node ; /例如例如node.keynode.key表示其中一个分量表示其中一个分量Typedef struct /定义顺序表定义顺序表L L的结构的结构 RecordType

6、 r MAXSIZE +1 ; /存储顺序表的向量存储顺序表的向量 /r0/r0一般作哨兵或缓冲区一般作哨兵或缓冲区 int length ; /顺序表的长度顺序表的长度SqList ,L; /例如例如L.rL.r或或L.lengthL.length表示其中一个分量表示其中一个分量# define MAXSIZE 20 /设记录数不超过设记录数不超过2020个个typedef int KeyType ; /设关键字为整型量（设关键字为整型量（intint型）型）若若r r数组是表数组是表L L中的一个分量且为中的一个分量且为nodenode类型，类型，则则r r中某元素的中某元素的keykey

7、分量表示为：分量表示为：ri.keyri.key77. 内部排序的算法有哪些？内部排序的算法有哪些？按排序的规则不同，可分为按排序的规则不同，可分为5类：类：v插入排序插入排序v交换排序交换排序v选择排序选择排序v归并排序归并排序v基数排序基数排序d关键字的位数关键字的位数(长度长度)按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3类：类：v简单的排序算法：时间效率低，简单的排序算法：时间效率低，O(n2)v先进的排序算法先进的排序算法: 时间效率高，时间效率高，O( nlog2n )v基基 数数 排排 序序 算法：时间效率高，算法：时间效率高，O( dn)8 1) 直接

8、插入排序直接插入排序 2) 折半插入排序折半插入排序 3）2-路插入排序路插入排序 4) 表插入排序表插入排序 5) 希尔排序希尔排序小改进小改进大改进大改进9新元素插入到哪里？新元素插入到哪里？例例1 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，3

9、1】, 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】 在已形成的在已形成的有序表中有序表中线性查找线性查找，并在，并在适当位置插入，把原来位置上的元素向后适当位置插入，把原来位置上的元素向后顺移顺移。最简单的排序法！最简单的排序法！10void InsertSort ( SqList &L ) /对顺序表对顺序表L作直接插入排序作直接插入排序 for ( i = 2; i =L.length; + i ) /直接在原始无序表直接在原始无序表L中排序中排序

10、 if (L.ri.key L.ri-1.key) /若若L.ri较小则插入有序子表内较小则插入有序子表内 L.r0= L.ri; /复制为哨兵复制为哨兵/只要子表元素比哨兵大就不断后移直到子表元素小于哨兵只要子表元素比哨兵大就不断后移直到子表元素小于哨兵for ( j=i-1; L.r0.key L.rj.key; -j ) L.rj+1= L.rj; /哨兵值送入当前要插入的位置（包括插入到表首）哨兵值送入当前要插入的位置（包括插入到表首）L.rj+1= L.r0; /if/ InsertSort （参见教材（参见教材P265P265）11例例1 1：关键字序列关键字序列T= （21，25

11、，49，25*，16，08），），请写出直接插入排序的具体实现过程。请写出直接插入排序的具体实现过程。* *表示后一个表示后一个25250 1 2 3 4 5 6252525* * *161616080808解：解：假设该序列已存入一维数组假设该序列已存入一维数组r7r7中，将中，将r0r0作为哨兵作为哨兵（TempTemp）。则程序执行过程为：）。则程序执行过程为：初态：初态：时间效率：时间效率： 因为在最坏情况下，所有元素的比较次数总和为因为在最坏情况下，所有元素的比较次数总和为（0 01 1n-1)O(nn-1)O(n2 2) )。其他情况下也要考虑。其他情况下也要考虑移动元素的次数。移

12、动元素的次数。 故时间复杂度为故时间复杂度为O(nO(n2 2) ) 空间效率：空间效率：仅占用仅占用1 1个缓冲单元个缓冲单元算法的稳定性：算法的稳定性：因为因为2525* *排序后仍然在排序后仍然在2525的后面的后面12优点：优点：比较次数大大减少，全部元素比较次数仅为比较次数大大减少，全部元素比较次数仅为O O( (n nloglog2 2n)n)。时间效率：时间效率：虽然比较次数大大减少，可惜移动次数并未减少，虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为所以排序效率仍为O(nO(n2 2) ) 。空间效率：空间效率：仍为仍为 O O（1 1）稳稳 定定 性：性： 稳

13、定稳定一个容易想到的改进方法：一个容易想到的改进方法： 既然子表有序且为顺序存储结构，既然子表有序且为顺序存储结构，则插入时采用则插入时采用折半查找折半查找可加速可加速。13这是对折半插入排序的一种改进，其这是对折半插入排序的一种改进，其目的目的是减少排序过程是减少排序过程中的移动次数。中的移动次数。代价：代价：需要增加需要增加n n个记录的辅助空间。增开辅助数组个记录的辅助空间。增开辅助数组d, d, 大大小与小与r r相同。相同。思路：思路：中值中值实现：实现：14例：待排序列例：待排序列T=(49，38，65，97, 76, 13, 27, 49*）finalfinalfirstfirs

14、tfirstfirstfinalfinalfirstfirstfirstfirstfinalfinalfinalfinalfinalfinalfirstfirstfirstfirstfinalfinalfirstfirstfinalfinalfirstfirstfinalfinal15讨论：讨论：若记录是若记录是链表结构链表结构，用直接插入排序行否？，用直接插入排序行否？答：答：行，而且无需移动元素，时间效率更高！行，而且无需移动元素，时间效率更高！16表插入排序算法分析：表插入排序算法分析： 无需移动记录，只需修改无需移动记录，只需修改2n次指针值。但由于比较次指针值。但由于比较次数没有减少

15、，故次数没有减少，故时间效率仍为时间效率仍为O(n2) 。 空间效率肯定低空间效率肯定低，因为增开了指针分量（但在运算，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元）。过程中没有用到更多的辅助单元）。 稳定性：稳定性：稳定稳定。注：注：此算法得到的只是一个有序链表，查找记录时只能此算法得到的只是一个有序链表，查找记录时只能满足顺序查找方式。满足顺序查找方式。改进：改进：可以根据表中指针线索，很快对所有记录重排，可以根据表中指针线索，很快对所有记录重排，形成形成真正的有序表（顺序存储方式），从而能满足真正的有序表（顺序存储方式），从而能满足折半查找方式。折半查找方式。具体实现见教材具

16、体实现见教材P269。17子序列的构成不是简单地子序列的构成不是简单地“逐段分割逐段分割”，而是将，而是将相隔某个增量相隔某个增量dkdk的记录组成一个子序列的记录组成一个子序列, ,让增量让增量dkdk逐趟缩逐趟缩短（例如依次取短（例如依次取5,3,15,3,1），直到），直到dkdk1 1为止。为止。1838例：例：关键字序列关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），），请写出希尔排序的具体实现过程。请写出希尔排序的具体实现过程。0123456789104938659776132749*5504初态：初态：第第1趟趟 (dk=5)第第2趟趟

17、 (dk=3)第第3趟趟 (dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 算法分析：算法分析：开始时开始时dk 的值较大，子序列中的对象较少，排序速度的值较大，子序列中的对象较少，排序速度较快；随着排序进展，较快；随着排序进展，dk 值逐渐变小，子序列中对象个数值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，逐渐变多，由于前面工作的基础，大多数对

18、象已基本有序，所以排序速度仍然很快。所以排序速度仍然很快。19时间效率：时间效率：空间效率：空间效率：因为仅占用因为仅占用1 1个缓冲单元个缓冲单元算法的稳定性：算法的稳定性：因为因为4949* *排序后却到了排序后却到了4949的前面的前面由经验公式得到由经验公式得到练练1. 欲将序列（欲将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码）中的关键码按字母升序重排，则初始步长为按字母升序重排，则初始步长为4的希尔排序一趟的结果是？的希尔排序一趟的结果是？答：答：原始序列：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X s

19、hellshell一趟后：一趟后：课堂练习：课堂练习：P,Q,R,A,D,H,C,F,M,S,X ,Y20原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，9

20、37937，863863，742742，751751，076076，438438256256，301301，694694，076076，937937，863863，742742，751751，129129，438438256256，301301，694694，076076，438438，863863，742742，751751，129129，937937第第1趟趟dk=5dk=5第第2趟趟dk=3dk=3第第3趟趟dk=1dk=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，

21、694694，076076，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，129129，256256，301301，438438，694694，742742，751751，863863，937937练练2. 以关键字序列（以关键字序列（256，