第10章排序一、基础知识题10.1 基本概念：内排序，外排序，稳定排序，不稳定排序，顺串，败者树，最佳归并树。

【解答】⑴内排序和外排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

内部排序适用于记录个数不多的文件，不需要访问外存，而外部排序适用于记录很多的大文件，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。

⑵稳定排序和不稳定排序假设待排序记录中有关键字K i=K j（i≠j），且在排序前的序列中R i领先于R j。

经过排序后，R i与R j的相对次序保持不变（即R i仍领先于R j），则称这种排序方法是稳定的，否则称之为不稳定的。

⑶顺串外部排序通常经过两个独立的阶段完成。

第一阶段，根据内存大小，每次把文件中一部分记录读入内存，用有效的内部排序方法（如快速排序、堆排序等）将其排成有序段，这有序段又称顺串或归并段。

⑷败者树败者树为提高外部排序的效率而采用的，是由参加比赛的n个元素作叶子结点而得到的完全二叉树。

每个非叶（双亲）结点中存放的是两个子结点中的败者数据,而让胜者去参加更高一级的比赛。

另外,还需增加一个结点,即结点0,存放比赛的全局获胜者。

⑸最佳归并树在外部排序的多路平衡归并的k叉树中，为了提高效率减少对外存的读写次数，按哈夫曼树构造的k叉树称最佳归并树。

这棵树中只有度为0和度为k的结点。

若用m表示归并段个数，用n k表示度为k的个数，若(m-1)%(k-1)=0，则不需增加虚段，否则应附加k-(m-1)%(k-1)-1个虚段（即第一个k路归并使用(m-1)%(k-1)+1个归并段）。

10.2设待排序的关键字序列为(15， 21， 6， 30， 23， 6′， 20， 17)，试分别写出使用以下排序方法每趟排序后的结果。

并说明做了多少次比较。

(1) 直接插入排序(2) 希尔排序(增量为5，2，1) (3) 起泡排序(4) 快速排序(5) 直接选择排序 (6) 锦标赛排序(7) 堆排序(8) 二路归并排序 (9) 基数排序【解答】(1) 直接插入排序初始关键字序列： 15，21，6，30，23，6′，20，17第一趟直接插入排序：【15，21】第二趟直接插入排序：【6，15，21】第三趟直接插入排序：【6，15，21，30】第四趟直接插入排序：【6，15，21，23，30】第五趟直接插入排序：【6，6′，15，21，23，30】第六趟直接插入排序：【6，6′，15，20，21，23，30】第七趟直接插入排序：【6，6′，15，17，20，21，23，30】 (2) 希尔排序(增量为5，2，1)初始关键字序列： 15，21，6，30，23，6′，20，17第一趟希尔排序： 6′，20，6，30，23，15，21，17第二趟希尔排序： 6′，15，6，17，21，20，23，30第三趟希尔排序： 6′，6，15，17，20，21，23，30(3) 起泡排序初始关键字序列：15，21，6，30，23，6′，20，17第一趟起泡排序：15，6，21，23，6′，20，17，30第二趟起泡排序：6，15，21，6′，20，17，23，30第三趟起泡排序：6，15，6′，20，17，21，23，30第四趟起泡排序：6，6′，15，17，20，21，30，23第五趟起泡排序：6，6′，15，17，20，21，30，23(4) 快速排序初始关键字序列： 15，21，6，30，23，6′，20，17第一趟快速排序：【6′，6】15【30，23，21，20，17】第二趟快速排序： 6′，6， 15【17，23，21，20】30第三趟快速排序： 6′，6， 15，17【23，21，20】30第四趟快速排序： 6′，6， 15，17，【20，21】23，30第五趟快速排序： 6，6′，15，17，20，21，30，23(5) 直接选择排序初始关键字序列： 15，21，6，30，23，6′，20，17第一趟直接选择排序： 6，21，15，30，23，6′，20，17第二趟直接选择排序： 6，6′，15，30，23，21，20，17第三趟直接选择排序： 6，6′，15，30，23，21，20，17第四趟直接选择排序： 6，6′，15，17，23，21，20，30第五趟直接选择排序： 6，6′，15，17，20，21，23，30第六趟直接选择排序： 6，6′，15，17，20，21，23，30第七趟直接选择排序： 6，6′，15，17，20，21，23，30(6) 锦标赛排序初始关键字序列： 15，21，6，30，23，6′，20，17666’1566’1715216306’20 176’15 6’15 306’17 15 21∞30 23 6’20 171523153023171521∞3023∞2017锦标赛排序的基本思想是：首先对n个待排序记录的关键字进行两两比较，从中选出⎡n/2⎤个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。

我们将一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出，具体做法为：输出“冠军”后，将（冠军）叶子结点关键字改为最大，继续进行锦标赛排序，直到选出关键字次小的记录为止，如此循环直到输出全部有序序列。

上面给出了排在前三个的记录，详细过程略。

(7) 堆排序初始关键字序列：15，21，6，30，23，6′，20，17初始堆： 6，17，6’，21，23，15，20，30第一次调堆： 6’，17，15， 21，23，30，20，【6】第二次调堆： 15，17，20，21，23，30，【6’，6】第三次调堆： 17，21，20，30，23，【15，6’，6】度均为1,排序完毕。

当n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件（长度均为3,k=2）进行排序,各需2次,共10次即可。

(2) 在最好情况下快速排序的原始序列实例：4,1,3,2,6,5,7。

(3) 在最坏情况下,若每次用来划分的记录的关键字具有最大(或最小)值,那么只能得到左(或右)子文件,其长度比原长度少1。

因此,若原文件中的记录按关键字递减次序排列,而要求排序后按递增次序排列时,快速排序的效率与冒泡排序相同,其时间复杂度为O(n2)。

所以当n=7时,最坏情况下的比较次数为21次。

(4) 在最坏情况下快速排序的初始序列实例： 7,6,5,4,3,2,1,要求按递增排序。

10.9判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。

(1)100，90，80，60，85，75，20，25，10，70，65，50(2)100，70，50，20，90，75，60，25，10，85，65，80【解答】(1) 是堆(2) 不是堆。

调成大堆： 100,90,80,25,85,75,60,20,10,70,65,5010.10在多关键字排序时，LSD和MSD两种方法的特点是什么？【解答】最高位优先（MSD）法：先对最高位关键字K0进行排序,将序列分成若干子序列,每个子序列中的记录都具有相同的K0值,然后,分别就每个子序列对关键字K1进行排序,按K1值不同再分成若干更小的子序列,……,依次重复,直至最后对最低位关键字排序完成,将所有子序列依次连接在一起,成为一个有序子序列。

最低位优先（LSD）法：先对最低位关键字K d-1进行排序,然后对高一级关键字K d-2进行排序,依次重复,直至对最高位关键字K0排序后便成为一个有序序列。

进行排序时,不必分成子序列,对每个关键字都是整个序列参加排序,但对K i(0<=i<d-1)排序时,只能用稳定的排序方法。

另一方面,按LSD进行排序时,可以不通过关键字比较实现排序,而是通过若干次“分配”和“收集”来实现排序。

10.11给出如下关键字序列321，156，57，46，28，7，331，33，34，63试按链式基数排序方法，列出一趟分配和收集的过程。

【解答】按LSD法→321→156→57→46→28→7→331→33→34→63分配 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]321 33 34 156 57 28331 63 46 7收集→321→331→33→63→34→156→46→57→7→2810.12奇偶交换排序如下所述：对于初始序列A[1]，A[2]，…，A[n]，第一趟对所有奇数i(1<=i<n)，将A[i]和A[i+1]进行比较，若A[i]>A[i+1]，则将两者交换；第二趟对所有偶数i(2<=i<n)，将A[i]和A[i+1]进行比较，若A[i]>A[i+1]，则将两者交换；第三趟对所有奇数i(1<=i<n)；第四趟对所有偶数i(2<=i<n)，…，依次类推直至到整个序列有序为止。

(1) 分析这种排序方法的结束条件。

(2) 写出用这种排序方法对35，70，33，65，24，21，33进行排序时，每一趟的结果。

【解答】(1)排序结束条件为没有交换为止(2)第一趟奇数：35,70,33,65,21,24,33第二趟偶数：35,33,70,21,65,24,33第三趟奇数：33,35,21,70,24,65,33第四趟偶数：33,21,35,24,70,33,65第五趟奇数：21,33,24,35,33,70,65第六趟偶数：21,24,33,33,35,65,70第七趟奇数：21,24,33,33,35,65,70(无交换)第八趟偶数：21,24,33,33,35,65,70(无交换) 结束10.13设某文件经内排序后得到100个初始归并段(初始顺串)，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？【解答】设归并路数为k,归并趟数为s,则s=⎡logk 100⎤,因⎡logk100⎤=3 ,且k为整数，故k=5,即最少5路归并可以完成排序。

10.14证明：置换-选择排序法产生的初始归并段的长度至少为m。

(m是所用缓冲区的长度)。

【证明】由置换选择排序思想,第一个归并段中第一个元素是缓冲区中最小的元素,以后每选一个元素都不应小于前一个选出的元素,故当产生第一个归并段时（即初始归并段）,缓冲区中m个元素中除最小元素之外,其他m-1个元素均大于第一个选出的元素,即当以后读入元素均小于输出元素时,初始归并段中也至少能有原有的m个元素。

证毕。

10.15设有11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25，40，16，38，77，64，53，88，9，48，98。