数据结构(第10章排序)

第10章内部排序排序是数据处理中经常用到的操作，先来给出排序的定义。通常我们把按关键字递增有序的序列称为正序序列，把按关键字递减有序的序列称为逆序序列。如果不特别声明，今后我们说的有序均是指正序。

需要注意的是，在上述定义中，关键字既可以是主关键字，也可以是次关键字。如果是主关键字，则不管对序列采用哪种排序方法，排序的结果是唯一的。

如果是次关键字，由于可能多个记录具有相同的关键字，这时对序列采用不同的排序方法，得到的排序结果可能不相同。

如果一种排序方法可以保证关键字相同的记录在排序前后的相对次序保持不变，则称此排序方法是稳定的；否则称为不稳定的.假设有一个记录序列（R1，R2，…，Rn），Ki为Ri的关键字,所谓排序就是要确定1、2、…、n的一种排列i1、i2、…、in，使得（Ri1，Ri2，…，Rin

）按关键字有序，即满足：

Ki1≤Ki2≤…≤Kin第10章内部排序根据排序过程中涉及的存储器类型，排序方法分为两大类：

为了描述方便起见，特做如下约定（参见P264）：在本章中，我们将研究各种内部排序方法。内部排序方法有许多种，从排序原理的角度看，可以分为以下几大类：如果记录数量很大，以致于内存无法容纳所有待排序记录，必须借助于外存进行排序，这种排序称为外部排序。如果内存可以容纳所有待排序记录，排序过程只涉及内存，这种排序称为内部排序。

①插入排序 ②交换排序 ③选择排序④归并排序 ⑤基数排序

这些不同类型的方法都有自己的适用范围，各有优缺点。⑴假设关键字均为整数，每个记录由关键字域和其他域组成。⑵用SqList

类型的变量L来表示待排记录序列，即把待排记录序列放在L的r数组中，r[0]空闲或作哨兵，length成员存放记录个数.⑶有时我们用R(K)表示关键字为K的记录，R(K)表示另一个关键字为K的记录。10.2插入排序一、直接插入排序直接插入排序的基本思想是：把数组L.r中的待排序的n个记录看成一个有序表和一个无序表，开始时有序表只包含r[1]，无序表包含r[2]～r[n]。接下来反复地做这样一件事：从无序表中取出第一个记录，把它插入到有序表的适当位置，使之成为新的有序表。k01234567L.rR(13)R(5)R(65)R(27)R(97)R(49)R(38)k01234567L.rR(5)R(65)R(27)R(97)R(49)R(38)R(13)这样经过n-1次插入后，无序表成为空表，有序表中就包含了全部记录。我们把每次插入一个记录的过程称为一趟排序。显然，用直接插入排序法对有n个记录的序列进行排序需要n-1趟。

下面对第i趟的插入过程做进一步的分析。

直接插入排序第i趟的任务是把r[i+1]插入有序表r[1]～r[i]中的适当位置，使之成为新的有序表。怎么完成呢？①把Ri+1暂存到r[0]中。k01…jj+1…ii+1…nL.rR1…Rj…Ri+1Ri-1RiRi+1②从有序表的最后一个记录r[i]

起，顺序向前查找首个≤

Ri+1

的记录，并且边比较边后移记录。③如果r[j]≤r[0]，则把要插入的记录Ri+1存储到r[j+1]。Rj+1下面对刚才的例子进行第3、4趟排序。k01234567L.rR(13)R(38)R(49)R(5)R(65)R(27)R(97)直接插入排序完整的排序过程如下：初始序列：[R(49)]，R(38)，R(13)，R(5)，R(65)，R(27)，R(97)i=1：

[R(38)，R(49)]，R(13)，R(5)，R(65)，R(27)，R(97)i=2：

[R(13)，R(38)，R(49)]，R(5)，R(65)，R(27)，R(97)i=3：

[R(5)，R(13)，R(38)，R(49)]，R(65)，R(27)，R(97)i=4：

[R(5)，R(13)，R(38)，R(49)，R(65)]，R(27)，R(97)i=5：

[R(5)，R(13)，R(27)，R(38)，R(49)，R(65)]，R(97)i=6：

[R(5)，R(13)，R(27)，R(38)，R(49)，R(65)，R(97)]直接插入排序根据上面的讨论，我们可以写出直接插入排序的算法。voidInsertSort(SqList&L){

for(i=1;i<L.length;i++){//i代表趟号

L.r[0]=L.r[i+1]; //设置哨兵

for(j=i;L.r[j].key>L.r[0].key);j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}//InsertSortk01234567L.rR(5)R(13)R(38)R(49)R(65)R(27)R(97)voidInsertSort(SqList&L){//算法10.1//对顺序表L作直接插入排序。

inti,j;for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){//"<"时，需将L.r[i]插入有序子表

L.r[0]=L.r[i];//复制为哨兵

for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//记录后移

L.r[j+1]=L.r[0];//插入到正确位置

}}//InsertSort在教材P265算法10.1中，i代表的是要插入的记录的下标，所以从2开始。另外，考虑到要插入的记录≥有序表中最后一个记录的情况，算法P265算法10.1做了进一步优化，增加了if语句。下面对直接插入排序法的性能进行分析。显然，比较和移动记录操作是基本操作。下面来考虑两种极端情况。k01234L.rR(60)R(53)R(28)R(5)当待排序的记录序列为逆序序列时，各趟所需比较和移动次数如下表所示。趟号比较次数移动次数123234………n-1nn+2合计此时，总的比较次数和移动记录次数，都分别达到了最大值。直接插入排序K01234L.rR(5)R(28)R(53)R(60)相反地，当待排序的记录序列为正序序列时，各趟所需比较和移动次数如下表所示。趟号比较次数移动次数110210………n-110合计n-10此时，总的比较次数和移动记录次数，都分别达到了最小值。

由此可以推断，当待排序的记录序列基本有序时，直接插入排序法会有较高的时间效率。综合以上分析，我们有如下结论：⑴直接插入排序法的时间复杂度为O(n2)；⑵直接插入排序法的空间复杂度为O(1)；⑷直接插入排序法在序列基本有序或n较小时具有较好性能。⑶直接插入排序法是稳定的排序方法；直接插入排序10.2插入排序二、折半插入排序折半插入排序也需要n-1趟。第i趟的任务也是把r[i+1]插入有序表r[1]～r[i]中的适当位置，使之成为新的有序表。k01234567L.rR(5)R(13)R(38)R(49)R(65)R(27)R(97)但是，与直接插入不同的是，它首先使用折半查找法来确定Ri+1的插入位置，然后再批量移动记录。k01…jj+1…ii+1…nL.rR1…RjRj+1…RiRi+1例一、用折半插入排序法对于如下序列排序。假设经过前4趟已经完成，下面演示第5趟排序。k01234567L.rR(5)R(13)R(38)R(49)R(65)R(27)R(97)折半插入排序根据上面的讨论，我们可以写出折半插入排序的算法。voidBInsertSort(SqList&L){

for(i=1;i<L.length;i++){//i代表趟号

L.r[0]=L.r[i+1]; //将r[i+1]暂存到r[0]

low=1;high=i;//设置初始查找区间

while(low<=high){m=(low+high)/2;if(L.r[0].key<L.r[m].key)high=m-1;//插入点在左半

elselow=m+1;//插入点在右半区间

}

for(j=i;j>=high+1;j--)L.r[j+1]=L.r[j];//记录后移

L.r[high+1]=L.r[0];//记录存入插入点high+1位置

}}//BInsertSort折半插入法虽然减少了关键字间的比较次数，但是记录的移动次数仍和直接插入法一样，因此，其时间复杂度仍为O(n2)。10.2插入排序三、希尔排序直接插入排序在n较小的时候，或在待排序列基本有序的情况下效果不错。正是基于这两点，1959年希尔提出了直接插入排序的改进方案--希尔排序。

例如，对此例可以设计增量序列为{5，3，1}。到底怎样一次次分割待排序列的呢？为此，我们设计一个递减的增量序列{d1，d2，…

，dt}

，其中，

d1>d2>…>dt，dt=1

下面结合例子介绍希尔排序的思想。k012345678910L.r49386597761327495504

希尔排序的主要思想是，把待排的序列分割成若干个子序列，对这些子序列分别进行直接插入排序。如此反复分割若干次，待整个序列变得基本有序时，再对所有记录进行一次直接插入排序。希尔排序⑴首先把待排序记录分为d1个组，以d1为步长，使下标距离为d1的记录在同一组中，并对每一组记录分别进行直接插入排序。k012345678910L.r[k]49386597761327495504增量序列{5，3，1}k012345678910L.r[k]13493827654997557604至此，完成了第1趟希尔排序。希尔排序⑵在第1趟排序的基础上，把记录序列分为d2个组，以d2为步长，使下标距离为d2的记录在同一组中，并对每一组记录分别进行直接插入排序。k012345678910L.r[k]13274955044938659776增量序列{5，3，1}k012345678910L.r[k]13495504654997387627至此，完成了第2趟希尔排序。如此重复，直到最后一趟。希尔排序⑶最后，在前面排序的基础上，把记录序列分为dt个组。由于dt=1,因此，所有记录被分在一个组中，接下来对所有记录进行直接插入排序。k012345678910L.r[k]13044938274955659776增量序列{5，3，1}k012345678910L.r[k]04132738494955657697至此，希尔排序过程结束。希尔排序由于巧妙利用了直接插入排序的长处，所以其效率应高于直接插入排序，它的时间复杂度约为O(n1.5)。另外，希尔排序的过程依赖于增量序列的选取，目前尚无最佳的增量序列的设计方法。最后，希尔排序又称为缩小增量排序，而且是不稳定的。10.2插入排序练习分别用直接插入排序和希尔排序法对下列关键字进行排序，写出每趟排序结果，其中希尔排序的增量为（3,1）

{21，25，49，25，16，08}10.3快速排序一、起泡排序本节主要讨论借助于“交换”手段进行排序的方法。起泡排序的思想很简单，它需要进行若干趟（不超过n-1趟）。在第i趟中，对于r[1]～r[n-i+1]间的记录，依次比较相邻记录r[j]、r[j+1]

，若出现逆序即r[j]>r[j+1]，则进行交换。如此重复，直到某趟中无逆序出现，或者n-1趟排序完成为止。例一、用起泡排序法对下面序列排序。k012…nL.rR1R2…Rn初始关键字49133865977627493813496597762749381349659776274938134965977627493813496576972749389749657613274938274965761397493827496597134997第一趟冒泡排序中间过程第一趟排序2749657613499738第二趟排序49496513277638第三趟排序654913274938第四趟排序1327494938第五趟排序27384913273813第六趟排序起泡排序对于“正序”的初始序列，起泡排序只需一趟排序，进行n-1次比较，0次记录交换。但是，对于“逆序”的初始序列，起泡排序要进行n-1趟，共进行n(n-1)/2次关键字比较，和同数量级的记录交换。因此，起泡排序法的时间复杂度为O(n2)。下面对起泡排序法的性能进行分析。显然，比较和交换记录是基本操作。下面来考虑两种极端情况。k01234L.rR(60)R(53)R(28)R(5)k01234L.rR(5)R(28)R(53)R(60)10.3快速排序二、快速排序假设初始序列如右图，快速排序的思想如下：k012…nL.rR1R2…Rn这样一来，序列就变成了下图的样子。它以某个位置i处的记录R1为界，被划分成了两部分，左半部分记录均≤R1，右半部分记录均≥R1。选择一个记录（比如R1）作为标尺；根据标尺对记录进行重排。凡是比R1小的记录都放在R1的左面,凡是比R1大的记录都放在R1的右面。k012…i-1ii+1…nL.rRk1Rk2…Rki+1R1Rki+1…Rkn这个过程称为一次划分或一趟快速排序。标尺被称为枢轴记录或支点，枢轴记录的关键字常称为pivotkey。可以看出，通过一趟快速排序，也使得枢轴记录找到了自己的最终位置。接下来，应分别对左半部分、右半部分继续进行划分，如此重复，直到每一部分仅包含一个记录为止。快速排序下面讨论一次划分的具体做法。假设待划分的部分为：k0…ss+1…t-1t…L.r…RksRks+1…Rkt-1Rkt…一次划分的具体过程如下：

⑴选择s处的记录L.r[s]为枢轴记录，置pivotkey=L.r[s].key。⑵将枢轴记录暂存到第0个分量。⑶令low=s、high=t，即分别指向待划分部分的首记录和尾记录。⑷从high所指的记录起向前搜索，直到第一个关键字＜pivotkey的记录，并将该记录移动到low所指位置；再从low所指的记录起向后搜索，直到第一个关键字＞pivotkey的记录，并将该记录移动到high所指位置。如此重复，直到low=high为止。⑸把枢轴记录复制到low所指位置。k012345678L.r4938659776132749下面通过例子来说明如何进行一趟快速排序。初始关键字49prikey一次交换二次交换三次交换四次交换完成一趟排序lowhigh4913386597762749652713389776492713389776496527381397766549279738137665492797381376654949lowlowhighhighlowhighhighlowhighlowhighhighlow快速排序根据上述分析，可以写出一次划分的算法。(P274算法10.6b)int

Partition(SqList&L,ints,intt){

pivotkey=L.r[s].key;//设置pivotkeyL.r[0]=L.r[s];//暂存到r[0]low=s;high=t;//设置首、尾指针

while(low<high){

while(low<high&&L.r[high].key>=pivotkey)--high;

L.r[low]=L.r[high];

while(low<high&&L.r[low]<=pivotkey)++low;

L.r[high]=L.r[low];}

L.r[low]=L.r[0];//把枢轴记录存到枢轴位置

returnlow;//返回枢轴位置}//Partition向左扫描向右扫描快速排序由刚才的例子可知，对上面的待排序列进行一次划分后，序列变成了：k012345678L.r4938659776132749首次划分结果：2738134976976549接下来，我们应再对这两部分分别进行快速排序，直到每一部分仅包含一个记录为止。132738497697654913273849496576971327384949657697最后结果：1327384949657697综上所述，对整个初始序列进行快速排序，就是先用一次划分将整个序列一分为二，然后分别对左子表、右子表进行划分，…，直到每一部分只包含一个记录为止。快速排序根据上述分析，可以写出快速排序的算法(P276算法)。voidQSort(SqList&L,ints,intt){

if(s>=t)return;//若区间长度≤1，不再划分

pivotloc=Partition(L,s,t);//划分且得到枢轴位置

QSort(L,s,pivotloc-1);//对左子表继续划分

QSort(L,pivotloc+1,t);//对右子表继续划分}//QSortvoidQuickSort(SqList&L){

QSort(L,1,L.length);//对区间[1,n]调用QSort}//QuickSort快速排序理论上已经证明，快速排序的平均时间为O(nlogn)。实际应用表明，就平均时间而言，快速排序被认为是最好的内部排序方法。但是，关于快速排序还要注意以下几点：当初始序列为基本有序时，快速排序就蜕化为起泡排序。快速排序不稳定，例如{R(20)，R(10)，R(10)}。与其他排序法相比，快速排序需要额外的栈空间，空间复杂度为O(logn)。例三、用快速排序法对序列(18，5，23，40，13，9)排序，要求写出每次划分后的结果和最后结果。{9，5，13}，18，{40，23}{5}，9，{13}{23}，40最后结果：

5，9，13，18，23，4010.4选择排序一、简单选择排序第i趟排序是在n-i+1各记录中选出关键字最小的记录，并和第i个记录交换。若待排记录序列的长度为n，则简单选择排序共需进行n-1趟。在进行第i趟时，首先从r[i]～r[n]中选取最小的记录（例如r[j]）,然后把r[i]与r[j]交换。k01…i-1i…j…nL.rR1…Ri-1……RnRi例一、用简单选择排序法对下面的序列排序。

Rjk012345678L.r4938659776132749第1趟：1338659776492749第2趟：1327659776493849第3趟：1327389776496549可以看出，在进行第i趟时，r[1]～r[i-1]已经有序。简单选择排序根据上面的讨论，我们可以写出简单选择排序的算法。voidSelectSort(SqList&L){

for(i=1;i<L.length;i++){//i代表趟号

j=i; //选取r[i]~r[n]中的最小记录r[j]

for(k=i+1;k<=L.length;k++)

if(L.r[k].key<L.r[j].key)j=k;

L.r[i]←→L.r[j];//r[j]与r[i]交换

}}//SelectSort简单选择排序下面对简单选择排序的性能进行分析。容易看出，在简单选择排序中，比较和记录交换是基本操作。趟号比较次数交换次数1n-112n-21………n-111合计n-1总之，简单选择排序需要交换n-1次记录，需要比较n(n-1)/2次。因此,该算法的时间复杂度为O(n2)。另外，简单选择排序的空间复杂度为O(1)，它是不稳定的排序方法。现在来考虑这样一个问题，即能否对简单选择排序加以改进呢？由以上分析不难看出，要想改进这个算法，就得从减少比较次数上下功夫。n-1次，第2趟比较了n-2次。实际上，在进行第2趟排序时，如果能够利用第1趟比较所得信息，第2趟就不用比较这么多次。类似地，在进行第i趟排序时，如果能够利用前些趟比较所得信息，那么第i趟的比较次数就可以减少。

基于这种想法，人们设计出了树形选择排序。在简单选择排序中，第1趟比较了10.4选择排序二、树形选择排序若待排记录序列的长度为n，则树形选择排序也需进行n-1趟。与简单选择排序类似，第1趟选取最小的记录，第2趟选取次小的记录，…，下面结合例子（P280）来介绍。例一、用树形选择排序法对下面的序列排序。（49，38，65，97，76，13，27，49）

首先进行第1趟，即选取最小的记录。为此，把待排序记录都作为最下层的叶子结点，并将叶子结点两两比较，直到求出最小值,并输出最小值(13)。13492713769765384938386513271310.4选择排序二、树形选择排序若待排记录序列的长度为n，则树形选择排序也需进行n-1趟。与简单选择排序类似，第1趟选取最小的记录，第2趟选取次小的记录，…，下面结合例子（P280）来介绍。例一、用树形选择排序法对下面的序列排序。（49，38，65，97，76，13，27，49）

然后进行第2趟，即选取次小的记录。为此，只需把最小值叶子结点(13)用∞代替，重新进行比较，而且只需调整祖先结点，其他结点保持不变。274927∞

769765384938386527277610.4选择排序二、树形选择排序若待排记录序列的长度为n，则树形选择排序也需进行n-1趟。与简单选择排序类似，第1趟选取最小的记录，第2趟选取次小的记录，…，下面结合例子（P280）来介绍。例一、用树形选择排序法对下面的序列排序。（49，38，65，97，76，13，27，49）

接下来进行第3趟，即选取第3小的记录。为此，只需把次小叶子结点(27)用∞代替，重新进行比较，且只需调整祖先结点，其他结点保持不变。经过n-1趟后，就得到了有序的序列。3849∞∞

7697653849383865494976树形选择排序下面对树形选择排序的性能进行分析。由例子可以看出，除了第1趟求最小记录外，其它各趟只需比较3次，即树的高度-1次。由于具有n个叶子结点的完全二叉树的高度为┌log2n┐+1，所以除第1趟外，其它各趟仅需比较┌log2n┐次，因此，树形选择排序的时间复杂度为O(nlog2n)。

由此可见，树形选择排序在进行第i趟时，由于充分利用了其它趟的比较结果，使得效率得以提高。但是它也有缺点，需要较多的辅助空间来保存中间结果。于是，人们又提出了改进方案即堆排序，堆排序的时间复杂度依然为O(nlog2n)，但只需一个记录大小的辅助空间。10.4选择排序三、堆排序则称之为堆。进一步地，前一种称为小顶堆，后一种称为大顶堆。为了介绍堆排序，先来复习一下完全二叉树的知识。或者一个序列（k1，k2，…，kn），如果满足：一棵有n个结点的二叉树，如果它与同深度的满二叉树的前n个结点一一对应，则该二叉树被称为完全二叉树。完全二叉树非常适于用顺序存储表示，方法是按照层序依次将结点存放在数组中。这样一来，每个完全二叉树对应一个序列。另外，有n个叶子结点的完全二叉树的高度为┌log2n┐+1。

小顶堆：(12，36，24，85，47，30，53，91)

大顶堆：(96，83，27，38，11，9)堆排序

小顶堆：(12，36，24，85，47，30，53，91)

大顶堆：(96，83，27，38，11，9)如果把这样一个序列，看成是某个完全二叉树所对应的序列，那么这棵二叉树画出来如右图所示。96832738119所有大顶堆对应的二叉树都具有此特点。由此联想到，如果从一个无序序列所对应的二叉树出发，通过某些操作把它调整成一个大顶堆的话，则堆顶记录即为最大值。另外，在输出了最大值之后，如果能将剩下的n-1个记录调整成一个新堆的话，则堆顶记录即为次大值。如此反复，就能得到一个有序序列，这个过程称为堆排序。不难看出，它具有如下特点：

任一分支结点的值≥其左、右孩子的值；左、右子树仍为大顶堆；堆顶记录就是序列中的最大值。堆排序具体地说，堆排序的操作步骤如下（为了保证输出序列为按关键字非递减有序，采用大顶堆排序）：⑴把待排记录序列调整成一个大顶堆；⑵把堆顶记录与堆中最后一个记录交换；⑶将剩下的记录调整为新的大顶堆；⑷重复⑵、⑶，直到堆中只剩一个记录为止。例一、用堆排序法对下面的序列排序。k012345678L.r4938659776132749它所对应的二叉树如右上图所示。4938659776132749

如何由此二叉树出发得到一个大顶堆呢？由于大顶堆要求结点的值≥其左、右孩子的值，为此需要依次对每个分支结点进行自上而下的调整。堆排序⑴把待排记录序列调整成一个大顶堆；⑵把堆顶记录与堆中最后一个记录交换；⑶将剩下的记录调整为新的大顶堆；⑷重复⑵、⑶，直到堆中只剩一个记录为止。①首先从从i=L.length/2开始，自底向上构建大顶堆k012345678L.r493865977613274949386549977613274938654997761327初始排序码集合49386549977613274938654997761327i=4时的局部调整49386549977613274938654997761327堆排序⑴把待排记录序列调整成一个大顶堆；⑵把堆顶记录与堆中最后一个记录交换；⑶将剩下的记录调整为新的大顶堆；⑷重复⑵、⑶，直到堆中只剩一个记录为止。①首先从从i=L.length/2开始，自底向上构建大顶堆k012345678L.r493865977613274949386549977613274938654997761327i=3时的局部调整49386549977613274938654997761327堆排序⑴把待排记录序列调整成一个大顶堆；⑵把堆顶记录与堆中最后一个记录交换；⑶将剩下的记录调整为新的大顶堆；⑷重复⑵、⑶，直到堆中只剩一个记录为止。①首先从从i=L.length/2开始，自底向上构建大顶堆k012345678L.r4938659776132749i=2时的局部调整4938654997761327493865499776132749976549387613274997653849761327堆排序⑴把待排记录序列调整成一个大顶堆；⑵把堆顶记录与堆中最后一个记录交换；⑶将剩下的记录调整为新的大顶堆；⑷重复⑵、⑶，直到堆中只剩一个记录为止。①首先从从i=L.length/2开始，自底向上构建大根堆k012345678L.r493865977613274997766538494913274997653849761327i=1时的局部调整9749653849761327堆排序⑴把待排记录序列调整成一个大顶堆；⑵把堆顶记录与堆中最后一个记录交换；⑶将剩下的记录调整为新的大顶堆；⑷重复⑵、⑶，直到堆中只剩一个记录为止。②接下来把堆顶记录97与堆中最后一个记录38交换，这样97找到了它的最终位置。766549491327L.r3876654949132797①首先从最后一个分支结点97开始，自底向上构建大根堆4938659776132749k012345678L.r4938659776132749L.r97766549491327389738堆排序⑴把待排记录序列调整成一个大顶堆；⑵把堆顶记录与堆中最后一个记录交换；⑶将剩下的记录调整为新的大顶堆；⑷重复⑵、⑶，直到堆中只剩一个记录为止。④接下来把堆顶记录76与堆中最后一个记录27交换，这样76找到了它的最终位置。3876654949132797L.r2749653849137697③为了把剩下的n-1个记录调整为新的大顶堆，下面从堆顶开始进行自上而下的调整，调整后的大顶堆如图所示。L.r76496538491327977627L.r3876654949132797496538491397堆排序⑴把待排记录序列调整成一个大顶堆；⑵把堆顶记录与堆中最后一个记录交换；⑶将剩下的记录调整为新的大顶堆；⑷重复⑵、⑶，直到堆中只剩一个记录为止。⑥接下来把堆顶记录65与堆中最后一个记录13交换，这样65找到了它的最终位置。2749653849137697L.r1349273849657697⑤为了把剩下的n-2个记录调整为新的大顶堆，下面从堆顶开始进行自上而下的调整，调整后的大顶堆如图所示。L.r65492738491376976513492738497697L.r2749653849137697堆排序L.r1327384949657697我们把自根到叶子结点的调整过程称为筛选。由于在每次筛选过程中，仅需一个辅助记录单元来完成记录交换,所以，堆排序的空间复杂度为O(1)。

另外，堆排序的时间复杂度为O(nlog2n)，即使在初始序列基本有序情况下也是如此，而快速排序此时为O(n2)。如此重复，直到堆中只剩一个记录为止。1327384949657697堆排序适宜记录较多的文件10.5归并排序因此，归并操作的时间复杂度为O(m+n)，空间复杂度为O(m+n)。归并排序是利用归并操作完成的。归并操作的功能在于将两个有序表合并为一个更长的有序表。下面以顺序存储结构为例，回顾一下归并操作。由此可以看出，若两个有序表的长度分别为m、n，为了把它们归并为一个有序表，需要大约进行m+n次比较和m+n次记录移动，另外还需要m+n个记录的辅助空间来存放归并结果。如果把归并操作的思想用于排序，就形成了归并排序方法。012301234a13911b28101416012345678c123891011141610.5归并排序在经过了3趟归并排序之后，就得到了有序序列。一般地，若待排序的记录序列长度为n，则需要进行┌log2n┐趟。由于在每趟归并排序中，需要比较n次，所以归并排序的时间复杂度为O(nlog2n)。下面通过例子来加以说明。假设待排序的记录序列如下，由于每个记录可看成是长度为1的有序子序列，所以，可以对它们进行两两归并。由于在进行归并排序时，需要长度为n的数组暂存每一趟的归并结果，所以归并排序的空间复杂度为O(n)。49，38，65，97，76，13，2738，4965，9713，7627第1趟后结果38，49，65，9713，27，76第2趟后结果13，27，38，49，65，76，97第3趟后结果10.5归并排序由前面的例子可以看出，当用归并排序对下面的序列排序时，k012…n-1nL.rR1R2…Rn-1Rn其核心操作是把数组L.r中前后相邻的两个有序序列（如r[s]～r[m]与r[m+1]～r[t]）归并为一个有序序列，P284算法10.12给出了该操作的实现算法Merge。k0…s…mm+1…t…L.r…Rs…RmRm+1…Rt…利用Merge函数，可以写出归并排序的完整算法，参见P284算法10.13和算法10.14。虽然快速排序、堆排序、归并排序的平均时间均为O(nlog2n)，但是，只有归并排序是稳定的排序方法。10.6基数排序对于关键字为278，109，013，930，589，184，505，269，018，083或者为WORK，HEAD，FOUR，TEAM，BELL，…的记录序列，除了用前面介绍的各种排序方法外，使用基数排序法可能会得到更高的效率。下面首先来分析这些关键字序列的特点。基数排序是一种按组成关键字的各位进行排序的方法。每个关键字由d位组成，其中k1为最高关键字位，kd为最低位。k1k2…kd各位的地位不同，当比较两个关键字时，是从最高位起开始比较,若相同则比较下一位，…，直到最低位。

k1～kd有同样的取值范围，如第1个序列为0～9，共10个数，这个10称为基数，基数常用rd表示。对这种记录序列的排序有两种思路。10.6基数排序下面以关键字序列278，109，013，930，589，184，505，269，018，083为例加以说明，此时d=3，rd=10。一、最高位优先法(MSD)0123456789278109013930589184505269018083⑴按最高关键字位即百位将记录分堆，每堆内记录的关键字具有相同的百位。⑵在每堆中，再按十位分成10个子堆，每个子堆内具有相同的十位。0123456789013018083⑶在每个子堆中，再按个位分堆。012345678901301810.6基数排序0…90…9至此，如果把最下层中的记录按顺序排列起来，就得到了有序序列。可以看出，MSD是按关键字位逐层分成若干子堆，而每堆的排序是独立进行的。0…90…90…9…………0…90…9……按k1按k210.6基数排序下面以关键字序列278，109，013，930，589，184，505，269，018，083为例加以说明，此时d=3，rd=10。二、最低位优先法(LSD)0123456789278109013930589184505269018083⑴按最低关键字位即个位将记录分成若干堆，每堆内具有相同的个位.⑵按顺序将各堆数据收集在一起，得到：⑶将新序列按十位分成若干堆，每堆内具有相同的十位。930，013，083，184，505，278，018，109，589，2690123456789278109013930589184505269018083⑷按顺序将各堆数据收集在一起，得到：505，109，013，018，930，269，278，083，184，58910.6基数排序⑸将新序列按百位分成若干堆，每堆内具有相同的百位。0123456789278109013930589184505269018083⑹按顺序将各堆数据收集在一起，得到：013，018，083，109，184，269，278，505，589，930505，109，013，018，930，269，278，083，184，589至此，得到的序列就是有序序列。

由此可以看出，LSD方法是一个分配和收集交替进行的过程，分配和收集的次数取决于关键字的位数d。10.6基数排序基数排序法就是基于LSD原理实现的。在基数排序法中，待排记录序列保存在静态链表中；需要进行d次分配与收集工作;

为了记录分配结果，建立了rd个链队列，f[i]、e[i]分别表示第i个队列的队头、队尾指针。下面结合P287图10.14的例子来介绍基数排序法。在本例中，由于每个关键字有d=3位，所以要进行3次分配与收集工作，又因为基数rd=10，所以需要建立10个链队列。例：初始状态：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]