[例12-7] 用某种排序方法对线性表(25，84，2l，47，15，27，68，35，20)进行排序时，若元素序列的变化情况如下：
25，84，2l，47，15，27，68，35，20 20，15，21，25，47，27，68，35，84 15，20，2l，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则采用的排序方法是( )。
A．选择排序 B．希尔排序 C．归并排序 D．快速排序
解析：从序列中看到，每次将一个子序列以第一个元素为基准分为两段，显然这是快速排序方法。本题答案为：D。 ：
[例12-8] 在所有排序方法中，关键字的比较次数与记录的初始排列次序无关的是( )。 A．希尔排序 B．冒泡排序 巴插入排序 D．选择排序
解析：由于选择排序每趟从待排记录中选出关键字最小的记录，每个记录都需要进行比较，不考虑已排好序的子序列，因此，关键字比较的次数与记录的初始排列次序无关。 本题答案为：D。
[例12-9] 一组记录的关键字为{46，79，56，38，40，84}，则利用堆排序(建立大根堆)的方法建立的初始堆为( )。
A．79，46，56，38，40，84 B．84，79，56，38，40，46 C．84，79，56，46，40，38 D．84，56，79，40，46，38 解析：根据初始堆的建立调整方法可知，本题答案为：B。
(例12-10) 设有1000个无序元素序列，希望用最快的速度挑选出其中前10个最大的元素，最好用( )法。
A．冒泡排序 B．快速排序 C．堆排序 D．基数排序
解析：由于堆排序一趟排好一个记录，当只挑选出其中前10个最大的记录时，使用堆 排序最好。本题答案为：C。
(例12-11) 下述几种排序方法中，要求内存量最大的是( )。 A．插入排序 B．选择排序 C．快速排序 D．归并排序 解析：由表12.1可知，本题答案为：D。
(例12-12) 下列排序算法中，其中( )是稳定的。 A．堆排序和冒泡排序 B．快速排序和堆排序 C．直接选择排序和归并排序 D．归并排序和冒泡排序 解析：由表12．1可知，本题答案为：D。 二、判断题
(例12-13) 若采用顺序存储结构进行排序操作，在待排序的元素很大时，为了交换元素的位置而移动元素要占用较多的时间，这是影响时间复杂度的主要因素。
解析：正确。在采用顺序存储结构进行排序操作时，时间复杂度主要反映在关键字的比较和对记录的移动上；在待排序的元素很大时，移动记录需要的时间是比较多的，从而移动元素就成了影响时间复杂度的主要因素。
(例12-14) 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。 解析：错误。若在待排的一组序列中，ki和kj的关键字相同，即ki=kj，且在排序前ki
领先于kj，那么当排序后，如果ki和kj的相对次序保持不变，即ki仍领先于kj，则称此排序方法为稳定的，否则称此方法为不稳定的。
(例12-15) 在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlbn)。
解析：错误。在初始数据已经有序时，快速排序算法蜕变为冒泡排序，其时间复杂度为O(n2)。
41
(例12-16) 在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。 解析：正确。在用堆排序算法排序时，第一次是将初始堆的第一个记录与最后一个记录交换，如果是大根堆就将最大的记录换到最后，依此类推，待排序完成后序列即可成为一个增序序列。
(例12-17) 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法，冒泡排序算法的最坏时间复杂度为O(n2)，而快速排序算法的最坏时间复杂度为O(nlbn)，所以快速排序比冒泡排序的算法效率更高。 解析：错误。由表12.1可知，在待排序列已经有序的情况下，快速排序算法的最坏时间复杂度为O(n2)，与冒泡排序是一样的。
[例12—18] 归并排序在任何情况下都比所有简单排序的速度快。
解析：错误。由表12.1可知，简单排序(如冒泡排序和直接插入排序)在最好情况下的时间复杂度为O(n)，而归并排序的时间复杂度为O(nlbn)，所以说命题说法是错误的。
[例12-19] 快速排序的速度在所有排序方法中是最快的，而且所需附加空间也最少。
解析：错误。由表12.1可知，快速排序的速度并不是在所有情况下都是最快的，它只是平均性能最好的一种排序方法。而直接插入排序、希尔排序、堆排序、直接选择排序、冒泡排序等方法所需附加空间都是一个，比快速排序所需要的辅助空间要少。 三、填空题
[例12—20] 若不考虑基数排序，则在内排序过程中，主要进行的两种基本操作是关键字的 和记录的 。
解析：在内排序过程中，主要进行的两种基本操作是关键字的比较和记录的移动。本题答案为：比较；移动。
(例12—21) 分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，最省时间的是 算法，最费时间的是 算法。
解析：由表12.1可知，对初态有序的表进行排序，堆排序的时间复杂度为O(nlbn)；快速排序为最坏情况，时间复杂度为O(n2)；冒泡排序为最好情况，时间复杂度为O(n)；归并排序时间复杂度为O(nlbn)。本题答案为：冒泡排序；快速排序。
(例12—22) 快速排序法在 情况下最不利于发挥其长处，在 情况下最易发挥其长处。 解析：快速排序在待排记录有序的情况下蜕变为冒泡排序是最坏情况，在待排记录基本无序而且记录数较多的情况下最易发挥其长处。本题答案为：待排记录有序；待排记录基本无序且记录数较多。 [例12—23] 每次通过直接或间接比较两个元素，若出现逆序排列时就交换它们的位置，此种方法叫做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。 解析：由快速排序和归并排序的定义可知，本题答案为：快速；归并。
[例12—24] 在归并排序和快速排序中，若原始记录接近正序或反序，则选用 ，若原始记录无序，则最好选用 。
解析：当原始记录接近正序或反序时，使用快速排序效率最低。本题答案为：归并排 序；快速排序。
[例12—25] 对n个记录的序列进行冒泡排序时，最少的比较次数是 。
解析：当初始序列正序时，第一趟比较n-1次，没有交换产生，退出算法。本题答案为：n-1。 (例12—26) 在堆排序、快速排序和归并排序中，若只从存储空间方面考虑，则应首先取 方法，其次选取 方法，最后选取 方法；若只从排序结果的稳定性方面考虑，则应选取 方法；若要在平均情况下排序最快，则应选取 方法；若要在最坏情况下排序最快并且要节省内存，则应选取 方法。
解析：由表12.2可知，本题答案为：堆排序；快速排序；归并排序；归并排序；快速排序；堆排序。 [例12—27] 排序不需要进行关键字的比较。
解析：基数排序不需要进行关键字的比较。本题答案为：基数。 四、应用题
42
(例12—28) 我们知道，对于由n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：
(1)当n= 7时，在最好情况下需进行多少次比较?请说明理由。 (2)当n＝7时，给出一个最好情况的初始排序的实例。 (3)当n＝7时，在最坏情况下需进行多少次比较?请说明理由。 (4)当n＝7时，给出一个最坏情况的初始排序的实例。
解析：(1)在最好情况下，假设每次划分能得到2个长度相等的子序列，子序列的长度为n=2k-1，那么，第一遍划分得到2个长度为[n/2]的子序列，第二遍划分得到4个长度为[n/4]的子序列；依此类推，总共进行k=lb(n+1)遍划分，各子序列长度为l，排序完毕。当n＝7时，k＝3，在最好情况下，第一遍比较6次可将序列分为2个长度都为3的子序列，第二遍分别对2个子序列进行排序，各比较2次。这样就可以将原序列排序完毕。所以最好情况下总共比较10次即可。
(2)最好的初始序列就是每次排序时都可将原序列分成2个长度一样的子序列的初始序列，即可使每个基准刚好都是该待排序列中大小位置居中的记录。当n＝7时，最好的初始排序情况的例子为4，7，5，6，3，1，2。
(3)在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右)子序列，其长度比原长度少1。因此，若原序列中的记录按关键字递减次序排列。而要求按递增次序排序时，快速排序的效率与冒泡排序相同，其时间复杂度为O(n2)。所以当n＝7时，最坏情况下的比较次数为21次。 (4)当n＝7时，最坏情况下的初始排序的例子为7，6，5，4，3，2，1。
（例l2—29) 在执行某排序算法过程中，出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法正确吗?为什么?
解析：这种说法是不正确的。因为排序的不稳定性是指排序前两个排序码相同的元素的相对次序经过排序后发生了变化，而题中未涉及到元素的相对次序改变，只有移动元素，所以此说法不正确。 [例12—30] 设记录的关键字集合key＝{49，38，66，90，75，10，20}。 (1)写出快速排序的第一趟和第二趟之后的结果。 (2)把关键字集合key调整成小根堆。
(3)在内部排序算法中，哪个排序要求的内存容量最多?
解析：(1)快速排序第一趟排序后的结果：{20，38，10，49，75，90，66}。 快速排序第二趟排序后结果：{10，20，38，49，75，90，66}。 (2)调整后的小根堆为：{10，38，20，90，75，66，49}。 (3)归并排序要求内存容量最多。
[例12—31] 设有6000个无序元素，希望用最快的速度挑选出其中最大的前10个元素。在以下的排序方法中，采用哪种方法最好?为什么?
快速排序 堆排序 归并排序 基数排序 希尔排序
解析：上面所列的几种排序方法都是速度比较快的排序方法，但快速排序、归并排序、
基数排序和希尔排序都是在排序结束后才能确定数据元素的全部顺序，在排序过程中无法知道部分元素的有序性。而堆排序则每次输出一个最大(或最小)的元素，然后对堆排序进行调整，保证堆顶的元素总是最大(或最小)。根据题意，只要求挑选出无序元素中最大的前10个元素，故采用堆排序方法是合适的。 (例12—32) 已知序列{25，18，60，40，7，21，32，73，68}，请给出分别采用冒泡排序方法、直接选择排序方法和快速排序方法对该序列做升序排列时的每一趟结果。 解析：(1)采用冒泡排序方法排序的各趟结果如下：(加框为每次冒出元素) 初始序列：25， 18， 60， 40， 7， 21， 32， 73， 68 7， 25， 18， 60， 40， 21， 32， 68， 73 第——趟：□
18， 25， 21， 60， 40， 32， 68， 73 第二趟： 7， □
21， 25， 32， 60， 40， 68， 73 第三趟： 7， 18， □
43
5， 32， 40， 60， 68， 73 第四趟： 7， 18， 21， 2□ 第五趟： 7， 18， 21， 25， 32， 40， 60， 68， 73 第五趟无元素交换，排序结束。
(2)采用直接选择排序方法排序的各趟结果如下：(加框为每次选出元素) 7， 21， 32， 73， 68 初始序列：25， 18， 60， 40， □
18， 60， 40， 25， 2l， 32， 73， 68 第——趟：[7] □
1， 32， 73， 68 第二趟： [7， 18] 60， 40， 25， 2□5， 60， 32， 73， 68 第三趟： [7， 18， 21] 40， 2□32， 73， 68 第四趟： [7， 18， 21， 25] 40， 60， □
40， 73， 68 第五趟： [7， 18， 21， 25， 32] 60， □
60， 73， 68 第六趟： [7， 18， 21， 25， 32， 40] □
68 第七趟： [7， 18， 21， 25， 32， 40， 60] 73， □ 第八趟： [7， 18， 21， 25， 32， 40， 60， 68] 73 结束： 7， 18， 21， 25， 32， 40， 60， 68， 73 (3)采用快速排序方法排序的各趟结果如下：
初始序列：25， 18， 60， 40， 7， 21， 32， 73， 68
第一趟： [21 18 7] 25 [40 60 32 73 68] 第二趟： [7 18] 21 25 [32] 40 [60 73 68] 第三趟： 7 [18] 21 25 32 40 60 [73 68] 第四趟： 7 18 21 25 32 40 60 [68] 73 结束： 7 18 21 25 32 40 60 68 73
(例12—33) 在冒泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序方向 相反的方向移动，试举例说明。快速排序过程中有没有这种现象?
解析：在冒泡排序过程中，有的关键宇在某趟排序中可能朝着与最终排序方向相反的 方向移动，如下面排序过程中关键字27的位置变化。 27 13 97 初始关键字：49 38 □
7 97 第一趟结果：13 49 38 2□7 49 38 97 第二趟结果：13 2□7 38 49 97 第三趟结果：13 2□
但在快速排序中不会出现这种情况，因为在每趟快速排序中，比基准元素大的元素都 交换到右边，而比基准元素小的元素都交换到左边。 五、算法设计题
[例12—34] 仔细阅读下面程序，并回答有关问题。 void test (int a[0.. 499], int n)
{
int i, j, x, flag；
flag= 1； i=1；
while(i flag = 0； for(j=l； j< ；j++) if( ) { 44