数据结构(严蔚敏) 第10章排序.ppt

《数据结构(严蔚敏) 第10章排序.ppt》由会员分享，可在线阅读，更多相关《数据结构(严蔚敏) 第10章排序.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第10章 排序 10.1 概 述 排序(Sorting)是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。从第9章的讨论中容易看出，为了查找方便，通常希望计算机中的表是按关键字有序的。又如建造树表(无论是二叉排序树或B-树)的过程本身就是一个排序的过程。因此，学习和研究各种排序方法是计算机工作者的重要课题之一。为了便于讨论，在此首先要对排序下一个确切的定义：假设含n个记录的序列为 R1，R2，Rn (10-1)其相应的关键字序列为 K1，K2，Kn (10-2)需确定1，2，n的一种排列p1，p2，pn，使其 相应的关键字满足如下

2、的非递减(或非递增)关系 Kp1Kp2Kpn 即使式（10-1）的序列成为一个按关键字有序的序列 Rp1，Rp2，Rpn 这样一种操作称为排序。上述排序定义中的关键字Ki可以是记录Ri(i=1，2，n)的主关键字，也可以是记录Ri的次关键字，甚至是若干数据项的组合。若Ki是主关键字，则任何一个记录的无序序列经排序后得到的结果是唯一的；若Ki是次关键字，则排序的结果不唯一，因为待排序的记录序列中可能存在两个或两个以上关键字相等的记录。假设Ki=Kj(1i n，1jn，i!=j)，且在排序前的序列中Ri领先于Rj(即ij)。若在排序后的序列中 Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，若

3、可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。本章集中讨论内部排序。内部排序的方法很多，每一种方法都有各自的优缺点，适合在不同的环境(如记录的初始排列状态等)下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序、选择排序、归并排序和计数排序等五类；如果按内部排序过程中

4、所需的工作量来区分，则可分为三类：(1)简单的排序方法，其时间复杂度为O(n2)；(2)先进的排序方法，其时间复杂度为O(nlogn)；(3)基数排序，其时间复杂度为O(dn)。10.2 插入排序 一、直接插入排序 直接插人排序(Straight Insertion Sort)是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。例如，已知待排序的一组记录的初始排列如下所示：R(49),R(38),R(65),R(97),R(76),R(13),R(27),R(49),(10-4)假设在排序过程中，前4个记录已按关键字递增的次序重新排列

5、，构成一个含4个记录的有序序列 R(38)，R(49)，R(65)，R(97)(10-5)现要将式(10-4)中第5个(即关键字为76的)记录插入上述序列，以得到一个新的含5个记录的有序序列，则首先要在式(10-5)的序列中进行查找以确定R(76)所应插入的位置，然后进行插入。假设从R(97)起向左进行顺序查找，得到下列新的有序序列 R(38)，R(49)，R(65)，R(76)，R(97)(10-6)称从式(10-5)到式(10-6)的过程为一趟直接插入排序。一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r1.i-1中插入一个记录ri后，变成含有i个记录的有序子序列r

6、1.i；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r0处设置监视哨。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。直接插人排序算法描述：void InsertSort(SqList&L)/对顺序表L作直接插入排序。for(i=2；i=L.length；+i)if LT(L.ri.key，L.ri-1.key)/“”，需将L.ri插入有序子表 L.r0=L.ri /复制为哨兵 for(j=i-1;LT(L.r0.

7、key，L.rj.key);-j)L.rj+1=L.rj；/记录后移 L.rj+1=L.r0 /插入到正确位置 /Insertsort 算法 10.1 初始关键字：(49)38 65 97 76 13 27 49 i=2 (38)(38 49)65 97 76 13 27 49 i=3 (65)(38 49 65)97 76 13 27 49 i=4 (97)(38 49 65 97)76 13 27 49 i=5 (76)(38 49 65 76 97)13 27 49 i=6 (13)(13 38 49 65 76 97)27 49 i=7 (27)(13 27 38 49 65 76 9

8、7)49 i=8 (49)(13 27 38 49 49 65 76 97)监视哨L.r0 图10.1 直接插入排序示例 直接插入排序的算法简洁，容易实现，那么它的效率如何呢?从空间来看，它只需要一个记录的辅助空间，从时间来看，排序的基本操作为比较两个关键字的大小和移动记录。当待排序列中记录按关键字非递减有序排列(以下称之为“正序”)时，所需进行关键字间比较的次数达最小值n-1，记录不需移动；反之，当待排序列中记录按关键字非递增有序排列(以下称之为“逆序”)时，总的比较次数达最大值(n+2)(n-1)/2。记录移动的次数也达最大值(n+4)(n-1)/2。若待排序记录是随机的，即待排序列中的记

9、录可能出现的各种排列的概率相同，则我们可取上述最小值和最大值的平均值，作为直接插入排序时所需进行关键字间的比较次数和移动记录的次数，约为n2/4。由此，直接插入排序的时间复杂度为O(n2)。二、其它插人排序 从上一节的讨论中可见，直接插入排序算法简便，且容易实现。当待排序记录的数量 n很小时，这是一种很好的排序方法。但是，通常待排序序列中的记录数量n很大，则不宜采用直接插入排序。由此需要讨论改进的办法。在直接插入排序的基础上，从减少“比较”和“移动”这两种操作的次数着眼，可实现其他的插入排序的方法。1、折半插入排序 由于插入排序的基本操作是在一个有序表中进行查找和插入，则从9.1节的讨论中可知

10、，这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序(BinarylnsertionSort)，其算法如算法10.2所示。void BInsertSort(SqList&L)/对顺序表L作折半插入排序。for(i=2；iL.length；+i)L.r0=L.ri /L.ri暂存到L.r0 low=1;high=i-1;/在rlow.high中折半查找有序插入的位置 while(low=high+1;-j)L.rj+1=L.rj;/记录后移 L.rhigh+1=L.r0;/插入 /for/BInsertSort 算法10.2 折半插入排序所需附加存储空间和直接插入排序

11、相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为O(n2)。2、2-路插入排序 2-路插入排序是在折半插入排序的基础上再改进之，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。具体做法是：另设一个和L.r同类型的数组d，首先将L.r1赋值给d1，并将d1看成是在排好序的序列中处于中间位置的记录，然后从L.r中第2个记录起依次插入到d1之前或之后的有序序列中。先将待插记录的关键字和d1的关键字进行比较，若Lri.keyd1.key，则将L.ri插入到d1之前的有序表中。反之，则将L.ri插入到d1之后的有序表

12、中。在实现算法时，可将d看成是一个循环向量，并设两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。初始关键字：49 38 65 97 76 13 27 49*排序过程中d的状态如下：i=1:(49)first finali=2:(49)(38)final firsti=3:(49 65)(38)final firsti=4:(49 65 97)(38)final firsti=5:(49 65 76 97)(38)final firsti=6:(49 65 76 97)(13 38)final first i=7:(49 65 76 97)

13、(13 27 38)final first i=8:(49 49*65 76 97 13 27 38)final first 图10.2 2-路插入排序示例 在2-路插入排序中，移动记录的次数约为n2/8。因此，2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。并且，当L.r1是待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去它的优越性。因此，若希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序。3、表插入排序 用静态链表做为待排序记录序列的存储结构。设数组中下标为“0”的分量为表头结点，并令表头结点记录的关键字取最大整数MAXINT。则表插入排序的过程描述

14、如下：首先将静态链表中数组下标为“1”的分量(结点)和表头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量(结点)按记录关键字非递减有序插入到循环链表中。0 1 2 3 4 5 6 7 8 MAXINT4938659776132749*10-MAXINT4938659776132749*681504723 从表插入排序的过程可见，表插入排序的基本操作仍是将一个记录插入到已排好序的有序表中。和直接插入排序相比，不同之处仅是以修改2n次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数相同。因此，表插入排序的时间复杂度仍是 O(n2)。另一方面，表插入排序的结果只是求得一个有序链

15、表，则只能对它进行顺序查找，不能进行随机查找，为了能实现有序表的折半查找，尚需对记录进行重新排列。三、希尔排序 希尔排序(Shells Sort)又称“缩小增量排序”(Diminishing Increment Sort)，它也是一种属插入排序类的方法，但在时间效率上较前述几种排序方法有较大的改进。从对直接插入排序的分析得知，其算法时间复杂度为O(n2)，但是，若待排记录序列为“正序”时，其时间复杂度可提高至O(n)。由此可设想，若待排记录序列按关键字“基本有序”，即序列中具有下列特性 L.ri.key MaxL.rj.key (10-7)1ji 的记录较少时，直接插入排序的效率就可大大提高，

16、从另一方面来看，由于直接插入排序算法简单，则在n值很小时效率也比较高。希尔排序正是从这两点分析出发对直接插入排序进行改进得到的一种插入排序方法。它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。初始关键字：49 38 65 97 76 13 27 49*55 04一趟排序结果：13 27 49*55 04 49 38 65 97 76 二趟排序结果：13 04 49*38 27 49 55 65 97 76三趟排序结果：04 13 27 38 49*49 55 65 76 97 从上述排序过程可见，希

17、尔排序的一个特点是：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。如上例中，第一趟排序时的增量为5，第二趟排序时的增量为3，由于在前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地往前挪动，而是跳跃式地往前移，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序，只要作记录的少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。下面用算法语言描述上述希尔排序的过程，为此先将算法10.1改写成如算法 10.4所示的一般形式。希尔排序算法如算法10.5所示。void ShellIn

18、sert(SqList&L，int dk)/对顺序表L作一趟希尔插入排序。/本算法是和一趟直接插入排序相比，作了以下修改：/1、前后记录位置的增量是dk，而不是1；/2、r0只是暂存单元，不是哨兵。当j=0时，插入位置已找到。for(i=dk+1；i0<(L.r0.key，L.rj.key)；j-=dk)L.rj+dk=L.rj；/记录后移，查找插入位置 L.rj+dk=L.r0；/插入 /if/ShellInsert 算法10.4 void ShellSort(Sqlist&L，int dlta，int t)/按增量序列dlta0.t-1对顺序表L作希尔排序。for(k=0；kL.r2.

19、key)，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。.一般地，第i趟起泡排序是从L.r1到L.rn-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需进行k(1=kn)趟起泡排序，显然，判别起泡排序结束的条件应该是“在一

20、趟排序过程中没有进行过交换记录的操作”。49 38 38 38 38 13 13 38 49 49 49 13 27 27 65 65 65 13 27 38 38 97 76 13 27 49 49 76 13 27 49*49*13 27 49*65 27 49*76 49*97 图10.6展示了起泡排序的一个实例 分析起泡排序的效率，容易看出，若初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；反之，若初始序列为“逆序”序列，则需进行n-1趟排序，需进行n(n-1)/2次比较，并作等数量级的记录移动。因此，总的时间复杂度为O(n2)。快速排

21、序(Quick Sort)是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。假设待排序的序列为L.rs，L.rs+1，L.rt，首先任意选取一个记录(通常可选第一个记录L.rs作为枢轴(或支点)(pivot)，然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。这个过程称作一趟快速排序(或一次划分)。一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别为low和high

22、，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。其算法如算法10.6(a)所示。int Partition(SqList&L，int low，int high)/交换顺序表L中子表L.rlow.high的记录，使枢轴记录到位，/并返回其所在位置，此时在它之前(后)的记录均不大(小)于它。pivotkey =L.rlow.key；/用子表的第一个记录作枢轴记录 while(lowh

23、igh)/从表的两端交替地向中间扫描 while(lowpivotkey)-high;L.rlowL.rhigh;/将比枢轴记录小的记录交换到低端 while(lowhigh&L.rlow.keypivotkey)+low;L.rlowL.rhigh;/将比枢轴记录大的记录交换到高端 return low;/返回枢轴所在位置/partition 算法10.6(a)改写上述算法，先将枢轴记录暂存在r0的位置上，排序过程中只作rlow或rhigh的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。int Partition(SqList&L，int low，int high)/交换顺序表L中

24、子表rlowhigh的记录，/枢轴记录到位，并返回其所在位置，/此时在它之前(后)的记录均不大(小)于它。L.r0=L.rlow；pivotkey=L.rlow.key；/枢轴记录关键字 while(lowhigh)/从表的两端交替地向中间扫描 while(lowpivotkey)-high;L.rlow=L.rhigh;/将比枢轴记录小的记录移到低端 low while(lowhigh&L.rlow.keypivotkey)+low;L.rhigh=L.rlow;/将比枢轴记录大的记录移到高端 L.rlow=L.r0;/枢轴记录到位 return low；/返回枢轴位置/Partition快

25、速排序示例：初始关键字：49 38 65 97 76 13 27 49*low high进行1次交换之后：27 38 65 97 76 13 49*low high进行2次交换之后：27 38 97 76 13 65 49*low high进行3次交换之后：27 38 13 97 76 65 49*low high进行4次交换之后：27 38 13 76 97 65 49*low high high 完成一趟排序 27 38 13 49 76 97 65 49*初始状态：49 38 65 97 76 13 27 49*一次划分之后：27 38 13 49 76 97 65 49*分别进行快速排

26、序：13 27 38 49*65 76 97 49*65有序序列：13 27 38 49 49*65 76 97 排序的全过程 递归形式的快速排序算法如算法10.7和算法10.8所示。void QSort(SqList&L，int low，int high)/对顺序表l中的子序列L.rlowhigh作快速排序 if(lowhigh)/长度大于1 pivotloc=Partition(L，low，high);QSort(L，low，pivotloc-1);/对低子表递归排序 QSort(L，pivotloc+1，high)；/对高于表递归排序 /QSort 算法 10.7void QuickSo

27、rt(SqList&L)/对顺序表L作快速排序 QSort(L，1，L.length)；/QuickSort 算法 10.8 通常，快速排序被认为是，在所有同数量级(O(nlogn)的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。为改进之，通常依“三者取中”的法则来选取枢轴记录，即比较 L.rs.key、L.rt.key和L.rfloor(s+t)/2).key，取三者中其关键字取中值的记录为枢轴，只要将该记录和L.rs互换，算法10.6(b)不变。经验证明，采用三者取中的规则可大大改善快速排序在最坏情况下的性能。

28、然而，即使如此，也不能使快速排序在待排记录序列已按关键字有序的情况下达到O(n)的时间复杂度。为此，可如下所述修改“一次划分”算法：在指针high减1和low增1的同时进行“起泡”操作，即在相邻两个记录处于“逆序”时进行互换，同时在算法中附设两个布尔型变量分别指示指针low和high在从两端向中间的移动过程中是否进行过交换记录的操作，若指针low在从低端向中间的移动过程中没有进行交换记录的操作，则不再需要对低端子表进行排序；类似地，若指针high在从高端向中间的移动过程中没有进行交换记录的操作，则不再需要对高端子表进行排序。显然，如此“划分”将进一步改善快速排序的平均性能。由以上讨论可知，从时

29、间上看，快速排序的平均性能优于前面讨论过的各种排序方法，从空间上看，前面讨论的各种方法，除2-路插入排序之外，都只需要一个记录的附加空间即可，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为floor(log2n)+1(包括最外层参量进栈)，但是，若每趟排序之后，枢轴位置均偏向子序列的一端，则为最坏情况，栈的最大深度为n。如果改写算法10.7，在一趟排序之后比较分割所得两部分的长度，且先对长度短的子序列中的记录进行快速排序，则栈的最大深度可降为O(logn)。10.4 选择排序 选择排序(SelectionSort)的基本思想是：每

30、一趟在n-i+1(i=1，2，n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。其中最简单、且为读者最熟悉的是简单选择排序。(Simple Selection Sort)。10.4.1 简单选择排序 一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1in)个记录交换之。显然，对L.r1.n中记录进行简单选择排序的算法为：令i从1至n-1，进行n-1趟选择操作，如算法10.9所示。void SelectSort(SqList&L)/对顺序表L作简单选择排序。for(i=1;iL.length；+i)/选择第i小的记录，并交换到

31、位 j=SelectMinKey(L，i)；/在L.ri.L.length中选择key最小的记录 if(i!=j)L.ri L.rj；/与第i个记录交换 算法10.9 容易看出，简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为“0”，最大值为3(n-1)。然而，无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为n(n-1)/2。因此，总的时间复杂度也是 O(n2)。那末，能否加以改进呢?改进简单选择排序应从如何减少“比较”出发考虑。显然，在n个关键字中选出最小值，至少进行n-1次比较，然而，继续在剩余的n-1个关键字中选择次小值就并非一定要进行n-2次比较，若能利用前

32、n-1次比较所得信息，则可减少以后各趟选择排序中所用的比较次数。实际上，体育比赛中的锦标赛便是一种选择排序。10.4.2 树形选择排序 树形选择排序(TreeSelectionSort)，又称锦标赛排序(TournamentSort)，是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在其中ceil(n/2)个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。这个过程可用一棵有n个叶子结点的完全二叉树表示。1313383865132749 38 6597137627 49*(a)输出13之后 输出13、27之后 (b)(c)由于含有n个叶子结点的

33、完全二叉树的深度为log2n+1，则在树形选择排序中，除了最小关键字之外，每选择一个次小关键字仅需进行log2n次比较，因此，它的时间复杂度为，O(nlog2n)。但是，这种排序方法尚有辅助存储空间较多、和“最大值”进行多余的比较等缺点。273827386576274938 659776 27 49*383849*38657649*4938 65 97 76 49*10.4.3 堆排序 堆排序(HeapSort)只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。堆的定义如下：n个元素的序列k1,k2,kn当且仅当满足下关系时，称之为堆。kik2i kik2i 或 kik2i+1

34、，kik2i+1 (i=1,2,n/2)若将和此序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此，若序列k1，k2，kn是堆，则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。例如，下列两个序列为堆，对应的完全二叉树如图10.10所示。96，83，27，38，11，09 12，36，24，85，47，30，53，91 图10.10 堆的示例9683273811091236248547305391 若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一

35、个堆，则得到 n个元素中的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。由此，实现堆排序需要解决两个问题：(1)如何由一个无序序列建成一个堆?(2)如何在输出堆顶元素之后，调整剩余元素成为一个新的堆?先讨论第二个问题，如何在输出堆顶元素之后，调整剩余元素成为一个新的堆?例如，图10.11(a)是个堆，假设输出堆顶元素之后，以堆中最后一个元素替代之，如图10.11(b)所示。此时根结点的左、右子树均为堆，则仅需自上至下进行调整即可。(a)(b)(c)(d)我们称这个自堆顶至叶子的调整过程为“筛选”。13382749*76 65499797382749*76 654913273

36、84949*76 6597133849*4997 76 652713 如何由一个无序序列建成一个堆?从一个无序序列建堆的过程就是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第n/2个元素，由此“筛选”只需从第n/2个元素开始。例如，图10.12(a)中的二叉树表示一个有8个元素的无序序列则筛选从第4个元素开始 1 2 3 4 (a)(b)(c)(d)49386597 76132749*49386549*76 13279749381349*76 65279713382749*76654997 堆排序的算法如算法10.11所示，其中筛选的算法如算法10.10所示。

37、为使记录序列按关键字非递减有序排列，则在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。由此，“筛选”应沿关键字较大的孩子结点向下进行。void HeapAdjust(SqList H，int s，int m)/已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，/本函数调整H.rs的关键字，使H.rs.m成为一个大顶堆 rc=H.rs;for(j=2*s;j=m;j*=2)/沿key较大的孩子结点向下筛选 /j为key较大的记录的下标 if(j0;

38、-i)/把H.r1.length建成大顶堆 HeapAdjust(H，i，H.length);for(i=H.length；i1;-i)H.r1H.ri;/将堆顶记录和当前未经排序子序列Hr.1.i中 /最后一个记录相互交换 HeapAdjust(H,1,i-1);/将H.R1.i-1重新调整为大顶堆 /HeapSort 算法 10.11 堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。对深度为k的堆，筛选算法中进行的关键字比较次数至多为2(k-1)次，则在建含n个元素、深度为k的堆时，总共进行的关键字

39、比较次数不超过4n(p283)。又，n个结点的完全二叉树的深度为log2n+1，则调整建新堆时调HeapAdjust过程n-1次，总共进行的比较次数不超过2n*log2n，由此，堆排序在最坏的情况下，其时间复杂度也为O(nlogn)。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小供交换用的辅助存储空间。10.5 归并排序 归并排序(Merging Sort)是又一类不同的排序方法。“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。它的实现方法早巳为读者所熟悉，无论是顺序存储结构还是链表存储结构，都可在O(m+n)的时间量级上实现。利用归并的思想容易实现排序。

40、假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。例如图10.13为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 图10.13 2-路归并排序示例 2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，

41、其算法(类似于算法2.7)如下所示。void Merge(RcdType SR，RcdType&TR,int i，int m，int n)for(j=m+1，k=i;i=m&j=n；+k)/将SR中记录由小到大地并入TR if LQ(SRi.key，SRj.key)TRk=SRi+;else TRk=SRj+;if(i=m)TRk.n=SRi.m;/将剩余的SRi.m复制到TR if(j=n)TRk.n=SRj.n;/将剩余的SRj.n复制到TR /merge 算法 10.12 一趟归并排序的操作是，调用n/2h次算法merge将SR1.n中前后相邻且长度为h的有序段进行两两归并，得到前后相邻

42、、长度为2h的有序段，并存放在TR1.n中，整个归并排序需进行log2n趟。可见，实现归并排序需和待排记录等数量的辅助空间，其时间复杂度为O(nlog2n)。与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序方法。但在一般情况下，很少利用2-路归并算法进行内部排序。（递归形式的2-路归并算法如算法10.13 算法10.14所示）10.6 基数排序 基数排序(Radix Sorting)是和前面所述各类排序方法完全不相同的一种排序方法。从前几节的讨论可见，实现排序主要是通过关键字间的比较和移动记录这两种操作，而实现基数排序不需要进行记录关键字间的比较。基数排序是一种借助多关键字排序

43、的思想对单逻辑关键字进行排序的方法。10.6.1 多关键字的排序 先看一个具体例子。已知扑克牌中52张牌每一张牌有两个“关键字”：花色和面值(23A)，且“花色”的地位高于“面值”，在比较任意两张牌面的大小时，必须先比较“花色”，若“花色”相同，则再比较面值。由此，将扑克牌整理成如上所述次序关系时，通常采用的办法是：先按不同“花色”分成有次序的四堆，每一堆的牌均具有相同的“花色”，然后分别对每一堆按“面值”大小整理有序。也可采用另一种办法：先按不同“面值”分成13堆，然后将这13堆牌自小至大叠在一起，然后将这付牌整个颠倒过来再重新按不同“花色”分成4堆，最后将这4堆牌按自小至大的次序合在一起，

44、此时同样得到一付满足如上次序关系的牌。这两种整理扑克牌的方法便是两种多关键字的排序方法。一般情况下，假设有n个记录的序列 R1，R2，Rn (10-10)且每个记录Ri中含有d个关键字(Ki0，Ki1，Kid-1)，则称序列(10-10)对关键字(K0，K1，Kd-1)有序是指：对于序列中任意两个记录Ri和Rj(1ijn)都满足下列有序关系：(Ki0，Ki1，Kid-1)(Kj0，Kj1，Kjd-1)其中K0称为最主位关键字，Kd-1称为最次位关键字。为实现多关键字排序，通常有两种方法：第一种方法是：先对最主位关键字K0进行排序，将序列分成若干子序列，每个子亨列中的记录都具有相同的K0值，然后

45、分别就每个子序列对关键字K1进行排序，按K1值不同再分成若干更小的子序列，依次重复，直至对Kd-2进行排序之后得到的每一子序列中的记录都具有相同的关键字(K0，K1，Kd-2)，而后分别每个子序列对Kd-1进行徘序，最后将所有子序列依次联接在一起成为一个有序序列，这种方法称之为最高位优先(Most Significant Digit first)法，简称MSD法；第二种方法是从最次位关键字Kd-1起进行排序。然后再对高一位的关键字Kd-2进行排序，依次重复，直至对K0进行排序后便成为一个有序序列。这种方法称之为最低位优先(Least Significant Digit first)法，简称 L

46、SD法。MSD和LSD只约定按什么样的“关键字次序”来进行排序，而未规定对每个关键字进行排序时所用的方法。但从上面所述可以看出这两种排序方法的不同特点：若按MSD进行排序，必须将序列逐层分割成若干子序列，然后对各子序列分别进行排序；而按 LSD进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对Ki(0id-2)进行排序时，只能用稳定的排序方法。另一方面，按LSD进行排序时，在一定的条件下(即对前一个关键字Ki(0id-2)的不同值，后一个关键字Ki+1均取相同值)，也可以不利用前几节所述各种通过关键字间的比较来实现排序的方法，而是通过若干次“分配”和“收集”来实现排序，如上述第

47、二种整理扑克牌的方法那样。10.6.2 链式基数排序 基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。有的逻辑关键字可以看成由若干个关键字复合而成的。例如，若关键字是数值，且其值都在0K999范围内，则可把每一个十进数字看成一个关键字，即可认为K由三个关键字(K0，K1，K2)组成，其中K0是百位数，K1是十位数，K2是个位数；又若关键字K是由五个字母组成的单词，则可看成是由五个关键字(K0，K1，K2，K3，K4)组成，由于如此分解而得的每个关键字长Kj都在相同的范围内，则按LSD进行排序更为方便，只要从最低数位关键字起，按关键字的不同值将序列中记录“分配”

48、到RADIX个队列中后再“收集”之，如此重复d次。按这种方法实现排序称之为基数排序，其中“基”指的是RADIX的取值范围，在上述两种关键字的情况下，它们分别为“10”和“26”。早期由于基数排序所需的辅助存储量(RADIX*N个记录空间)太大。直到1954年有人提出用“计数”代替“分配”才使基数排序得以在计算机上实现，但此时仍需要n个记录和2*RADIX个计数单元的辅助空间。此后，有人提出用链表作存储结构，则又省去了n个记录的辅助空间。下面我们就来介绍这种“链式基数排序”的方法。具体例子:首先以静态链表存储n个待排记录，并令表头指针指向第一个记录，如图10.14(a)所示；第一趟分配对最低数位

49、关键字(个位数)进行，改变记录的指针值将链表中的记录分配至10个链队列中去，每个队列中的记录关键字的个位数相等，其中fi和ei分别为第i个队列的头指针和尾指针；第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将 10个队列中的记录链成一个链表如图10.14(c)；第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的，其过程和个位数相同，如图10.14(d)(g)所示。至此排序完毕。(P287 图10.14)基数排序算法类C语言描述：#define MAX_NUM_OF_KEY 8 /关键字项数的最大值#define RADIX 10

50、/关键字基数，此时是十进制整数的基数#define MAX_SPACE 10000 typedef struct keysType keysMAX_NUM_OF_KEY;/关键字 InfoType otheritems；/其它数据项 int next；SLCell;/静态链表的结点类型 typedef struct SLCell rMAX_SPACE;/静态链表的可利用空间,r0为头结点 int keynum;/记录的当前关键字个数 int recnum；/静态链表的当前长度SLList；/静态链表类型 typedef int ArrType RADIX；/指针数组类型链式基数排序中一趟分配的