数据结构第十章内排序

1、第十章第十章 排序排序 10.1 插入排序插入排序 10.2 快速排序快速排序 10.3 选择排序选择排序 10.4 归并排序归并排序 10.5 基数排序基数排序 10.6 各种内部排序方法的比较讨论各种内部排序方法的比较讨论 10.1 概述概述1、排序、排序l排序排序是计算机程序设计中的一种重要操作，它的功能是将一个是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有数据元素（或记录）的任意序列，重新排列成一个按关键字有序序列。序序列。l其相应的关键字序列为其相应的关键字序列为lK1，K2，K n，l假设含假设含n个记录的序列为：个记录的序

2、列为：lR1，R2，R n (9.1) l需确定需确定1，2， n的一种排列的一种排列P1，P2，P n，使其相，使其相应的关键字满足如下的非递减（或非递增）关系应的关键字满足如下的非递减（或非递增）关系KP1 KP2 KP n，即使（，即使（9.1）式的序列成为一个按关键字）式的序列成为一个按关键字有序的序列有序的序列RP1，RP2，RPn，这样一种操作称为，这样一种操作称为排序排序。2、稳定的、非稳定的、稳定的、非稳定的3、内部排序、外部排序、内部排序、外部排序l假设假设Ki=Kj（1 i n，1 j n，i j）且在排序前的序列中）且在排序前的序列中Ri领先领先Rj（即（即ij）。）。l

3、内部排序：内部排序：指的是待排序记录存放在计算机随机存储器中指的是待排序记录存放在计算机随机存储器中进行的排序过程。进行的排序过程。l外部排序：外部排序：指的是排序记录的数量很大，以致内存一次指的是排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。的排序过程。l反之，若可能使排序后的序列中反之，若可能使排序后的序列中Rj领先于领先于Ri，则称所用的，则称所用的排序方法是排序方法是不稳定的不稳定的。l若在排序后的序列中若在排序后的序列中Ri仍领先仍领先Rj，则称所用的排序方法是，则称所用的排序方法是稳稳定的

4、定的；4、排序方法、排序方法l插入排序插入排序：直接插入排序、折半插入排序、希尔排序：直接插入排序、折半插入排序、希尔排序l交换排序交换排序：冒泡排序、快速排序：冒泡排序、快速排序l选择排序选择排序：简单选择排序、树形选择排序、堆排序：简单选择排序、树形选择排序、堆排序l归并排序归并排序：2-路归并排序路归并排序l基数排序基数排序: 多关键字排序、链式基数排序多关键字排序、链式基数排序l如果按内部排序过程中所需的工作量来区分，可分为：如果按内部排序过程中所需的工作量来区分，可分为：（1）简单排序）简单排序，其时间复杂度为，其时间复杂度为T(n)=O(n)（2）先进的排序方法）先进的排序方法，其

5、时间复杂度为其时间复杂度为T(n)=O(nlogn)（3）基数排序）基数排序，其时间复杂度为其时间复杂度为T(n)=O(d.n) 5、排序基本操作、排序基本操作 ：（1）比较两个关键字大小；）比较两个关键字大小；（2）将记录从一个位置移动到另一个位置。）将记录从一个位置移动到另一个位置。l插入排序的基本思想是插入排序的基本思想是：每一步将一个待排序的记录，按：每一步将一个待排序的记录，按其主关键字的大小插入到前面已经排序的文件中适当位置其主关键字的大小插入到前面已经排序的文件中适当位置上，直至全部插完为止。上，直至全部插完为止。 10.1 插入排序插入排序1、直接插入排序、直接插入排序 l直接

6、插入排序是一种最简单的排序方法，它的基本操作直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的有序表中，从而得到一个是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增加新的、记录数增加1的有序表。的有序表。l例如：已知待排序的一组记录的初始排列如下所示：例如：已知待排序的一组记录的初始排列如下所示：R（49），），R（38），），R（65），），R（97），），R（76），），R（13），），R（27），），R（19）。）。1、直接插入排序、直接插入排序l假设在排序过程中，前四个记录已按关键字递增的次序，重假设在排序过程中，前四个记录已按关键字递增的次序，重

7、新排列，构成一个含新排列，构成一个含4个记录的有序序列个记录的有序序列:l现要将第现要将第5个（关键字为个（关键字为76）的记录插入上述序列，可以得）的记录插入上述序列，可以得到一个新的含到一个新的含5个记录的有序序列，个记录的有序序列，则首先要找到插入的位则首先要找到插入的位置，然后进行插入。置，然后进行插入。l假设从假设从R（97）起向左进行顺序查找，由于）起向左进行顺序查找，由于65 76 97，则，则R（76）应插入在）应插入在R（65）和）和R（97）之间，从而得到下列新）之间，从而得到下列新的有序序列的有序序列:lR（38），），R（49），），R（65），），R（76），），R（

8、97） (9.4) l称从式（称从式（9.3）到式（）到式（9.4）的过程为一趟直接插入排序。）的过程为一趟直接插入排序。l38，49，65，97 (9.3)l一般情况下，第一般情况下，第i趟直接插入排序的操作为：趟直接插入排序的操作为：l在含有在含有i-1个记录的有序子序列个记录的有序子序列r1i-1中插入一个记录中插入一个记录ri后，变成含有后，变成含有i个记录的有序子序序列个记录的有序子序序列r1i；l并且，和顺序查找类似，为了在查找插入位置的过程中避并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在免数组下标出界，在r0处设置监视哨。处设置监视哨。l整个排序过程为进行

9、整个排序过程为进行n-1趟插入，即：先将序列中的第一个记趟插入，即：先将序列中的第一个记录看成是一个有序序列的子序，然后从第录看成是一个有序序列的子序，然后从第2个记录起逐个进行个记录起逐个进行插入直至整个序列变成按关键字非递减有序序列为止。插入直至整个序列变成按关键字非递减有序序列为止。l在自在自i-1起往前搜索的过程中，可以同时后移记录。起往前搜索的过程中，可以同时后移记录。1、直接插入排序、直接插入排序例例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49

10、65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：排序结果：1、直接插入排序、直接插入排序l当待排序列中记录按关键字非递减有序排列当待排序列中记录按关键字非递减有序排列(正序）所需进行正序）所需进行关键字间比较的次数达最小值关键字间比较的次数达最小值112nni2)1)(4()1(2nnini2) 1)(2(2nninil记录移动的次数也达

11、到最大值记录移动的次数也达到最大值l当待排序列中记录按关键字非递增有序排列（逆序）所需当待排序列中记录按关键字非递增有序排列（逆序）所需进行关键字间比较的次数达最大值进行关键字间比较的次数达最大值l我们可取上述最小值和最大值的平均值，作为直接插入排序时我们可取上述最小值和最大值的平均值，作为直接插入排序时所需进行关键字间的比较次数和移动记录的次数，约为所需进行关键字间的比较次数和移动记录的次数，约为n2/4。由此，直接插入排序的时间复杂度为由此，直接插入排序的时间复杂度为O（ n2）。）。l记录不需要移动。记录不需要移动。1、直接插入排序、直接插入排序2、其它插入排序、其它插入排序（1）折半插

12、入排序）折半插入排序l由于插入排序的基本操作是在一个有序表中进行查找和插由于插入排序的基本操作是在一个有序表中进行查找和插入，则从上章的讨论可知，这个入，则从上章的讨论可知，这个“查找查找”操作可利用操作可利用“折半折半查找查找”来实现，来实现，由此进行的插入排序称之为折半插入排序由此进行的插入排序称之为折半插入排序。l直接插入排序的基本操作是向有序表中插入一个记录，平均情况直接插入排序的基本操作是向有序表中插入一个记录，平均情况下总比较次数约为下总比较次数约为n2/4。既然是在有序表中确定插入位置，可以。既然是在有序表中确定插入位置，可以不断二分有序表来确定插入位置，通过待插入记录与有序表居

13、中不断二分有序表来确定插入位置，通过待插入记录与有序表居中的记录按关键码比较，将有序表一分为二，下次比较在其中一个的记录按关键码比较，将有序表一分为二，下次比较在其中一个有序子表中进行，这样继续下去，直到要比较的子表中只有一个有序子表中进行，这样继续下去，直到要比较的子表中只有一个记录时，比较一次便确定了插入位置。记录时，比较一次便确定了插入位置。i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.i=8 20 (6 13 20 30 39 42 70 85 )l折

14、半插入排序折半插入排序i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sj 算法评价算法评价l折半插入排序所需附加存储空间和直接插入排序相同，从时折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍记录的移动次数不变。

15、因此，折半插入排序的时间复杂度仍为：为： O(n2) （2）2-路插入排序路插入排序 l2路插入排序是在折半排序的基础上再改进之，其目的是减路插入排序是在折半排序的基础上再改进之，其目的是减少排序过程中移动记录的次数，但为此需要少排序过程中移动记录的次数，但为此需要n个记录的辅助个记录的辅助空间。空间。 P267 时间复杂度：时间复杂度：T(n)=O(n) 空间复杂度：空间复杂度：S(n)=O(1)3、希尔排序、希尔排序l希尔排序又称希尔排序又称“缩小增量法缩小增量法” l基本思想基本思想：先将整个待排记录序列分割成若干子序列分：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个

16、序列中的记录别进行直接插入排序，待整个序列中的记录“基本有基本有序序”时，再对全体记录进行一次直接插入排序。时，再对全体记录进行一次直接插入排序。l排序过程：排序过程：先取一个正整数先取一个正整数d1n，把全部记录分成，把全部记录分成d1个个组，所组，所有距离为有距离为d1倍数倍数的记录放一组，在各组内进行插入的记录放一组，在各组内进行插入排序；然后取排序；然后取d2r2.key，则将两个记录交换；，则将两个记录交换；l然后比较第二个记录与第三个记录的关键字；依次类推，直至然后比较第二个记录与第三个记录的关键字；依次类推，直至第第n-1个记录和第个记录和第n个记录的关键字比较为止。个记录的关键

17、字比较为止。l上述过程称作第一趟冒泡排序上述过程称作第一趟冒泡排序，其结果使得关键字最大的记录，其结果使得关键字最大的记录被安置到最后一个记录的位置上。被安置到最后一个记录的位置上。l然后进行第二趟冒泡排序，对前然后进行第二趟冒泡排序，对前n-1个记录进行同样操作，其结个记录进行同样操作，其结果是使关键字次大的记录被安置到第果是使关键字次大的记录被安置到第n-1个记录的位置上。个记录的位置上。l，重复上述过程，直到，重复上述过程，直到“在一趟排序过程中没有进行过交在一趟排序过程中没有进行过交换记录的操作换记录的操作”为止。为止。例例49 38 65 97 76 13 27 30初始关键字初始关

18、键字38 49 65 76 13 27 30 97第一趟第一趟38 49 65 13 27 30 76第二趟第二趟38 49 13 27 30 65第三趟第三趟38 13 27 30 49第四趟第四趟13 27 30 38第五趟第五趟13 27 30第六趟第六趟3849769713972797137676762730136527653065131349493049273827383038301、起泡排序、起泡排序算法描述与分析算法描述与分析l起泡排序的效率，若初始序列为起泡排序的效率，若初始序列为“正序正序”，则只需进，则只需进行一趟排序，在排序过程中进行行一趟排序，在排序过程中进行n-1次关

19、键字间的比次关键字间的比较；反之，若初序列较；反之，若初序列“逆序逆序”，则需进行，则需进行n-1趟排序，趟排序，需进行需进行 2)1()1(2nninil次比较。并作等数量级的记录移动，因此，总的时间次比较。并作等数量级的记录移动，因此，总的时间复杂度为复杂度为O（n2）。）。2、快速排序、快速排序2、快速排序、快速排序 l快速排序快速排序是对起泡排序的一种改进，是对起泡排序的一种改进，其基本思想是其基本思想是：通过一：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部的关键字均比

20、另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。分记录进行排序，以达到整个序列有序。l假设待排序的序列为假设待排序的序列为L.rs，L.rs+1，L.rt，首先任，首先任意选取一个记录（通常可选第一个记录意选取一个记录（通常可选第一个记录L.rs）作为）作为枢轴枢轴（或（或支点支点Pivot），然后按下述原则重新排列其余记录：将所有关），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。它大的记录都安置在它的位置之后。l由此，可以该由此，可以

21、该“枢轴枢轴”记录最后所落的位置最作分界线，将记录最后所落的位置最作分界线，将序列序列L.rs，L.rs+1，L.rt分割成两个子序列分割成两个子序列L.rs，L.rs+1，L.ri-1和和 L.ri+1，L.ri+2，L.rt，这个过程称作一趟快速排序这个过程称作一趟快速排序。l一趟快速排序的具体做法是一趟快速排序的具体做法是：对：对rst中记录进行一趟快中记录进行一趟快速排序，附设两个指针速排序，附设两个指针low和和high，它们的初值分别为，它们的初值分别为low和和high，设枢轴记录的关键字为，设枢轴记录的关键字为Pivotkey，l然后从然后从low所指位置起向后搜索找到第一个关

22、键字大于所指位置起向后搜索找到第一个关键字大于Pivotkey的记录和的记录和枢轴记录相互交换枢轴记录相互交换做，重复这两步直至做，重复这两步直至low=high。l首先从首先从high所指位置起向前搜索找到第一个关键字小于所指位置起向前搜索找到第一个关键字小于Pivotkey的记录和的记录和枢轴记录相互交换，枢轴记录相互交换，快速排序快速排序初始关键字：初始关键字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序：完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序：分别进行快速排序： ( 13) 27 (38) 49 (50

23、65) 76 (97)快速排序结束：快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij快速排序实例快速排序实例l通常，快速排序平均时间复杂度为通常，快速排序平均时间复杂度为O(nlogn)，但待排序记录的，但待排序记录的键值几乎已排序时，情况反而恶化，每一趟快速快速排序的基键值几乎已排序时，情况反而恶化，每一趟快速快速排序的基准记录位置就是第一个记录位置或最后一个记录位置。准记录位置就是第一个记录位置或最后一个记录位置。最坏情最坏情况下的时间复杂度为况下的时间复杂度为T(n)=O(n)。l快速排序的平均时间为快速排序的平均时间

24、为Tavg(n)=knlnn，其中，其中n为待排序序列记为待排序序列记录的个数，录的个数，k为某个常数，经验证明，在所有同数量级的此类为某个常数，经验证明，在所有同数量级的此类（先进的）排序方法中，快速排序的常数因子（先进的）排序方法中，快速排序的常数因子k最小。因此，最小。因此，就平均时间而言，快速排序是目前被认为是最好的一种内部排就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。序方法。l快速排序递归算法需要栈空间来实现递归，一般情况下需要的空快速排序递归算法需要栈空间来实现递归，一般情况下需要的空间为间为S(n)=O(log2n)，最坏情况下，需要的栈空间为，最坏情况下，需要

25、的栈空间为S(n)=O(n)。l快速排序方法是不稳定的快速排序方法是不稳定的。快速排序快速排序l选择排序的基本思想选择排序的基本思想：每一趟在：每一趟在n-i+1(i =1,2,n-1)个记录个记录中选取关键字最小的记录作为有序序列中第中选取关键字最小的记录作为有序序列中第i 个记录。个记录。 10.3 选择排序选择排序1、简单选择排序、简单选择排序l一趟简单选择排序的操作为：通过一趟简单选择排序的操作为：通过n-1次关键字的比较，从次关键字的比较，从n- i +1个记录中选择出关键字最小的记录，并和第个记录中选择出关键字最小的记录，并和第i（1 i n）个记录）个记录交换之。交换之。l再通过

26、再通过n-2次比较，从剩余的次比较，从剩余的n-1个记录中找出关键字次小个记录中找出关键字次小的记录，将它与第二个记录交换的记录，将它与第二个记录交换l重复上述操作，共进行重复上述操作，共进行n-1趟排序后，排序结束趟排序后，排序结束. 初始：初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟：一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 2

27、7 38 49 65 97 76 六趟：六趟： 13 27 38 49 65 76 97 排序结束：排序结束： 13 27 38 49 65 76 971、简单选择排序、简单选择排序 简单选择排序过程中，所需进行记录移动的操作次数较少，简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为其最小值为“0”，最大值为，最大值为3(n-1)。然而，无论记录的初始。然而，无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为排列如何，所需进行的关键字间的比较次数相同，均为(n(n-1)/2。因此，总的时间复杂度也是。因此，总的时间复杂度也是 O（n2）。）。算法描述与算法评价算法描述

28、与算法评价 选择排序的主要操作是进行关键字间的比较，因此改进简单选择排序的主要操作是进行关键字间的比较，因此改进简单选择排序应从如何减少选择排序应从如何减少“比较比较”出发考虑。显然，在出发考虑。显然，在n个关个关键字中选出最小值，至少进行键字中选出最小值，至少进行n-1次比较，然而，继续在剩次比较，然而，继续在剩余的余的n-1个关键字中选择小值就并非一定要进行个关键字中选择小值就并非一定要进行n-2次比较，次比较，若能利用前若能利用前n-1次比较所得信息，则可减少以后各趟选择排次比较所得信息，则可减少以后各趟选择排序中所用的比较次数。序中所用的比较次数。2、树形选择排序、树形选择排序l树形选

29、择排序，又称锦标赛排序树形选择排序，又称锦标赛排序，是一种按照锦标赛，是一种按照锦标赛的思想进行选择排序的方法。的思想进行选择排序的方法。l首先对首先对n个记录的关键字进行两两比较，然后在其中个记录的关键字进行两两比较，然后在其中 n/2 个较小者之间再进行两两比较，如此重复，直至选出最小个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。关键字的记录为止。l这个过程可用一棵有这个过程可用一棵有n个叶子结点的完全二叉树表示，个叶子结点的完全二叉树表示，8个个叶子结点中依次存放排序之前的叶子结点中依次存放排序之前的8个关键字，个关键字，每个非终端结每个非终端结点中的关键字均等于其

30、左、右孩子结点中较小的关键字，点中的关键字均等于其左、右孩子结点中较小的关键字，则根结点中的关键字即为叶子结点中的最小关键字则根结点中的关键字即为叶子结点中的最小关键字。l在输出最小关键字之后，根据关系的可传递性，欲选出在输出最小关键字之后，根据关系的可传递性，欲选出次小关键字，仅需要将叶子结点中的最小关键字改为次小关键字，仅需要将叶子结点中的最小关键字改为“最大值最大值”，然后从该叶子结点开始，和其左（右）兄，然后从该叶子结点开始，和其左（右）兄弟的关键字进行比较，弟的关键字进行比较，修改从叶子结点到根的路径上各修改从叶子结点到根的路径上各结点的关键字，则根结点的关键字即为次小关键字结点的关

31、键字，则根结点的关键字即为次小关键字。l同理可依次从小到大的所有关键字。由于含有同理可依次从小到大的所有关键字。由于含有n个叶子结个叶子结点的完全二叉树的深度为点的完全二叉树的深度为 log2n+1 ，则在树形选择中，则在树形选择中，除了最小关键字之外，每选择一个次小关键字仅需进行除了最小关键字之外，每选择一个次小关键字仅需进行 log2n 次比较，因此，它的时间复杂度为次比较，因此，它的时间复杂度为O（nlog2n)。2、树形选择排序、树形选择排序38 654997 76 13 27 493865132738131338 654997 76 27 493865762738272738 654

32、997 76 4938657649384938树形选择排序示例树形选择排序示例输出13之后输出13、27之后或(i=1,2,.n/2)ki k2iki k2i+1ki k2iki k2i+13、堆排序、堆排序l堆排序只需要一个记录大小的辅助空间，每个待排序的记录堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。仅占有一个存储空间。（2）堆和完全二叉树）堆和完全二叉树 若将和此序列对应的一维数组（即若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端点的值

33、均不大于则堆的含义表明，完全二叉树中所有非终端点的值均不大于（或不小于）左、右孩子结点的值。由此，若序列（或不小于）左、右孩子结点的值。由此，若序列k1, k2, kn是堆，则堆顶元素（或完全二叉树的根）必为序是堆，则堆顶元素（或完全二叉树的根）必为序列中列中n个元素的最小值（或最大值）个元素的最小值（或最大值）（1）堆的定义）堆的定义：n个元素的序列个元素的序列(k1,k2,kn)，当且仅当满，当且仅当满足下列关系时，称之为堆足下列关系时，称之为堆例例 （96，83，27，38，11，9）例例 （13，38，27，50，76，65，49，97）962791138831327384965765

34、097l可将堆序列看成完全二叉树，则堆顶元素可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中（完全二叉树的根）必为序列中n个元素的最个元素的最小值或最大值小值或最大值3、堆排序、堆排序（3）堆排序）堆排序：若在输出堆顶的最小值之后，使得剩余：若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则可得到个元素的序列重又建成一个堆，则可得到n个元素的次个元素的次小值；如此反复执行，便能得到一个有序序列，这个过小值；如此反复执行，便能得到一个有序序列，这个过程称之为程称之为堆排序堆排序。l实现堆排序需解决的两个问题实现堆排序需解决的两个问题l如何由一个无序序列建成一个

35、堆？如何由一个无序序列建成一个堆？l如何在输出堆顶元素之后，调整剩余元素，使之如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？成为一个新的堆？l二个问题解决方法二个问题解决方法筛选筛选 3、堆排序、堆排序（4）筛选）筛选 l方法：方法：l输出堆顶元素之后，以堆中最后一个元素替代之；输出堆顶元素之后，以堆中最后一个元素替代之；l然后将根结点值与左、右子树的根结点值进行比较，并然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；与其中小者进行交换；l重复上述操作，直至叶子结点，将得到新的堆，重复上述操作，直至叶子结点，将得到新的堆，称这个称这个从堆顶至叶子的调整过程为从堆

36、顶至叶子的调整过程为“筛选筛选” 3、堆排序、堆排序例例13273849657650979727384965765013输出：输出：132749389765765013输出：输出：139749382765765013输出：输出：13 273849502765769713输出：输出：13 276549502738769713输出：输出：13 27 383、堆排序、堆排序4965502738769713输出：输出：13 27 387665502738499713输出：输出：13 27 38 495065762738499713输出：输出：13 27 38 499765762738495013输出：

37、输出：13 27 38 49 506597762738495013输出：输出：13 27 38 49 509765762738495013输出：输出：13 27 38 49 50 653、堆排序、堆排序7665972738495013输出：输出：13 27 38 49 50 659765762738495013输出：输出：13 27 38 49 50 65 769765762738495013输出：输出：13 27 38 49 50 65 76 973、堆排序、堆排序（5）建堆）建堆 l从一个无序序列建堆的过程就是一个反复从一个无序序列建堆的过程就是一个反复“筛选筛选”的过的过程，若将此序列看

38、成是一个完全二叉树，则最后一个非程，若将此序列看成是一个完全二叉树，则最后一个非终端结点是终端结点是 n/2 个元素，由此个元素，由此“筛选筛选”只需从只需从 n/2 个个元素开始。元素开始。l建堆：建堆：从无序序列的第从无序序列的第 n/2 个元素（即此无序序列对应个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选素止，进行反复筛选3、堆排序、堆排序4965382713769750496538271376509749133827657650974913382765765097132738496576509

39、7例如例如 含含8个元素的无序序列个元素的无序序列（49，38，65，97，76，13，27，50）3、堆排序、堆排序l时间复杂度时间复杂度：最坏情况下：最坏情况下T(n)=O(nlogn)l空间复杂度：空间复杂度：S(n)=O(1)l因为其运行时间主要耗费在建初始堆和调整新建堆时进行的因为其运行时间主要耗费在建初始堆和调整新建堆时进行的反复反复“筛选筛选”上。对深度为上。对深度为k的堆，筛选算法中进行的关键的堆，筛选算法中进行的关键字比较次数至多为字比较次数至多为2(k-1)次。总共进行的比较的次数为：次。总共进行的比较的次数为：2( log2(n-1) + log2(n-2) +log22

40、)2n( log2n )由由此，此，堆排序在最坏的情况下，其时间复杂度为堆排序在最坏的情况下，其时间复杂度为O(nlogn)。l相对于快速排序，此外，堆排序仅需一个记录大小供交换相对于快速排序，此外，堆排序仅需一个记录大小供交换用，用，。因此是一种适合于排序较大文件的排序方法。因此是一种适合于排序较大文件的排序方法。l堆排序是一种不稳定的排序方法。堆排序是一种不稳定的排序方法。3、堆排序、堆排序l归并排序归并排序是又一类不同的排序方法。是又一类不同的排序方法。“归并归并”的含义是将两的含义是将两个或两个以上的有序表组合成一个新的有序表个或两个以上的有序表组合成一个新的有序表10.4 归并排序归

41、并排序l排序过程：排序过程：假设初始序列含有假设初始序列含有n个记录，则可看成个记录，则可看成n个有序个有序的子序列，每个子序列长度为的子序列，每个子序列长度为1，然后两两归并，得到，然后两两归并，得到 n/2 个长度为个长度为2或或1的有序子序列；再两两归并，的有序子序列；再两两归并，如此重复，如此重复，直至得到一个长度为直至得到一个长度为n的有序序列为止，这种排序方法称为的有序序列为止，这种排序方法称为2-路归并排序。路归并排序。 l2-路归并排序中的核心操作是将一维数组中前后相邻的两个路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。有序序列归并为一个有序序列

42、。将两个或两个以上的将两个或两个以上的有序表组合成一个新的有序表，叫有序表组合成一个新的有序表，叫2-路归并排序。路归并排序。初始关键字：初始关键字： 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归并排序归并排序l时间复杂度：时间复杂度：T(n)=O(nlog2n)l空间复杂度：空间复杂度：S(n)=O(n)l一趟归并排序的操作是一趟归并排序的操作是:调用调用 次算法将次算法将SR1,n 中中前后相邻且

43、长度为前后相邻且长度为h的有序序列段进行两两归并，得到前后的有序序列段进行两两归并，得到前后相邻、长度为相邻、长度为2h 的有序段，并存放在的有序段，并存放在TR1,n中，整个归中，整个归并排序需进行并排序需进行 log2n 趟。可见，实现归并排序需和待排序记趟。可见，实现归并排序需和待排序记录等数量的辅助空间，其时间复杂度为录等数量的辅助空间，其时间复杂度为O(nlog2n)。l与快速排序和堆排序相比，归并排序的最大特点，它是一种与快速排序和堆排序相比，归并排序的最大特点，它是一种稳定的排序方法稳定的排序方法。但在一般情况下，很少利用。但在一般情况下，很少利用2路归并排序路归并排序方法进行内

44、部排序。方法进行内部排序。hn2归并排序归并排序l 2 3 A 2 3 Al 2 3 A 2 3 A10.5 基数排序基数排序1、多关键字排序、多关键字排序l每一张牌有两个每一张牌有两个“关键字关键字”：花色和面值花色和面值，且，且“花色花色”的地的地位高于位高于“面值面值”，在比较任意两张牌面的大小时，必须先比，在比较任意两张牌面的大小时，必须先比较较“花色花色”，若，若“花色花色”相同，则再比较面值。相同，则再比较面值。l已知扑克牌中已知扑克牌中52张牌面的次序为：张牌面的次序为：l两个关键字两个关键字：花色（：花色（ ） 面值（面值（23A）l并且并且“花色花色”地位高于地位高于“面值面

45、值”l方法方法1：先对花色排序，将其分为先对花色排序，将其分为4个组，即梅花组、方块个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将最后，将4个组连接起来即可。个组连接起来即可。l方法方法2：先按先按13个面值给出个面值给出13个编号组个编号组(2号，号，3号，号，.，A号号)，将牌按面值依次放入对应的编号组，分成，将牌按面值依次放入对应的编号组，分成13堆。再按堆。再按花色给出花色给出4个编号组个编号组(梅花、方块、红心、黑心梅花、方块、红心、黑心)，将，将2号组中号组中牌取出分别放入对应花色组，再将牌取出分别放

46、入对应花色组，再将3号组中牌取出分别放入号组中牌取出分别放入对应花色组，对应花色组，这样，这样，4个花色组中均按面值有序，然个花色组中均按面值有序，然后，将后，将4个花色组依次连接起来即可。个花色组依次连接起来即可。 l由此，将扑克牌调整成如上所述次序时，通常采用的方法是：由此，将扑克牌调整成如上所述次序时，通常采用的方法是：1、多关键字排序、多关键字排序l一般情况下，假设有一般情况下，假设有n个记录的序列个记录的序列R1，R2，Rn，且每，且每个记录个记录Ri中含有中含有d个关键字（个关键字（Ki0，Ki1，Kid-1），则称序列），则称序列对关键字（对关键字（K0，K1，Kd-1）有序是指

47、：对于序列中任意两）有序是指：对于序列中任意两个记录个记录Ri和和Rj（1 ij n）都满足下列有序关系）都满足下列有序关系l为实现多关键字排序，通常有两种方法：为实现多关键字排序，通常有两种方法：l先对先对最高位关键字进行排序最高位关键字进行排序l先对先对最高低关键字进行排序最高低关键字进行排序l（Ki0，Ki1，Kid-1）（Kj0，Kj1，Kjd-1）l其中其中K0称为称为最主位关键字最主位关键字，Kd-1称为称为最次位关键字最次位关键字。1、多关键字排序、多关键字排序l第一种方法是先对最高位关键字第一种方法是先对最高位关键字K0（如花色）进行排序，（如花色）进行排序，将序列分成若干子序

48、列，每个子序列中的记录都具有相同将序列分成若干子序列，每个子序列中的记录都具有相同的的K0值；值；l然后分别就每个子序列对次关键字然后分别就每个子序列对次关键字K1（如面值）进行排（如面值）进行排序，按序，按K1值不同再值不同再分成若干更小的子序列；分成若干更小的子序列；l依次重复，直至对依次重复，直至对Kd-2进行排序之后得到的每一子序列中的进行排序之后得到的每一子序列中的记录都具有相同的关键字（记录都具有相同的关键字（ K0，K1，Kd-2），而后分），而后分别每个子序列对别每个子序列对Kd-1进行排序，最后将所有子序列依次联接进行排序，最后将所有子序列依次联接在一起成为一个有序序列，这种

49、方法称之为在一起成为一个有序序列，这种方法称之为最高优先法最高优先法（Most Significant Digit first） （MSD) 。1、多关键字排序、多关键字排序l第二种方法是从最低位关键字第二种方法是从最低位关键字Kd-1起进行排序。然后再对高起进行排序。然后再对高一位的关键字一位的关键字Kd-2排序，排序，依次重复，直至对最高位关键依次重复，直至对最高位关键字字K0排序后，便成为一个有序序列。这种方法称之为排序后，便成为一个有序序列。这种方法称之为最低最低位优先法位优先法(LSD)。lMSD与与LSD不同特点不同特点l按按MSD排序排序，必须将序列逐层分割成若干子序，必须将序列

50、逐层分割成若干子序列，然后对各子序列分别排序列，然后对各子序列分别排序。l按按LSD排序排序，不必分成子序列，对每个关键字都是，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而整个序列参加排序；并且可不通过关键字比较，而通过若干次通过若干次“分配分配”与与“收集收集”实现排序实现排序。1、多关键字排序、多关键字排序2、链式基数排序、链式基数排序l基数排序基数排序：借助：借助“分配分配”和和“收集收集”对单逻辑关键字进行排对单逻辑关键字进行排序的一种方法序的一种方法 l链式基数排序链式基数排序：用链表作存储结构的基数排序：用链表作存储结构的基数排序l逻辑关键字可以看成

51、由若干个关键字复合而成的。例如，若逻辑关键字可以看成由若干个关键字复合而成的。例如，若关键字是数值，且其值都在关键字是数值，且其值都在0 k 999范围内，则可把每一个范围内，则可把每一个十进制数字看成一个关键字，即可认为十进制数字看成一个关键字，即可认为K由三个关键字由三个关键字（ K0， K1， K2 ）组成，其中）组成，其中K0是百位数，是百位数， K1是十位数，是十位数，K2是个位数；是个位数；l又若关键字又若关键字K由五个字母组成的单词，则可看成是由五个关由五个字母组成的单词，则可看成是由五个关键字（键字（ （K0， K1， K2 ，K3，K4 ）组成，其中）组成，其中K j-1是（

52、自左是（自左至右）的第至右）的第j+1个字母。个字母。l由于如此分解而得的每个关键字由于如此分解而得的每个关键字Kj都在相同的范围内都在相同的范围内（对数字，（对数字， 0 Kj 9，对字母，对字母“A” Kj Z”），按），按LSD进进行排序更为方便，只要从最小数位关键字起，按关键字行排序更为方便，只要从最小数位关键字起，按关键字的不同值将序列中记录的不同值将序列中记录“分配分配”到到RADIX个队伍中后再个队伍中后再“收集收集”之，如此重复之，如此重复d次。次。l按这种方法实现排序称之为基数排序按这种方法实现排序称之为基数排序，其中，其中“基基”指的指的是是RADIX的取值范围，在上述两种

53、关键字的情况下，它的取值范围，在上述两种关键字的情况下，它们分别是们分别是“10”和和“26”。l首先以静态链表存储首先以静态链表存储n个待排记录，并令表头指针指向第个待排记录，并令表头指针指向第一个记录，如图一个记录，如图(a)所示。所示。2、链式基数排序、链式基数排序l第一趟分配对最低数位关键字（个位数）进行，改变记录第一趟分配对最低数位关键字（个位数）进行，改变记录的指针值将链表中的记录分配至的指针值将链表中的记录分配至10个链对列中去，每个队个链对列中去，每个队列中的记录关键字的个位数相等，如图列中的记录关键字的个位数相等，如图(b)所示。所示。l其中其中fi和和ei分别为第分别为第i

54、个队列的头指针和尾指针；个队列的头指针和尾指针；l第一趟收集是改变所有非空队列的对尾记录的指针值域，第一趟收集是改变所有非空队列的对尾记录的指针值域，令其指向下一个非空队列的对头的记录，重新将令其指向下一个非空队列的对头的记录，重新将10个队列个队列中的记录链成一个链表，如图（中的记录链成一个链表，如图（c）所示；）所示；l第二趟分配，第二趟收集及第三趟分配和第三趟收集分别第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的，其过程和个位数相同，如图是对十位数和百位数进行的，其过程和个位数相同，如图(d)(g)所示，至此排序完毕。所示，至此排序完毕。2、链式基数排序、链式基数排序例例初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配一趟分配930063083184505278008109589269一趟收集：一趟收集：2、链式基数排序、链式基数排序50