第10章 排序一、 基础知识题10.1 基本概念：内排序，外排序，稳定排序，不稳定排序，顺串，败者树，最佳归并树解答】⑴内排序和外排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序内部排序适用于记录个数不多的文件，不需要访问外存，而外部排序适用于记录很多的大文件，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果⑵稳定排序和不稳定排序 假设待排序记录中有关键字Ki=Kj（i≠j），且在排序前的序列中Ri领先于Rj经过排序后，Ri与Rj的相对次序保持不变（即Ri仍领先于Rj），则称这种排序方法是稳定的，否则称之为不稳定的⑶顺串 外部排序通常经过两个独立的阶段完成第一阶段，根据内存大小，每次把文件中一部分记录读入内存，用有效的内部排序方法（如快速排序、堆排序等）将其排成有序段，这有序段又称顺串或归并段⑷败者树 败者树为提高外部排序的效率而采用的，是由参加比赛的n个元素作叶子结点而得到的完全二叉树每个非叶（双亲）结点中存放的是两个子结点中的败者数据,而让胜者去参加更高一级的比赛。
另外,还需增加一个结点,即结点0,存放比赛的全局获胜者⑸最佳归并树 在外部排序的多路平衡归并的k叉树中，为了提高效率减少对外存的读写次数，按哈夫曼树构造的k叉树称最佳归并树这棵树中只有度为0和度为k的结点若用m表示归并段个数，用nk表示度为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’171521630236’2017 6’156’1530 6’171521∞ 30236’2017 1515231530 23171521∞ 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】第四次调堆： 20，21，23，30，【17，15，6’，6】第五次调堆： 21，30，23，【20，17，15，6’，6】第六次调堆： 23，30，【21，20，17，15，6’，6】第七次调堆： 30，【23，21，20，17，15，6’，6】堆排序结果调堆：【30，23，21，20，17，15，6’，6】 (8) 二路归并排序初始关键字序列： 15，21，6，30，23，6′，20，17 二路归并排序结果：15，17，20，21，23，30，6，6’ final↑ ↑first (9) 基数排序初始关键字序列：p→15→21→6→30→23→6′→20→17第一次分配得到:B[0].f→30→20←B[0].eB[1].f→21←B[1].eB[3].f→23←B[3].eB[5].f→15←B[5].eB[6].f→6→6’←B[6].eB[7].f→17←B[7].e第一次收集得到:p→30→20→21→23→15→6→6’→17第二次分配得到B[0].f→6→6’←B[0].eB[1].f→15→17←B[1].eB[2].f→20→21→23←B[5].eB[3].f→30←B[3].e第二次收集得到p→6→6’→15→17→20→21→23→30基数排序结果：6，6′，15，17，20，21，23，30 10.3在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。
【解答】见下表：排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序O(n2)O(n2)O(1)稳定 折半插入排序O(n2)O(n2)O(1)稳定 二路插入排序O(n2)O(n2)O(n)稳定 表插入排序O(n2)O(n2)O(1)稳定 起泡排序O(n2)O(n2)O(1)稳定 直接选择排序O(n2)O(n2)O(1)不稳定2,2’,1希尔排序O(n1.3)O(n1.3)O(1)不稳定3,2,2’,1(d=2,d=1)快速排序O(nlog2n)O(n2)O(log2n)不稳定2,2’,1堆排序O(nlog2n)O(nlog2n)O(1)不稳定2,1,1’(极大堆)2-路归并排序O(nlog2n)O(nlog2n)O(n)稳定 基数排序O(d*(rd+n))O(d*(rd+n))O (rd )稳定 10.4在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 【解答】这种说法不对因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。
对4，3，2，1起泡排序就可否定本题结论10.5 在堆排序、快速排序和归并排序方法中： (1)若只从存储空间考虑，则应首先选取哪种排序，其次选取哪种排序，最后选取哪种排序？(2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？(3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？(4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？【解答】(1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序 10.6 设要求从大到小排序问在什么情况下冒泡排序算法关键字交换的次数为最多解答】对冒泡算法而言，初始序列为反序时交换次数最多若要求从大到小排序，则表现为初始是上升序时关键字交换的次数为最多 10.7 快速排序的最大递归深度是多少？最小递归深度是多少？【解答】设待排序记录的个数为n,则快速排序的最小递归深度为ëlog2nû+1,最大递归深度n 10.8我们知道，对于n个元素组成的顺序表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关问： (1) 当n=7时，在最好情况下需进行多少次比较？请说明理由2) 当n=7时，给出一个最好情况的初始排序的实例。
3) 当n=7时，在最坏情况下需进行多少次比较？请说明理由4) 当n=7时，给出一个最坏情况的初始排序的实例解答】(1) 在最好情况下,每次划分能得到两个长度相等的子文件假设文件的长度n=2k-1,那么第一遍划分得。