二、综合应用题
## 二、综合应用题
01. 设关键字序列为{3,7,6,9,7,1,4,5,20}，对其进行排序的最小交换次数是多少？
02. 设顺序表用数组 A[] 表示，表中元素存储在数组下标 $1 \sim m + n$ 的范围内，前 $m$ 个元素递增有序，后 $n$ 个元素递增有序，设计一个算法，使得整个顺序表有序。
1）给出算法的基本设计思想。
2）根据设计思想，采用 $C / C++$ 描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度与空间复杂度。
03. 设有一个数组中存放了一个无序的关键序列 $K_{1}, K_{2}, \dots, K_{n}$。现要求将 $K_{n}$ 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 $n$。
## 8.6.4 答案与解析
### 一、单项选择题
01. A
采用排除法。题目要求是稳定排序，因此排除选项B和D，又基数排序不能对float型和double型的实数进行排序，因此排除选项C。
02. C
堆排序和快速排序不是稳定排序算法，而直接插入排序算法的时间复杂度为 $O(n^{2})$。
03. C
各种排序算法的时间和空间复杂度、稳定性等见表8.1。
04. ① I、IV、VI ② II、VI、VII ③ I、IV
读者应能从算法的原理上理解算法的稳定性情况。堆排序和归并排序在最坏情况下的时间复杂度与最好情况下的时间复杂度是同一数量级的，都是 $O(n \log_2 n)$。
05. A
堆排序的空间复杂度为 $O(1)$，因此快速排序的空间复杂度在最坏情况下为 $O(n)$，平均空间复杂度为 $O(\log_2 n)$，归并排序的空间复杂度为 $O(n)$。
06. B
冒泡排序的趟数为 $1 \sim n - 1$，和序列初态有关。简单选择排序每趟都选出一个最小（或最大）的元素，排序趟数固定为 $n - 1$。基数排序每趟都要进行分配和收集，排序趟数固定为 $d$。快速排序的趟数和枢轴的选取有关，即和划分是否对称有关，当划分的两个区域分别包含0个元素和 $n - 1$ 个元素时，这种最大限度的不对称性发生在序列初态基本有序时。
07. C
直接插入排序的趟数始终为 $n - 1$，而与序列的初始状态无关。2 路归并排序的趟数始终为 $\lceil \log_2 n \rceil$，而与序列的初始状态无关。堆排序每趟选出一个最大元素或最小元素，然后调整堆，初始建好堆后，需要 $n - 1$ 趟输出和调整堆的操作，而与序列的初始状态无关。
08. C
简单选择排序和直接插入排序的趟数始终为 $n - 1$。冒泡排序的趟数为 $1 \sim n - 1$，快速排序的趟数为 $\log_2 n \sim n - 1$，具体取决于序列的初始状态（快速排序还取决于划分方法）。
09. A
选择排序和序列初态无关，直接排除。初始序列基本有序时，插入排序比较次数较少。本题中，插入排序仅需比较 $n - 1 + 4$ 次，而希尔排序和冒泡排序的比较次数均远大于此。
<!-- page: 390 -->
2027年数据结构考研复习指导
10. A
简单选择排序的总比较次数显然是确定的。折半插入排序每趟的比较次数都为 $O(\log_2 m)$（$m$ 为当前已排好序的子序列的长度），因此总比较次数也是确定的。基数排序不是基于比较的排序算法。其他几种排序算法的比较次数显然和序列的初始状态有关。
11. C
堆是用于排序的，在查找时它是无序的，所以效率没有其他查找结构的高。
12. A
基数排序每趟需要利用前一趟已排好的序列，无法并行执行。快速排序每趟划分的子序列互不影响，可以并行执行。冒泡排序每趟对未排序的所有元素进行一趟处理，无法并行执行。堆排序可以并行执行，因为根结点的左右子树构成的子堆在执行过程中是互不影响的。
13. B
每趟冒泡和选择排序后，总会有一个元素被放置在最终位置上。显然，这里{11, 12}和{4, 5}所处的位置并不是最终位置，因此不可能是冒泡和选择排序。2路归并算法经过第二趟后应该是每4个元素有序的，但{11, 12, 13, 7}并非有序，因此也不可能是2路归并排序。
14. A
题中给出的排序过程，每一趟都是从前往后依次比较使最大值沉底，符合冒泡排序的特点。分别用其他3种排序算法尝试，归并排序第一趟后的结果为(2, 12, 16, 88, 5, 10)，基数排序第一趟后的结果为(10, 2, 12, 5, 16, 88)，希尔排序显然不符合。
15. A
对于说法I，简单选择排序每次选择未排序序列中的最小元素放入其最终位置。对于说法II，希尔排序每次对划分的子表进行排序，得到局部有序的结果，所以不能保证每趟结束都能确定一个元素的最终位置。对于说法III，快速排序每趟结束后都将枢轴元素放到最终位置。对于说法IV，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于选项V，2路归并排序每趟对子表进行两两归并，从而得到若干局部有序的结果，但无法确定最终位置。
16. B
归并排序的代码比插入排序的代码更为复杂，前者的空间复杂度为 $O(n)$，后者为 $O(1)$。但是前者的时间复杂度为 $O(n \log_2 n)$，后者为 $O(n^2)$。
17. D
在顺序存储的条件下，插入排序、选择排序、冒泡排序的时间复杂度都是 $O(n^{2})$，更换为链式存储后的时间复杂度还是 $O(n^{2})$。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加。
18. D
当数据规模较小时可选择复杂度为 $O(n^{2})$ 的简单排序算法，当数据规模较大时应选择复杂度为 $O(n\log_2n)$ 的排序算法，当数据规模大到内存无法放下时需选择外部排序算法，说法I正确。数据的存储方式主要分为顺序存储和链式存储，有些排序算法（如堆排序）只能用于顺序存储方式，说法II正确。若对数据稳定性有要求，则不能选择不稳定的排序算法，说法III显然正确。当数据初始基本有序时，直接插入排序的效率最高，冒泡排序和直接插入排序的时间复杂度都为 $O(n)$，而归并排序的时间复杂度仍然为 $O(n\log_2n)$，说法IV正确。
19. A
考虑比较极端的情况，对于有序数组，直接插入排序的比较次数为 $n - 1$ ，简单选择排序的比较次数始终为 $1 + 2 + \dots + n - 1 = n(n - 1) / 2$ ，说法I正确。两种排序算法的辅助空间都为 $O(1)$ ，无
<!-- page: 391 -->
第8章 椿序
379
差别，说法Ⅱ错误。初始有序时，移动次数均为0；对于通常情况，直接插入排序每趟插入都需要依次向后挪位，而简单选择排序只需与找到的最小元素交换位置，后者的移动次数少很多，说法Ⅲ错误。
## 20. D
直接插入排序和快速排序的特点如下表所示。
| | 适合初始序列情况 | 适合元素数量 | 空间复杂度 | 稳定性 |
| --- | --- | --- | --- | --- |
| 直接插入排序 | 大部分元素有序 | 较少 | O(1) | 稳定 |
| 快速排序 | 基本无序 | 较多 | O(log2n) | 不稳定 |
可见，说法I、II、III、IV都是采用直接插入排序而不采用快速排序的可能原因。
## 21. C
稳定的内部排序算法：插入排序、冒泡排序、归并排序和基数排序。不稳定的内部排序算法：简单选择排序、快速排序、希尔排序和堆排序。
## 22. D
简单选择排序每趟从未排序部分选出最小（或最大）元素，与未排序部分的首元素交换。无论输入如何，最多执行 $n - 1$ 次交换，总移动次数为 $O(n)$，是所有选项中最少的。而起泡排序、直接插入排序和快速排序在最坏情况下均需 $O(n^{2})$ 次移动（如逆序时起泡和插入需要大量移位，快排递归分割导致频繁交换）。因此，简单选择排序在最坏情况下的元素移动次数最少。
## 23. A
第1趟排序后，序列呈现出以间隔3分组的局部有序特征：下标模3相同的元素各自有序（如位置1,4,7上的25,10,15变为10,15,25；位置2,5,8上的40,20,35变为20,35,40），这是希尔排序在增量 $d = 3$ 时对各子序列进行插入排序的典型特征。第2趟进一步调整，符合增量缩小至1的结果。而其他三种排序方法均无法产生这种跨距离分组、局部有序的中间状态。
## 二、综合应用题
### 01. 【解答】
直接插入排序的交换次数更多，因此应当采用简单选择排序。
初始序列：3,7,6,9,7,1,4,5,20
第一次：1,7,6,9,7,3,4,5,20 交换1,3
第二次：1,3,6,9,7,7,4,5,20 交换3,7
第三次：1,3,4,9,7,7,6,5,20 交换4,6
第四次：1,3,4,5,7,7,6,9,20 交换5,9
第五次：1,3,4,5,6,7,7,9,20 交换6,7
所以最小交换次数为5（注意这里求的是交换次数，而不是移动次数或比较次数）。
### 02. 【解答】
1）算法的基本设计思想如下：将数组A[1...m+n]视为一个已经过m趟插入排序的表，则从 $m + 1$ 趟开始，将后 $n$ 个元素依次插入前面的有序表中。
2）算法的实现如下：
void Insert_Sort(ElemType A[], int m, int n) {
int i, j;
for (i = m + 1; i &lt;= m + n; i++) {
//依次将 A[m+1...m+n] 插入有序表
A[0] = A[i]; //复制为哨兵
for (j = i-1; A[j] &gt; A[0]; j--) //从后往前插入
A[j+1] = A[j]; //元素后移
A[j+1] = A[0]; //插入
<!-- page: 392 -->
2027年数据结构考研复习指导
```txt
}
3）时间复杂度由 $m$ 和 $n$ 共同决定，从上面的算法不难看出，在最坏情况下元素的比较次数为 $O(mn)$，而元素移动的次数为 $O(mn)$，所以时间复杂度为 $O(mn)$。
因为算法只用到了常数个辅助空间，所以空间复杂度为 $O(1)$。
此外，本题也可采用归并排序，将 A[1...m] 和 A[m+1...m+n] 视为两个待归并的有序子序列，算法的时间复杂度为 $O(m + n)$，空间复杂度为 $O(m + n)$。
## 03. 【解答】
基本思想：以 $K_n$ 为枢轴进行一趟快速排序。将快速排序算法改为以最后一个元素为枢轴，先从前往后，再从后往前。算法的代码如下：
int Partition(ElemType K[], int n) {
//交换序列 K[1..n]中的记录，使枢轴到位，并返回其所在位置
int i = 1, j = n; //设置两个交替变量初值分别为 1 和 n
ElemType pivot = K[j]; //枢轴
while (i &lt; j) { //循环跳出条件
while (i &lt; j &amp;&amp; K[i] &lt;= pivot)
i++; //从前往后找比枢轴大的元素
if (i &lt; j)
K[j] = K[i]; //移动到右端
while (i &lt; j &amp;&amp; K[j] &gt;= pivot)
j--; //从后往前找比枢轴小的元素
if (i &lt; j)
K[i] = K[j]; //移动到左端
} //while
K[i] = pivot; //枢轴存放在最终位置
return i; //返回存放枢轴的位置
}
## 8.7 外部排序
外部排序可能会考查相关概念、方法及排序过程。本节的主要内容包括：
① 外部排序是指对大文件进行排序，即待排序记录存储在外存中，且无法一次性全部装入内存，需在内存与外存之间多次交换数据，以完成整个文件的排序。
② 为减少多路平衡归并中外存读/写次数可采取的方法：增大归并路数和减少归并段数。
③ 利用败者树可高效实现多路归并，从而增大归并路数。
④ 利用置换-选择排序可生成更长的初始归并段，从而减少归并段个数。
⑤ 由长度不等的归并段进行多路平衡归并时，需要构造最佳归并树。
## 8.7.1 外部排序的基本概念
此前介绍的排序算法均假设所有数据可一次性载入内存（称为内部排序）。而在许多应用中，常需对大规模文件进行排序；由于记录数量庞大，无法将整个文件一次性装入内存。此时，待排序记录必须存储在外存中，排序时仅能将部分数据调入内存处理，并通过多次内外存之间的数据交换，逐步完成整体排序。这类依赖内外存协同操作的排序算法，称为外部排序。
<!-- page: 393 -->
第8章 椿序
381
## 8.7.2 外部排序的方法
文件通常以块为单位存储在磁盘上，操作系统也按块对磁盘信息进行读/写操作。由于磁盘读/写的机械动作耗时远高于内存运算时间（相比而言后者可忽略不计），因此外部排序的时间代价主要取决于访问磁盘的次数，即I/O次数。
### 最高选择 ➤ 对大文件排序时使用的排序算法（2016）
外部排序通常采用归并排序策略，包含两个阶段：① 生成初始归并段。根据内存缓冲区大小，将外存上的文件划分为若干子文件，依次读入内存，利用内部排序算法对每个子文件排序后写回外存，形成多个有序的初始归并段（也称顺串）；② 多路归并。对这些初始归并段进行逐趟多路归并，每趟将多个有序段合并为更长的有序段，逐步减少段数，最终得到整个有序文件。
例如，一个包含2000个记录的文件，每个磁盘块可容纳125个记录。首先通过8次内部排序，得到8个初始归并段R1～R8，每段包含250条记录。随后，对该文件执行如图8.15所示的2路归并，直至获得一个有序文件。具体实现时，可将内存工作区划分为三个缓冲区（见图8.14）：两个输入缓冲区和一个输出缓冲区。首先，从归并段R1和R2中各读入一个磁盘块，分别存入两个输入缓冲区；然后在内存中进行2路归并，将归并结果依次写入输出缓冲区；若输出缓冲区已满，则将其内容写入新的归并段R1'，清空后继续接收后续归并结果；若某个输入缓冲区取空，则从对应的归并段中读入下一块数据，继续参与归并。如此反复，直至R1与R2的所有记录均被归并完毕。接着归并R3与R4、R5与R6、R7与R8，完成第一趟归并。第二趟归并R1'与R2'、R3'与R4'。第三趟归并R1''与R2''，最终得到完整的有序文件，整个过程共进行3趟归并。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.14 2路归并
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.15 2路归并的排序过程 在外部排序中实现两两归并时，通常无法将两个输入有序段及归并结果同时驻留于内存中，因此必须频繁地将数据从外存读入、再将结果写回磁盘，这会消耗大量时间。一般而言，有 外部排序总时间 = 内部排序时间 + 外存读/写时间 + 内部归并时间 显然，外存读/写时间远大于内部排序与内部归并所需的时间，因此应着力减少I/O次数。由于外存的读/写操作以磁盘块为单位进行，结合前例可知，每趟归并需进行16次读和16次写，共32次I/O；3趟归并加上初始内部排序阶段的32次I/O，总计 $32 \times 3 + 32 = 128$ 次I/O操作。 若改用4路归并，则仅需2趟归并，总I/O次数降至 $32 \times 2 + 32 = 96$ 次。由此可见，增大归并路数可有效减少归并趟数，从而显著降低总的磁盘I/O次数，如图8.16所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.16 4路归并的排序过程 一般地，对 $r$ 个初始归并段进行 $k$ 路归并（每趟将 $k$ 个或更少的有序子文件合并为一个）。第一趟可将 $r$ 个归并段合并为 $\left\lfloor r / k \right\rfloor$ 个，后续每趟归并将 $m$ 个归并段合并为 $\left\lfloor m / k \right\rfloor$ 个，直至只剩一个 <!-- page: 394 --> 2027年数据结构考研复习指导 归并段。树的高度 $-1 = \lceil \log_4 r \rceil =$ 归并趟数 $S$。因此，增大归并路数 $k$，或减少初始归并段个数 $r$，均可减少归并趟数 $S$，进而减少磁盘 I/O 次数，有效提升外部排序效率。 ## 8.7.3 多路平衡归并与败者树 增大归并路数 $k$ 可减少归并趟数 $S$，从而降低 I/O 次数。然而，随着 $k$ 的增大，内部归并的时间开销也会显著增加。这是因为在 $k$ 个元素中选出关键字最小者，每次选择需要进行 $k - 1$ 次比较；每趟归并 $n$ 个元素，共需 $(n - 1)(k - 1)$ 次比较。$S$ 趟归并的总比较次数为 $$ S(n - 1)(k - 1) = \lceil \log_4 r \rceil (n - 1)(k - 1) = \lceil \log_2 r \rceil (n - 1)(k - 1) / \lceil \log_2 k \rceil $$ 式中，$(k - 1)/\lceil \log_2 k \rceil$ 随 $k$ 增大而增大，因此内部归并时间也随之增长，这将部分抵消因减少 I/O 次数带来的性能收益。因此，不能直接使用普通的多路归并方法。 为使内部归并的时间复杂度不受 $k$ 增大的影响，引入了败者树。败者树是树形选择排序的一种变体，可视为一棵完全二叉树。其 $k$ 个叶结点分别存放 $k$ 个归并段当前参与比较的元素，内部结点用于记录左右子树比较中的“败者”（关键字较大者），而“胜者”（较小者）继续向上参与比较，最终胜者的段号存于 ls[0]，其对应的关键字即为当前最小值。 **考点重点** 败者树的实现原理（2024） 如图8.17(a)所示，考虑5路归并，叶结点为b0, b1, b2, b3, b4；b3与b4比较，b4为败者，将其段号4写入父结点ls[4]；b1与b2比较，b2为败者，将段号2写入ls[3]；胜者b3与b0比较，b0为败者，将段号0写入ls[2]；最后，两个子树的胜者b3与b1比较，b1为败者，将段号1写入ls[1]；而将胜者b3的段号3写入ls[0]，表明当前最小关键字来自第3段。输出b3中的关键字后，从第3段读入下一个关键字，更新b3，并沿路径向上重新调整败者树。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)
图8.17 实现5路归并的败者树
由于 $k$ 路归并的败者树深度为 $\lceil \log_2 k \rceil + 1$，因此从 $k$ 个记录中选出最小关键字，仅需 $\lceil \log_2 k \rceil$ 次比较。此时，总的比较次数约为
$$
S(n - 1) \lceil \log_2 k \rceil = \lceil \log_4 r \rceil (n - 1) \lceil \log_2 k \rceil = (n - 1) \lceil \log_2 r \rceil
$$
可见，使用败者树后，内部归并的比较次数与归并路数 $k$ 无关。因此，在内存空间允许的前提下，增大 $k$ 可有效降低归并树高度，减少 I/O 次数，从而提高外部排序的效率。
① 本节中出现的关于比较次数的公式只是为了帮助读者理解相关原理，无须死记硬背。
<!-- page: 395 -->
第8章 椿序
383
值得注意的是，归并路数 $k$ 并非越大越好。增大 $k$ 需要增加输入缓冲区的数量。若总内存容量固定，则每个缓冲区的容量将相应减小，导致每趟归并中外存读/写的次数增加。当 $k$ 过大时，尽管归并趟数减少，但总体 I/O 次数反而可能增加，从而抵消性能增益。
## 8.7.4 置换-选择排序（生成初始归并段）
由 8.7.2 节可知，减少初始归并段个数 $r$ 同样可减少归并趟数 $S$。若待排序记录总数为 $n$，每个归并段的平均长度为 $\ell$，则归并段个数 $r = \lceil n / \ell \rceil$。采用普通内部排序方法生成的初始归并段长度通常固定（除最后一段外），其长度受限于内存工作区的大小。因此，有必要探索新方法以生成更长的初始归并段，从而减少 $r$，这就是本节要介绍的置换-选择算法。
**考虑指标** ▶ 置换-选择排序生成初始归并段的实例（2023）
设初始待排文件为 FI，归并段输出文件为 FO，内存工作区为 WA，其中 WA 可容纳 $w$ 个记录，初始时 FO 与 WA 均为空。置换-选择算法的执行步骤如下：
1）从 FI 读入 $w$ 个记录至工作区 WA。
2）从 WA 中选出当前关键字最小的记录，记为 MINIMAX 记录。
3）将该 MINIMAX 记录写入 FO。
4）若 FI 非空，则从 FI 读入下一个记录至 WA。
5）从 WA 中所有关键字不小于当前 MINIMAX 关键字的记录中，选出关键字最小者，作为新的 MINIMAX 记录。
6）重复步骤 3）～5），直至 WA 中不存在关键字不小于当前 MINIMAX 的记录为止，此时完成一个初始归并段的输出。
7）重复步骤 2）～6），直至 FI 与 WA 均为空，从而生成全部初始归并段。
通过该方法，初始归并段长度不再受限于内存大小 $w$，而取决于输入数据的分布。理想情况下（如输入基本有序），可生成长度远超 $w$ 的归并段，显著减少归并段总数。
设待排文件 $\mathrm{FI} = \{17,21,05,44,10,12,56,32,29\}$，WA 容量为 3，排序过程如表 8.2 所示。
表 8.2 置换-选择排序过程示例
| 输出文件 FO | 工作区 WA | 输入文件 FI |
| --- | --- | --- |
| — | — | 17, 21, 05, 44, 10, 12, 56, 32, 29 |
| — | 17 21 44 | 44, 10, 12, 56, 32, 29 |
| 05 | 17 21 44 | 10, 12, 56, 32, 29 |
| 05 17 | 10 21 44 | 12, 56, 32, 29 |
| 05 17 21 | 10 12 44 | 56, 32, 29 |
| 05 17 21 44 | 10 12 56 | 32, 29 |
| 05 17 21 44 56 | 10 12 32 | 29 |
| 05 17 21 44 56 # | 10 12 32 | 29 |
| 10 | 29 12 32 | — |
| 10 12 | 29 32 | — |
| 10 12 29 | 12 | — |
| 10 12 29 32 | — | — |
| 10 12 29 32 # | — | — |
上述算法，在 WA 中选择 MINIMAX 记录的过程需利用败者树来实现。
<!-- page: 396 -->
2027年数据结构考研复习指导