《数据结构》课件第9章

第9章排序9.1排序的基本概念9.2插入排序9.3交换排序9.4选择排序9.5归井排序9.6基数排序9.7排序算法本章小结习题九实训9-1内部排序算法时间复杂度分析实训9-2排序算法的应用

【教学目标】通过对本章的学习，要求掌握排序的基本概念；熟练掌握直接插入排序、直接选择排序、冒泡排序、快速排序，掌握希尔排序、堆排序、归并排序、基数排序的基本思想、排序过程及实现算法；了解各种排序方法的稳定性与时间复杂度。排序(Sorting)是计算机程序设计中的一种重要操作，也是日常生活中经常遇到的问题，如高考录取按总分从高到低进行，奥运跨栏决赛按成绩由快到慢排定名次，都是按某种次序进行的。排序就是将一组无序的序列按指定的关键字重新排列成一个有序的序列。排序的方法很多，本章只介绍一些常用的排序方法及实现算法。9.1排序的基本概念9.1.1排序从上一章的讨论中容易看出，为了查找方便，通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以采用查找效率较高的折半查找法，其平均查找长度为O(log2n),而无序的顺序表只能进行顺序查找，其平均查找长度为(n+1)/2。又如建造二叉排序树的过程本身就是一个排序的过程。例如，表9-1为某班学生考试情况表，表中每个学生的情况包括学号、姓名、三门课的考试成绩以及这三门课的平均成绩。表9-1学 习 成 绩 表如果希望按学号对学生考试成绩表进行排序，则学号就是其排序关键字；如果希望按考试的平均成绩对该表进行排序，则平均成绩就是其排序关键字。可见，数据元素序列的排序可以根据实际需要，选取其任一数据项作为排序关键字。所谓排序，就是对于有n个记录的序列：{R1，R2，…，Rn}其相应关键字的序列是：{K1，K2，…，Kn}通过排序，找出当前下标序列为1，2，…，n的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减(或非递增)关系，即：Kp1≤Kp2≤…≤Kpn这样就得到一个按关键字有序的记录序列：{Rp1，Rp2，…，Rpn}9.1.2稳定排序与不稳定排序假定待排序的序列中存在多个记录具有相同的键值。若经过排序，这些记录的相对次序仍然保持不变，即对任意两个键值相同的记录在无序序列中Ki=Kj，且i＜j，而在排序后的序列中Ri仍在Rj之前，则称这种排序方法是稳定的，否则称为不稳定的。无论是稳定排序还是不稳定排序，均能排好序。在应用排序的某些场合，如选举和比赛等，对排序的稳定性是有特殊要求的。需要强调的是，证明一种排序方法是稳定的，要从算法本身的步骤中加以证明，而证明排序方法是不稳定的，只需给出一个反例说明即可。例如，一组记录对应的关键字序列为(2，27，36，8，6，8*)，可以看出，关键字8的记录有两个(第二个加*以示区别)。若采用一种排序方法得到结果序列(2，6，8，8*，27，36)，那么这种排序方法是稳定的；若采用另一种排序方法得到结果序列(2，6，8*，8，27，36)，那么这种排序方法是不稳定的。9.1.3内部排序和外部排序根据排序过程中所使用的存储设备的不同，排序可以分成内部排序(InternalSorting)和外部排序(ExternalSorting)两大类。内部排序是指在排序的整个过程中，数据全部存放在计算机的内存储器中，并且在内存储器中调整记录间的相对位置，在此期间没有进行内、外存储器的数据交换。外部排序是指在排序的过程中，数据的主要部分存放在外存储器上，借助于内存储器逐步调整记录之间的相对位置，在这个过程中，需要不断地在内、外存储器之间进行数据的交换。本章仅讨论内部排序的各种典型方法和算法。内部排序的方法有很多，按照采用的策略不同，主要有插入排序、交换排序、选择排序、归并排序和基数排序五类。为了讨论方便，假设待排记录的关键字均为整数，且都采用顺序存储，均从数组中下标为1的位置开始存储，下标为0的位置存储监视哨，或空闲不用。下面用C语言描述：#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey; /*关键字项*/

OtherTypeother-data; /*其他数据项*/}RecordType; /*记录类型*/typedefstruct{RecordTyper[MAXSIZE+1];

/*r[0]闲置或用作监视哨*/intlength; /*顺序表长度*/}Sqlist;9.2插入排序插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。打扑克牌时的抓牌就是插入排序的一个很好的例子，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。常用的插入排序算法有直接插入排序、折半插入排序和希尔排序三种。9.2.1直接插入排序

1.直接插入排序的基本思想直接插入排序(StraightInsertionSort)是一种最基本的插入排序方法，其基本操作是将第i个记录插入到前面i-1个已排好序的记录中。具体过程为：将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1，Ki-2，…，K1进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。完整的直接插入排序是从i = 2开始的，也就是说，将第1个记录视为已排好序的单元素子集合，然后将第2个记录插入到单元素子集合中，i从2循环到n，即可实现完整的直接插入排序。

2.直接插入排序举例

例9.1

关键字序列(15，8，27，21，40，27*，48)用直接插入排序的过程如图9.1所示。图9.1直接插入排序过程示意图由此可见，对有n条记录的序列进行直接插入排序，需重复以下步骤n-1次：

(1)根据关键字值的大小，查找插入位置。

(2)插入记录。

3.直接插入排序算法假设待排序记录存放在r[1],r[2],…,r[n]之中，为了提高效率，附设一个监视哨r[0]，使得r[0]始终存放待插入的记录。监视哨的作用有两个：一是备份待插入的记录，以便前面关键字较大的记录后移；二是防止越界。直接插入排序算法用C语言描述如下：voidInsertSort(RecordTyper[],intn)

/*用直接插入排序方法对r[1]，…，r[n-1]进行排序*/{

inti,j

for(i=2;i<=n;i++)

{r[0]=r[i]; /*将待插入记录存放到r[0]中*/for(j=i-1;r[0].key<r[j].key;j--) /*寻找插入位置*/

r[j+1]=r[j];r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/

}}该算法的要点是：①使用监视哨r[0]临时保存待插入的记录；②从后往前查找应插入的位置；③查找与移动在同一循环中完成。

4.直接插入排序算法分析从空间角度来看，它只需要一个辅助空间r[0]。从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。对于一次插入排序，算法中的while循环的次数主要取决于待插记录与前i-1个记录的关键字的关系。分两种情况来考虑：

(1)原始序列中各记录已经按关键字递增的顺序有序排列(顺序)。在这种情况下，while循环次数为零，因此在一次排序中，关键字的比较次数为1，记录的移动次数为2(r[0] = r[i]和r[j + 1] = r[0])，整个序列的排序所需的记录关键字比较次数以及记录的移动次数分别为比较次数 = n-1

移动次数 = 2(n-1)

(2)原始序列中各记录按关键字递减的顺序逆序排列(逆序)。在这种情况下，第i次排序时，while的循环次数为i，因此关键字的比较次数为i + 1，记录的移动次数为(i + 2)，整个序列排序所需的关键字比较次数以及记录的移动次数分别为比较次数 = ∑(i + 1) = (n-1)(n-2)/2移动次数 = ∑(i + 2) = (n-1)(n + 4)/2上述两种情况是最好和最坏的两种极端情况。可以证明，原始序列越接近有序，该算法的效率也越高，如果原始序列中各记录的排列次序是随机的，则关键字的期望比较次数和记录的期望移动次数均约为n2/4，因此，直接插入排序的时间复杂度为O(n2)。从算法的空间复杂度来看，在整个排序过程只需一个记录的辅助空间，所以其空间复杂度为O(1)。这种排序方法是稳定的。直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能就不好，为此，可以对直接插入排序做进一步的改进。在直接插入排序法的基础上，从减少“比较关键字”和“移动记录”两种操作的次数着手来进行改进。9.2.2折半插入排序对于直接插入排序，在将第i个记录插入适当位置的操作中，首先要在第1个记录至第i-1个记录中找到第i个记录应当插入的位置。实际上前i-1个记录已经是一个有序表，所以在查找第i个记录的插入位置时，可以采用“折半查找”方法来实现，用这种方法进行的插入排序称为折半插入排序(BinaryInsertionSort)。折半插入排序算法用C语言描述如下：voidBinSort(RecordTyper[],intn)/*用折半插入排序方法对r[1]，…，r[n-1]进行排序*/{

intlow,high,mid,i,j

for(i=2;i<=n;++i)

{r[0]=r[i]; /*r[i]暂存在r[0]中*/low=1;high=i-1;while(low<=high) /*确定插入位置*/{

mid=(low+high)/2;if(r[0].key<r[mid].key)

high=mid-1;

else

low=mid+1;

}

for(j=i-1;j>=low;--j)r[j+1]=r[j];

/*记录依次向后移动*/

r[low]=r[0]; /*插入记录*/

}}折半插入排序比直接插入排序有效。为确定r[i]的插入位置，最多只需要比较log2i次，总的比较次数最多为log22 + log23 + … + log2n = log2n!。而log2n!≤nlog2n，因此插入n-1个元素的平均关键字的比较次数为O(nlog2n)。虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。显然，折半插入排序的空间复杂度为O(1)。折半插入排序是一种稳定的排序方法。9.2.3希尔排序

1.希尔排序的基本思想希尔排序(Shell’sSort)又称做缩小增量排序(DiminishingIncrementSort)，是D.L.Shell在1959年提出的一种排序方法。从对直接插入排序的分析得知：

(1)原始序列接近有序，其时间复杂度可提高至O(n)；

(2)当n的值较小时，效率也比较高。希尔排序正是从这两点分析出发对直接插入排序进行改进得到的一种插入排序方法。它的基本思想是：把待排序的序列分成若干小组，对同一组内的数据元素采用直接插入排序方法进行排序，在分组时，始终保证当前组的数据元素个数超过前面分组排序时组内数据元素的个数，直至最后所有数据元素成为一组。一般情况下，具体的作法是：先设置一个增量h1=

n/2

，将待排序序列中所有间隔为h1的元素放在同一组中，然后对各组内元素分别进行直接插入排序；再设置一个增量h2 = 

h1/2

，将待排序序列中所有间隔为h2的元素放在同一组中进行排序；依此类推，h3=

h2/2

,…,直至hi=1(i=1，2，…，log2n)为止。

2.希尔排序举例

例9.2

关键字初始序列为(15，27，8，21，40，21*，10，36，30，17，32，25)，采用希尔排序方法，过程如图9.2所示。图9.2希尔排序过程示意

3.希尔排序算法及分析进行一趟希尔排序的算法与一趟直接插入排序相比，做了如下修改：前后记录位置的增量是h，而不是1；r[0]只是暂存单元，而不是监视哨。当j≤0时，插入位置已找到。希尔排序算法用C语言描述如下：voidShellSort(RecordTyper[],intn)/*用希尔排序方法对r[1],…,r[n]进行排序,r[0]为暂存单元*/{

inti,j,h;

h=n/2; /*增量置初值*/

while(h>0) /*增量为正整数，其最小值为1*/{

for(i=h+1;i<=n;i++) /*h+1为第一个子序列的第二个元素的下标*/

if(r[i].key<r[i-h].key)

{

r[0]=r[i]; /*备份r[i](不做监视哨)*/

for(j=i-h;j>0&&(r[0].key<r[j].key);j=j-h)

r[j+h]=r[j];

r[j+h]=r[0];}

h=h/2; /*减小增量*/

}}希尔排序算法的速度取决于所选增量hi。增量序列的选取到目前为止没有一个最佳值，但不管hi的值如何选取，最后一个值必须是1，因此，希尔排序算法的时间复杂度的估算比较复杂，大量研究说明，希尔排序算法的时间复杂度在O(nlog2n)～O(n2)之间。希尔排序适合于中等规模的记录序列进行排序的情况。由图9.3可知，希尔排序是一种不稳定的排序。9.3交换排序交换排序的基本思想是：两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对，直到全部满足为止。常用的交换排序算法有冒泡排序和快速排序两种。9.3.1冒泡排序冒泡排序(BubbleSort)又称为相邻比序法，以递增排序为例，其基本思想是：将相邻的数据元素的关键字进行比较，若前面元素的关键字大于后面元素的关键字，则将它们互换，否则不交换。

例9.3

无序关键字序列(763246805546*)，用冒泡法排序过程如图9.3所示。由图9.3可知，n个元素要进行n-1趟排序，但若在一趟排序中相邻元素进行比较时没有交换发生，则可认为已经排好序了。图9.3冒泡排序过程(a)第一趟冒泡排序过程及结果；(b)各趟冒泡排序结果冒泡排序算法用C语言描述如下：

voidBubbleSort(RecordTyper[],intn)

/*用冒泡排序法对r[1],…,r[n]进行排序*/

{

int,i,m,flag；

flag=1； /*标志量。交换发生时为1*/

m=n; /*每趟排出的最大值存放的位置，也就是每趟参与排序的元素个数*/

while(m>1&&flag){

flag=0；

for(i=1；i<m；i++)

if(r[i].key>r[i+1].key)

{

flag=1；

r[0]=r[i]；

r[i]=r[i+1]；

r[i+1]=r[0]；

} m--;

}}在该函数中，待排序序列中n个记录顺序存储在r[1],…,r[n]中，r[0]用作临时存储空间，外层for循环控制排序的执行次数，内层for循环用于控制在一次排序中相邻记录的比较和交换。flag为标志量，当flag = 1时，表明在一次排序过程中，至少进行了一次记录的交换，反之，当flag = 0时，则表明在前次排序过程中，没有任何记录交换位置，排序结束。冒泡排序的时间复杂度为O(n2)，它是一种稳定的排序方法。9.3.2快速排序

1.快速排序的基本思想图9.4快速排序中表的分割快速排序(QuickSort)是冒泡排序的一种改进方法。其基本思想是：从待排序序列中选取一个记录T(通常可选第一个记录)，然后将T的关键字和待排序序列中其余记录的关键字进行比较，关键字小的记录移到T的前面，关键字大的记录移到T的后面。经过一趟比较后就将待排序序列分成了两部分(称为两个子表)，T记录就是这两个子表的分界线，前面子表中的所有记录的关键字均不大于T的关键字，而后面子表中的所有记录的关键字均不小于T的关键字。继续对分割后的各子表按上述原则进行分割，直到所有子表只有一个记录为止，则此时的排序序列就变成了有序表。这个过程如图9.4所示。图9.4快速排序中表的分割在对待排序序列或子表进行分割时，可以按如下步骤进行：首先，选取表中的第一个元素(也可选取表中的其它某个元素作为分割表的基准)，并将该元素赋给临时变量T。然后设置两个指针i和j分别指向表的起始与最后的位置。反复做以下两种操作：

(1)将j逐渐减小，并逐次比较r(j)与T，直到发现一个r(j)＜T为止，并将r(j)移到r(i)的位置上。

(2)将i逐渐增大，并逐次比较r(i)与T，直到发现一个r(i)＞T为止，将r(i)移到r(j)的位置上。上述两个操作交替进行，直到指针i与j指向同一个位置(即i==j)为止，此时将T移到r(i)的位置上。

2.快速排序举例

例9.4

关键字值序列为(48,62,35,77,55,14,35,98)，快速排序过程如图9.5所示。图9.5快速排序示例(a)一趟快速排序；(b)快速排序全过程

3.快速排序算法及分析快速排序中一趟排序的算法用C语言描述如下：intsplit(RecordTyper[],intm,intn)/*对记录r[m]，…，r[n]进行分割，返回分界线位置*/{

inti,j；

RecordTypet；

i=m；

j=n；

t=r[i]； /*选择基准记录*/

while(i<j)

{while((i<j)&&(r[j].key>=t.key))

/*j从右到左找小于t.key的记录*/j=j-1；

if(i<j)

/*找到小于t.key的记录，则进行交换*/{

r[i]=r[j]；

i=i+1；}while((i<j)&&(r[i].key<=t.key))

/*i从左到右找大于t.key的记录*/

i=i+1；if(i<j) /*找到大于t.key的记录，则进行交换*/{ r[j]=r[i]；

j=j-1；

}}

r[i]=t；/*将基准记录保存到i=j的位置*/

return(i)；/*返回基准记录的位置*/}快速排序算法用C语言描述如下：voidQkSort(RecordTyper[],intm,intn,)/*对记录r[m],…,r[n]用快速排序算法进行排序*/{inti；

if(m<n)/*子表不空*/

{

i=split(r,m,n)； /*分割*/QkSort(r,m,i–1)； /*对前面子表进行快速排序*/QkSort(r,i+1,n)； /*对后面子表进行快速排序*/

}}在冒泡排序中，记录的比较和交换是在相邻的单元中进行的，记录每次交换只能上移或下移一个位置，故总的比较和移动次数较多。而在快速排序中，记录的比较和交换是从两端向中间进行的，当前记录“总是和与它相距最远的且没有比较过的记录”相比较，记录移动的距离较远，故可减少总的比较次数和移动次数。快速排序的平均时间复杂度为O(nlog2n)。但是若初始记录序列按关键字有序或基本有序时，快速排序将蜕变为冒泡排序，其时间复杂度为O(n2)。当n较大时，快速排序是目前为止在平均情况下速度最快的一种排序方法。它是一种不稳定的排序方法。9.4选择排序选择排序的基本思想是：每步从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列的最后，直到全部排完为止。选择排序算法最常用的有两种：直接选择排序和堆排序。9.4.1直接选择排序直接选择排序(StraightSelectionSort)是一种最简单的排序方法。它的基本思想是：首先在待排序的所有记录中选出关键字最小的记录，把它与第一个记录进行交换，然后在其余的记录中再选出关键字最小的记录与第二个记录进行交换。依此类推，直至所有记录排序完成。有n个数据元素，必须要重复n-1趟选择，其中第i(i = 1,2,…,n-1)趟选择过程如下：

(1)在待排序序列(r[i]，…，r[n])中选择关键字最小的元素r[k]。

(2) r[k]与待排序序列的第一个元素r[i]交换位置。

例9.5

初始关键字序列为(15，27，8，21，40，21*，10，36)，直接选择排序过程如图9.6所示。方括号内表示待排序的数据。图9.6直接选择排序示意直接选择排序算法用C语言描述如下：voidSelectSort(RecordTyper[],intn)/*用直接选择排序方法对r[1],…,r[n]进行排序*/{

inti,j,k；

for(i=1；i<n；i++)

{

k=i；

for(j=i+1；j<=n；j++)

if(r[j].key<r[k].key)

k=j；

if(k!=i){r[0]=r[i]； /*r[0]用作临时变量，交换r[i]和r[k]*/r[i]=r[k]；

r[k]=r[0]；

}

}}从算法中可以看出，在直接选择排序中，第一次排序要进行n-1次比较，第二次排序时要进行n-2次比较，…，所以总的比较次数为

(n-1) + (n-2) + … + 1 = (n-1)n/2由此可知，直接选择排序的时间复杂度为O(n2)。直接选择排序是一种稳定的排序。9.4.2堆排序堆排序(HeapSort)是在直接选择排序法的基础上借助完全二叉树结构而形成的一种排序方法。在直接选择排序中，为找出关键字最小的记录，需要做n-1次比较，然后为寻找关键字次小的记录要对剩下的n-1个记录进行n-2次比较。在这n-2次比较中，有许多次比较在第一次排序的n-1次比较中已做过了。事实上，直接选择排序的每次排序除了找到当前关键字最小的记录外，还产生了许多比较结果信息，这些信息在以后的各次排序中还有用，但由于没有保存这些信息，因此每次排序都要对剩余的全部记录的关键字重新进行一遍比较，这样大大增加了时间开销。堆排序是针对直接选择排序所存在的上述问题而形成的一种改进方法。它在寻找当前关键字最小的记录的同时，还保存了本趟排序过程所产生的其它比较信息。

1.堆的概念堆的定义：具有n个元素的序列(R1，R2，…，Rn)，相应的关键字序列(K1，K2，…，Kn)当且仅当满足或(i=1,2,…,n/2)时称之为堆，前者称为大根堆，后者称为小根堆。由堆的定义可以看出，堆顶元素(即第一个元素)必为最大值(或最小值)。在实际处理中，可以用一维数组存储堆序列中的元素，也可用完全二叉树直观地表示堆的结构。例如，序列(98，77，35，62，55，14，35，48)是一个大根堆，序列(14，48，35，62，55，98，35，77)是一个小根堆，它们所对应的完全二叉树如图9.7所示。在用完全二叉树表示堆时，树中的所有非叶子结点的关键字值均不小于(或不大于)其左、右子树的根结点的关键字值。本节将以大根堆为例进行讨论。图9.7堆的示例(a)大根堆；(b)小根堆

2.堆排序的方法若在输出堆顶的最大值后，使得剩余n-1个元素的序列又重建成一个堆，则得到n个元素中的次大值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。可以按以下步骤实现堆排序：

(1)将n个记录存放在一个一维数组中；

(2)将一维数组中的n个记录调整成堆；

(3)将看成的完全二叉树的根(第1个数组元素位置上的记录)与最后一个记录对调；

(4)将第1至第n-i(1≤i≤n-1)个记录再构成堆；

(5)重复(3)至(4)步，直到i = n-1。实现堆排序需要解决两个问题：①如何由一个无序序列建成一个堆？②如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？下面先讨论第二个问题，然后再讨论第一个问题。以一维数组r[1,…,n]存储待排序记录，r[0]作为临时存储单元。问题1:输出堆顶元素后，如何重建堆?以从图9.8(a)的大根堆中输出最大元素为例。首先将完全二叉树根结点中的记录r[1]与最后一个记录r[n]对调，后面的操作将不再考虑交换下来的原来堆顶元素，只将其余元素r[1]～r[n-1]构成堆。在这些元素对应的完全二叉树中，根结点的左、右子树均为堆，只有根可能不符合堆的要求。如图9.8(b)所示。将新的根结点记录移出，该记录称为待调整记录，此时根结点相当于空结点。从空结点的左、右孩子中选出一个关键字较大的记录，如果该记录的关键字大于待调整记录的关键字，则将该记录上移至空结点中。如图9.8(c)所示。此时，原来那个关键字较大的子结点相当于空结点。重复上述移动过程，直到空结点左、右子树的关键字均不大于待调整记录的关键字，此时将待调整记录放入空结点即可。如图9.8(d)至图9.8(f)所示。上述调整方法相当于把待调整记录逐步向下“筛”的过程，所以称这个自堆顶至叶子的调整过程为“筛选”。图9.8输出堆顶元素并调整建新堆过程(a)大根堆；(b)交换48与98；(c) 48移出，77准备上移；(d)77上移后，62准备上移；(e) 62上移后，48准备移入空记录；(f) 48移入空记录得到筛选后的堆问题2：如何由一个任意序列建成堆？一个任意序列看成是对应的完全二叉树，由于叶子结点可以视为单元素的堆，因而可以反复利用“筛选”法，自底向上逐层把所有以非叶子结点为根的子树调整为堆，直到将整个完全二叉树调整为堆。如果二叉树结点数目为n，则最后一个叶子结点的编号为n，而它的双亲就是最后一个非叶子结点，其编号为

n/2

。因此，“筛选”须从第

n/2

个元素开始，逐层向上倒退，直到根结点。

例9.6

已知关键字序列：｛48，62，35，77，55，14，35，98｝，要求将其筛选为一个堆。

解：在此，n = 8，所以应从第４个结点77开始筛选。建堆过程如图9.9所示。图中箭头所指为当前待筛结点。图9.9建初始堆过程示例(a)初始无序序列，准备筛77；(b) 77筛完后，准备筛35；(c) 35筛完后，准备筛62；(d) 62筛完后，准备筛48；(e) 48筛完后，得到大根堆

3.堆排序的算法及分析首先利用筛选算法建初始堆，移出最大元素后再利用筛选算法重建堆，重复n-1次移出再重建的过程，完成排序。待排序元素存放在数组r[1,…,n]中。

(1)筛选的算法用C语言描述如下：

voidsift(RecordTyper[],intk,intm)

/*假设r[k,…,m]是以r[k]为根的完全二叉树，且分别以r[2k]和r[2k+1]为根的左、右子树都是大根堆，通过筛选，使整个序列r[k,…,m]满足堆的性质*/{

inti,j;

RecordTypex；

i=k；

j=2*i； /*r[j]是r[i]的左孩子*/

x=r[i]； /*移出根结点*/

while(j<=m){

if(j<m&&r[j].key<r[j+1].key)

j++； /*若右孩子较大，则把j修改为右孩子的下标*/

if(x.key<r[j].key) /*若父结点小于孩子结点*/{

r[i]=r[j]； /*将r[j]上移到父结点的位置上*/

i=j； /*以上移子结点的原位置为新的父结点位置，继续向下筛*/

j=2*i；

}elsej=m+1；/*父结点不小于子结点，筛选运算完成，令j=m+1，以便中止循环*/

}

r[i]=x；/*被筛结点的值放入最终位置*/}

(2)堆排序算法：利用筛选函数，从第

n/2

个元素开始，向上倒退，直到根结点r[1]，建立初始堆。将已有堆中的根与最后一个叶子交换，利用筛选函数，进一步恢复堆，直到一棵树只剩一个根为止。堆排序算法用C语言描述如下：voidHeapSort(RecordTyper[],intn){

inti；

RecordTypew；

for(i=n/2；i>=1；i--) /*建立初始堆*/

sift(r,i,n)；for(i=n；i>=2；i--)

/*进行n-1次循环，完成堆排序*/{

w=r[i]； /*将第一个元素同当前区间内最后一个元素对换*/

r[i]=r[1]；

r[1]=w；

sift(r,1,i-1)； /*r[i]结点为已移出者，r[1]～r[i-1]结点重建堆*/

}}堆排序算法的时间复杂度是O(nlog2n)。堆排序是一种不稳定的排序方法。9.5归并排序归并排序(MergingSort)的基本思想是：将两个有序的序列合并成一个有序的序列。如果无序序列中有n个记录，则可以把它看成n个有序的子序列，每个子序列只包含一个记录，归并排序先将每个相邻的两个子序列合并，得到

n/2

个有序子序列，每个子序中包含2个或1个记录，然后再将这些子序列中相邻的子序列两两归并。依此类推，直到合并成一个有序的序列为止。由于在排序过程中，子序列总是两两归并，因此归并排序也称为二路归并排序。

例9.7

关键字序列为：(36，62，22，58，72，10，22*，89，55，33)，采用二路归并排序过程如图9.10所示。图9.10二路归并排序过程归并排序法的基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列，通过递归调用两两合并的函数来实现。两两合并的算法在例2.2中已经详细介绍，这里不再重复。归并排序法的时间复杂度为O(nlog2n)。归并排序是一种稳定的排序方法，这是它与快速排序和堆排序相比的最大特点。一般情况下，由于要求附加与待排记录等数量的辅助空间，因此归并排序较少用于内部排序，而主要用于外部排序。9.6基数排序基数排序(RadixSort)又称为吊桶排序，是和前面介绍的各种排序方法完全不同的一种排序方法。前面介绍的排序方法中，主要是通过关键字间的比较和移动记录这两个操作来实现排序，而基数排序不需要进行记录关键字间的比较，它是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。基数排序有链式基数排序和多关键字排序等方法。本节只介绍链式基数排序。假设记录r[i]的关键字为keyi，keyi是由d位十进制数字构成的，即keyi = Ki1Ki2…Kid，其中Ki1是最高位，Kid是最低位，每一位的值都在0≤Kij≤9的范围内，此时基数rd = 10。如果keyi是由d个小写英文字母构成的，即'a'≤Kij≤'z'，则基数rd = 26。链式基数排序属于“低位优先”排序法，即从最低位开始，按关键字每位的不同值将序列中的记录“分配”到rd个队列当中，再按顺序“收集”，如此重复d次，通过反复进行分配与收集操作来完成排序。

例9.8

关键字序列{278，109，63，930，589，184，505，269，8，83}，采用链式基数排序的过程如图9.11所示。f[j]和e[j]分别代表第j个分配队列的头尾指针。对于n个记录(每个记录关键字最多含d位，每位的取值范围为rd个值)进行链式排序的时间复杂度为O(d(n + rd))。链式基数排序是稳定的排序方法，适合于n值很大而关键字位数较少的序列。图9.11链式基数排序示例(a)初始状态；(b)第一趟分配之后；(c)第一趟收集之后；图9.11链式基数排序示例(d)第二趟分配之后；(e)第二趟收集之后；(f)第三趟分配之后；(g)第三趟收集之后的有序记录9.7排序算法9.7.1各种排序算法的比较在各种排序方法中，没有哪一种是绝对最优的，在实际使用时需根据不同情况适当选择所需的排序方法，甚至可将多种方法结合起来使用。几种常用排序方法的比较如表9.2所示。表9-2几种常用排序方法比较9.7.2排序方法的选择上面对各种排序方法进行了综合比较和分析，那么在实际应用中究竟如何选择合适的排序方法呢？一般来说，首先应从稳定性方面进行分析。若要求算法稳定，则只能在稳定方法中选择，否则可从所有排序方法中进行选择，也可从待排序的记录数n的大小上进行考虑。若n较大，首先在改进的排序方法中进行选择，然后再考虑其他因素。综上所述，列出以下几种选择方法，仅供读者参考：

(1)当待排序的结点数n较大、关键字分布比较均匀且对算法的稳定性不作要求时，宜选择快速排序法。

(2)当待排序的结点数n较大、关键字分布可能出现正序或逆序的情况且对算法的稳定性不作要求时，宜采用堆排序或归并排序。

(3)当排序的结点数n较大、内存空间较大且要求算法稳定时，宜采用归并排序。

(4)当待排序的结点数n较小，对排序的稳定性不作要求时，宜采用直接选择排序。若关键字不接近逆序，也可采用直接插入排序。

(5)当待排序的结点数n较大，关键字基本有序或分布较均匀且要求算法稳定时，采用直接插入排序。在实际应用中，可根据实际要求进行选择。本章小结本章首先介绍了排序及其相关的基本概念，然后介绍了直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、排序过程及实现算法，并对这些算法的效率进行了分析和比较。一个好的排序算法所需要的比较次数和存储空间都应该较少，但通过本章的学习可以看出，不存在一个“十全十美”的排序算法能够适合于不同的场合，每一种排序算法各有优缺点。在实际应用中，应根据问题的规模大小、排序的稳定性、算法的效率等方面进行分析和比较，从而针对不同的应用场合选择合适的排序算法。习题九一、单选题

1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是

。

A.希尔排序 B.冒泡排序

C.直接插入排序 D.直接选择排序

2.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用

排序法。

A.冒泡排序 B.堆排序

C.快速排序 D.基数排序

3.排序的元素序列基本有序的前提下，效率最高的排序方法是

。

A.直接插入排序 B.直接选择排序

C.快速排序 D.归并排序

4.一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为

。

A. 79，46，56，38，40，80

B. 84，79，56，38，40，46

C. 84，79，56，46，40，38

D. 84，56，79，40，46，38

5.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为

。

A. 38，40，46，56，79，84

B. 40，38，46，79，56，84

C. 40，38，46，56，79，84

D. 40，38，46，84，56，79

6.排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为

。

A.希尔排序 B.归并排序

C.插入排序D.选择排序

7.用一种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：初始：25，84，21，47，15，27，68，35，20第一趟：20，15，21，25，47，27，68，35，84第二趟：15，20，21，25，35，27，47，68，84第三趟：15，20，21，25，27，35，47，68，84则所采用的排序方法是

。

A.选择排序 B.希尔排序

C.归并排序 D.快速排序

8.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是

。

A. O(1) B. O(n)

C. O(n2) D. O(nlog2n)

9.给定n个元素的向量，建立一个有序单链表的时间复杂度是

。

A. O(1) B. O(n)

C. O(n2) D. O(nlog2n)

二、解决下列问题

1.已知序列(17，18，60，40，7，32，73，65，85)，请给出采用冒泡排序法对该序列作升序排序时每一趟的结果。

2.已知序列(503，87，512，61，908，170，897，275，653，462)，请给出采用堆排序法对该序列作升序排序时每一趟的结果。

3.已知序列(503，87，512，61，908，170，897，275，653，462)，请给出采用基数排序法对该序列作升序排序时每一趟的结果。

4.已知序列(503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94)，请给出采用快速排序法对该序列作升序排序时每一趟的结果。实训9-1内部排序算法时间复杂度分析【实训目的】掌握常用内部排序算法，并对各种内部排序算法时间复杂度进行分析。【实训要求】

1.对以下3种常用排序算法比较其关键字比较次数和关键字移动次数(关键字交换计为3次移动)：直接插入排序、冒泡排序、快速排序。

2.待排序表的表长不少于100，其中的数据用伪随机数，至少要用5组不同的输入数据做比较。【算法分析】在程序适当的地方插入计数操作。【程序清单】#include<stdlib.h>#defineMAXSIZE100voidInsertSort(intr[],intn)/*用直接插入排序方法对r[1]，…，r[n-1]进行排序*/{inti,j,b,y;

b=0; /*比较计数器初值为0*/y=0; /*移动计数器初值为0*/for(i=2;i<=n;i++) /*认为r[1]是已排好的初始序列*/{r[0]=r[i]; /*将待插入记录存放到r[0]中*/y++;for(j=i-1;r[0]<r[j];j--)/寻找插入位置*/{r[j+1]=r[j];b++;y++;}b++;/*使循环结束的最后一次比较计数加1*/r[j+1]=r[0];/*将待插入记录插入到已排序的序列中*/y++;}printf("比较%d次,移动%d次\n",b,y);}/*InsertSort*/voidBubbleSort(intr[],intn)/*用冒泡排序法对r[1],…,r[n]进行排序*/{inti,m,b,y,flag;b=0; /*比较计数器初值为0*/y=0; /*移动计数器初值为0*/ flag=1; /*标志量。交换发生时为1*/m=n; /*每趟排出的最大值存放的位置，也就是每趟参与排序的元素个数*/while(m>1&&flag){flag=0;for(i=1;i<m;i++)

{if(r[i]>r[i+1]){flag=1;r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];

y+=3; /*交换作移动3次*/}b++;}m--;}printf("比较%d次,移动%d次\n",b,y);}intsplit(intr[],intm,intn,int*pb,int*py)/*对记录数组r[m]，…，r[n]进行分割，返回分界线位置，参数pb、py返回比较和移动次数*/{inti,j;intt;i=m;j=n;t=r[i]; /*选择基准记录*/(*py)++;/*移动计数*/while(i<j){while((i<j)&&(r[j]>=t))/*j从右到左找小于t的记录*/{j=j-1;(*pb)++;/*比较计数*/}if(i<j) /*找到小于t的记录，则进行交换*/{r[i]=r[j];(*py)++;i=i+1;}while((i<j)&&(r[i]<=t)) /*i从左到右找大于t的记录*/{i=i+1;(*pb)++;}if(i<j)/*找到大于t的记录，则进行交换*/{r[j]=r[i];(*py)++;j=j-1;}}r[i]=t; /*将基准记录保存到i=j的位置*/(*py)++; return(i); /*返回基准记录的位置*/}voidQkSort(intr[],intm,intn,int*pb,int*py)/*对记录数组r[m]，…，r[n]用快速排序算法进行排序，参数pb、py返回比较和移动的次数*/{inti;if(m<n)/*子表不空*/

{i=split(r,m,n,pb,py); /*分割*/QkSort(r,m,i-1,pb,py); /*对前面子表进行快速排序*/QkSort(r,i+1,n,pb,py); /*对后面子表进行快速排序*/

}}main(){inti,j,r[MAXSIZE];intb,y;for(i=1;i<=5;i++){printf("\n第%d组数据\n",i);for(j=1;j<=100;j++)r[j]=rand();printf("直接插入排序:\t");InsertSort(r,100);printf("冒泡排序:\t");BubbleSort(r,100);b=0;y=0;printf("快速排序:\t");QkSort(r,1,100,&b,&y);printf("比较%d次,移动%d次\n",b,y);}}

程序运行结果如下：观察结果会发现，冒泡排序、快速排序的比较和移动次数总是不变，且冒泡排序的效率最高，比较次数仅为99，移动次数为0。如果将冒泡函数BubbleSort()中的“flag = 0;”一句删除，即无论是否发生交换都不中止排序，则发现冒泡比较4950次，移动0次。这是因为伪随机函数rand()所产生的是一个有序序列，冒泡排序过程中不会发生交换。此时快速排序退化为冒泡排序，所以比较4950次。且由于每趟快速排序时都要经过保存和写回基准记录r[i]的步骤，所以移动次数为2*99 = 198。实训9-2排序算法的应用【实训目的】运用各种排序算法解决实际问题。【实训内容】为奥运会男子110米栏比赛设计排序和查询系统，可分别按选手编号和成绩排序，并提供按编号查询、按编号和名次输出的功能。【实训要求】

1.编写完整程序，主函数显示如下菜单：

1—输入

2—按选手编号排序

3—按成绩排序

4—按选手编号查询

5—按编号输出

6—按名次输出

0—退出

2.编写输入、按选手编号排序(直接选择排序)、按成绩排序(堆排序)、按选手编号查询(折半查找)和输出5个函数。【算法分析】记录至少包括选手编号、成绩等数据项，以数组形式存储。分别以编号和成绩为关键字排序，并将排序结果分别用另外的数组保存。按选手编号进行折半查找要在排序后的结果中进行。【程序清单】#include<stdio.h>#defineMAXSIZE100typedefstruct{intnumber;floatscore;}RecordType;voidinput(RecordTyper[],intn){

inti;for(i=1;i<=n;i++){printf("r[%d]的编号成绩:\n",i);scanf("%d%f",&r[i].number,&r[i].score);}}voidSelectSort(RecordTyper[],intn)/*用直接选择排序方法对r[1],…,r[n]按选手编号进行排序*/{inti,j,k;for(i=1;i<n;i++) { k=i; for(j=i+1;j<=n;j++) if(r[j].number<r[k].number) k=j; if(k!=i) {

r[0]=r[i]; /*r[0]用作临时变量，交换r[i]和r[k]*/r[i]=r[k];r[k]=r[0];}}}voidsift(RecordTyper[],intk,intm)/*假设ｒ[k,…,m]是以ｒ[k]为根的完全二叉树，且分别以r[2k]和r[2k+1]为根的左、右子树都是大根堆，通过筛选，使整个序列r[k,…,m]满足堆的性质*/{inti,j;RecordTypex;i=k;j=2*i; /*r[j]是r[i]的左孩子*/x=r[i]; /*移出根结点*/while(j<=m){ if(j<m&&r[j].score<r[j+1].score) j++; /*若右孩子较大，则把j修改为右孩子的下标*/ if(x.score<r[j].score) /*若父结点小于孩子结点*/ { r[i]=r[j]; /*将r[j]上移到父结点的位置上*/

i=j; /*以上移子结点的原位置为新的父结点位置，继续向下筛*/ j=