二、综合应用题
## 二、综合应用题
01. 已知序列 $\{503, 87, 512, 61, 908, 170, 897, 275, 653, 462\}$，采用非递归的 2 路归并排序算法对该序列做升序排序时需要几趟排序？给出每一趟的结果。
02. 设待排序的关键字序列为 $\{12, 2, 16, 30, 28, 10, 16^*, 20, 6, 18\}$，试写出使用最低位优先（LSD）基数排序算法每趟排序后的结果。
03. 【2021 统考真题】已知某排序算法如下：
void cmpCountSort(int a[], int b[], int n) {
int i, j, *count;
count = (int *)malloc(sizeof(int) * n);
// C++语言: count = new int[n];
for (i = 0; i < n; i++) count[i] = 0;
for (i = 0; i < n - 1; i++) for(j = i + 1; j < n; j++) if(a[i] < a[j]) count[j]++;
else count[i]++;
for (i = 0; i < n; i++) b[count[i]] = a[i];
free(count); // C++语言: delete count;
}
请回答下列问题。
1）若有 int a[] = {25, -10, 25, 10, 11, 19}, b[6]；，则调用 cmpCountSort(a, b, 6) 后数组 b 中的内容是什么？
2）若 a 中含有 $n$ 个元素，则算法执行过程中，元素之间的比较次数是多少？
<!-- page: 382 -->
2027年数据结构考研复习指导
3）该算法是稳定的吗？若是，阐述理由；否则，修改为稳定排序算法。
## 8.5.5 答案与解析
### 一、单项选择题
#### 01. C
我们知道插入排序不能保证在一趟排序结束后一定有元素放在最终位置上。事实上，归并排序也不能保证。例如，序列 $\{6,5,7,8,2,1,4,3\}$ 进行一趟2路归并排序（从小到大）后为 $\{5,6,7,8,1,2,3,4\}$，显然它们都未被放在最终位置上。
#### 02. C
基数排序是基于关键字各位的大小进行排序的，而不是基于关键字的比较进行的。
#### 03. D、C
归并排序在平均情况和最坏情况下的空间复杂度都是 $O(n)$，快速排序只在最坏情况下才是 $O(n)$，平均情况是 $O(\log_2 n)$。因此，归并排序是本章所有排序算法中占用辅助空间最多的。
#### 04. A
前面已讲过选择排序的比较次数与序列初始状态无关，归并排序的比较次数的数量级也与序列的初始状态无关。读者应能从算法的原理方面来考虑为什么和初始状态无关。
#### 05. B
$N$ 个元素进行 $k$ 路归并排序的趟数 $m$ 满足 $k^m = N$，即 $m = \lceil \log_k N \rceil$，本题中为 $\lceil \log_2 n \rceil$。
#### 06. B
$N$ 个元素进行 $k$ 路归并排序的趟数 $m$ 满足 $k^m = N$，这里要求的是 $k$，代入可得 $k = 3$。
#### 07. A、B
注意，当一个表中的最小元素比另一个表中的最大元素还大时，比较的次数是最少的，仅比较 $N$ 次；而当两个表中的元素依次间隔地比较时，即 $a_1 < b_1 < a_2 < b_2 < \dots < a_n < b_n$ 时，比较的次数是最多的，为 $2N - 1$ 次。
建议读者对此举一反三：若将本题中的两个有序表的长度分别设为 $M$ 和 $N$，则最多（或最少）的比较次数是多少？时间复杂度又是多少？
#### 08. C
第一趟归并后 $\{1,2\}, \{4,6\}, \{3,5\}, \{7,8\}$，共比较4次；第二趟归并后 $\{1,2,4,6\}, \{3,5,7,8\}$，共比较4次；第三趟归并后 $\{1,2,3,4,5,6,7,8\}$，共比较6次。三趟归并共需进行14次比较。
#### 09. B
这里采用2路归并排序算法，且是第二趟排序，因此每4个元素放在一起归并，可将序列划分为 $\{25,50,15,35\}, \{80,85,20,40\}$ 和 $\{36,70\}$，分别对它们进行排序后有 $\{15,25,35,50\}, \{20,40,80,85\}$ 和 $\{36,70\}$。
#### 10. D
按照所有中国人的生日排序，一方面 $N$ 是非常大的，另一方面关键字所含的排序码数为2，且一个排序码的基数为12，另一个排序码的基数为31，都是较小的常数值，因此采用基数排序可以在 $O(N)$ 内完成排序过程。
#### 11. D
本题思路来自基数排序的LSD，首先应确定 $k_{1}$、$k_{2}$ 的排序顺序，若先排 $k_{1}$ 再排 $k_{2}$，则排序结果不符合题意，排除选项A和C。再考虑排序的稳定性，当 $k_{2}$ 排好序后，再对 $k_{1}$ 排序，若对 $k_{1}$ 排序采
<!-- page: 383 -->
第8章 椿序
371
用的方法是不稳定的，则对于 $k_{1}$ 相同而 $k_{2}$ 不同的元素可能会改变相对次序，从而不一定能满足题设要求。直接插入排序是稳定的，而简单选择排序是不稳定的，只能选择选项D。
12. C
基数排序有MSD和LSD两种，基数排序是稳定的。对于选项A，不符合LSD和MSD；对于选项B，符合MSD，但关键字42、46的相对位置发生了变化；对于选项D，不符合LSD和MSD。
13. D
基数排序中建立的队列个数等于进制数。
14. C
快速排序的平均空间复杂度是 $O(\log_2n)$，归并排序的空间复杂度是 $O(n)$，其他都是 $O(1)$。
15. D
考虑两个升序链表合并，两两比较表中元素，每比较一次，确定一个元素的链接位置（取较小元素，头插法）。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，因为 $2\max(m,n) \geqslant m + n$，所以时间复杂度为 $O(\max(m,n))$。此外，每次比较把两个链表中的较小结点插入新链表的表头，直到一个链表为空，因为原链表是升序排列的，要求合并后为降序排列的，因此还要把另一个链表剩下的结点一一插入新链表的表头，不论是最好情况还是最坏情况，都需要遍历两个链表中的所有结点。
16. C
基数排序的第一趟排序是按照个位数字的大小来进行的，第二趟排序是按照十位数字的大小来进行的，排序的过程如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
17. C
基数排序的元素移动次数与序列初态无关，而其他三种排序算法都与序列初态有关。
18. C
基数排序是一种稳定的排序算法。因为采用最低位优先（LSD）的基数排序，即第一趟对个位进行分配和收集操作，所以第一趟分配和收集后的结果是{151, 301, 372, 892, 93, 43, 485, 946, 146, 236, 327, 9}，元素372之前、之后紧邻的元素分别为301和892。
19. A。
送分题。本书对归并的定义原话是“归并的含义是将两个或两个以上的有序表合并成一个新的有序表”，而2路归并是将两个有序表合并为一个新的有序表。
<!-- page: 384 -->
2027年数据结构考研复习指导
## 20. C
从左至右对这三个有序序列进行 2 路归并排序的过程如下。
① 合并(3,5)和(7,9)：比较 3 和 7（1 次），选择 3；比较 5 和 7（1 次），选择 5；剩余元素 7 和 9 直接加入。② 合并(3,5,7,9)和(6)：比较 3 和 6（1 次），选择 3；比较 5 和 6（1 次），选择 5；比较 7 和 6（1 次），选择 6；剩余元素 7 和 9 直接加入。总共比较 5 次。
## 二、综合应用题
### 01. 【解答】
$n = 10$，需要排序的趟数 $= \lceil \log_2 10 \rceil = 4$，各趟的排序结果如下：
初始序列：503, 87, 512, 61, 908, 170, 897, 275, 653, 462
第一趟：87, 503, 61, 512, 170, 908, 275, 897, 462, 653（长度为 2）
第二趟：61, 87, 503, 512, 170, 275, 897, 908, 462, 653（长度为 4）
第三趟：61, 87, 170, 275, 503, 512, 897, 908, 462, 653（长度为 8）
第四趟：61, 87, 170, 275, 462, 503, 512, 653, 897, 908（长度为 10）
### 02. 【解答】
使用链式队列的基数排序的排序过程如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
需要通过 2 次分配和收集完成排序。
### 03. 【解答】
cmpCountSort 算法基于计数排序的思想，对序列进行排序。cmpCountSort 算法遍历数组中的元素，count 数组记录比对应待排序数组元素下标大的元素个数，例如，count[1] = 3 的意思是数组 a 中有三个元素比 a[1] 小，即 a[1] 是第四大元素，a[1] 的正确位置应是 b[3]。
1）排序结果为 $b[6] = \{-10, 10, 11, 19, 25, 25\}$。
<!-- page: 385 -->
第8章 椿序
373
2）由代码 for (i=0; i<n-1; i++) 和 for (j=i+1; j<n; j++) 可知，在循环过程中，每个元素都与它后面的所有元素比较一次（所有元素都两两比较一次），比较次数之和为 $(n-1)+(n-2)+\cdots+1$，所以总比较次数为 $n(n-1)/2$。
3）不是。需要将程序中的 if 语句修改如下：
若不加等号，两个相等的元素比较时，前面元素的 count 值会加 1，则导致原序列中靠前的元素在排序后的序列中处于靠后的位置。
## 8.6 各种内部排序算法的比较及应用
### 8.6.1 内部排序算法的比较
前面讨论的排序算法很多，各种排序算法的对比是考研常考的内容。通常从五个方面进行对比：时间复杂度、空间复杂度、稳定性、适用性和过程特征。
**考点追查** ▶ 各种排序算法的特点和对比（2009、2010、2017、2020、2022、2025）
从时间复杂度看：简单选择排序、直接插入排序和冒泡排序在平均情况下的时间复杂度均为 $O(n^{2})$，且实现较为简单。其中，直接插入排序和冒泡排序在最好情况下可达 $O(n)$，而简单选择排序的时间复杂度与序列初始状态无关。希尔排序作为插入排序的改进，对较大规模的数据通常具有较高效率，但目前未知其精确的渐近时间。堆排序利用堆这种数据结构，可在 $O(n)$ 时间内完成建堆，整个排序过程的时间复杂度为 $O(n\log_2n)$。快速排序基于分治思想，最坏情况下的时间复杂度为 $O(n^{2})$，但平均性能可达 $O(n\log_2n)$，在实际应用中快速排序通常表现优异。归并排序同样基于分治思想，其分割过程与初始序列无关，因此最好、最坏和平均时间复杂度均为 $O(n\log_2n)$。
从空间复杂度看：简单选择排序、插入排序、冒泡排序、希尔排序和堆排序仅需常数级辅助空间，空间复杂度为 $O(1)$。快速排序需要递归工作栈，平均空间复杂度为 $O(\log_2 n)$，最坏情况下可能达到 $O(n)$。2路归并排序在合并操作中需要额外的辅助数组用于元素复制，空间复杂度为 $O(n)$。虽有方法可减少辅助空间，但通常会导致算法复杂度显著增加，甚至影响时间效率。
**考点追查** ▶ 各种排序算法的稳定性及分析（2021、2023）
从稳定性看：插入排序、冒泡排序、归并排序和基数排序是稳定的排序算法，而简单选择排序、快速排序、希尔排序和堆排序都是不稳定的。在平均时间复杂度为 $O(n\log_2n)$ 的排序算法中，只有归并排序是稳定的。判断排序算法是否稳定，关键在于分析其操作是否会改变相等元素的相对次序；对于不稳定的算法，通常可通过构造一个反例加以验证。
**考点追查** ▶ 各种排序算法的适用性（2017）
从适用性看：折半插入排序、希尔排序、快速排序和堆排序适用于顺序存储。直接插入排序、冒泡排序、简单选择排序、归并排序和基数排序既适用于顺序存储，也适用于链式存储。
**考点追查** ▶ 各种排序算法的过程特征（2012）
从过程特征看：不同排序算法在一趟或几趟处理后的中间结果通常是不同的。考研题目常给出初始序列和部分排序后的结果，要求判断所用的排序方法。这就要求考生熟练掌握各类算法的过程特征。如冒泡排序、简单选择排序和堆排序在每趟处理后都能确定当前最大（或最小）元素的最终位置，而快速排序在一趟划分后，至少能确定一个元素（枢轴）的最终位置等。
<!-- page: 386 -->
2027年数据结构考研复习指导
表8.1列出了各种排序算法的时空复杂度和稳定性情况。其中，空间复杂度仅列出平均情况；由于希尔排序的时间复杂度依赖于所选的增量序列，因此无法给出精确表达式。
表 8.1 各种排序算法的性质
| 算法种类 | 时间复杂度 | | | 空间复杂度 | 是否稳定 |
| --- | --- | --- | --- | --- | --- |
| | 最好情况 | 平均情况 | 最坏情况 | | |
| 直接插入排序 | O(n) | O(n²) | O(n³) | O(1) | 是 |
| 冒泡排序 | O(n) | O(n²) | O(n³) | O(1) | 是 |
| 简单选择排序 | O(n²) | O(n²) | O(n³) | O(1) | 否 |
| 希尔排序 | | | | O(1) | 否 |
| 快速排序 | O(nlog₂n) | O(nlog₂n) | O(n²) | O(log₂n) | 否 |
| 堆排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(1) | 否 |
| 2路归并排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(n) | 是 |
| 基数排序 | O(d(n + r)) | O(d(n + r)) | O(d(n + r)) | O(r) | 是 |
## 8.6.2 内部排序算法的应用
通常情况，对排序算法的比较和应用应考虑以下情况。
**特别说明** 选取排序算法时需要考虑的因素（2019）
### 1. 选取排序算法需要考虑的因素
1）待排序元素的个数 $n$。
2）待排序序列的初始状态（如是否基本有序）。
3）关键字的结构及其分布情况。
4）对稳定性的要求。
5）存储结构类型及辅助空间的限制等。
### 2. 排序算法选型小结
1）若 $n$ 较小，可采用直接插入排序或简单选择排序。直接插入排序的记录移动次数通常多于简单选择排序，因此当记录本身信息量较大时，简单选择排序更为合适。
2）若 $n$ 较大，应采用时间复杂度为 $O(n\log_2n)$ 的排序算法，如快速排序、堆排序或归并排序。当关键字随机分布时，快速排序通常被认为是最高效的基于比较的内部排序算法。堆排序所需辅助空间少于快速排序，且不会退化到最坏情况，但两者均为不稳定排序。若既要求稳定性，又希望达到 $O(n\log_2n)$ 的时间复杂度，则应选用归并排序。
3）若初始序列已基本有序，则直接插入或冒泡排序更为高效，因其最好时间复杂度为 $O(n)$。
4）在基于比较的排序算法中，每次比较两个关键字仅有两种可能的结果，因此其执行过程可用一棵判定树来描述。由此可证明：对于 $n$ 个关键字的随机排列，任何基于比较的排序算法，在最坏情况下至少需要 $O(n\log_2n)$ 的时间。
5）若 $n$ 很大，且关键字位数较少、可分解为多个子关键字（如整数、字符串），则基数排序是更优选择，因其时间复杂度可接近线性。
6）当记录本身信息量较大（如包含大量字段或大对象）时，为避免因频繁移动记录而产生高昂开销，宜采用链表作为存储结构，此时插入类或归并类排序更具优势。
## 8.6.3 本节试题精选
### 一、单项选择题
01. 若要求排序是稳定的，且关键字为实数，则在下列排序算法中应选（）。
<!-- page: 387 -->
第8章 排序
375
A. 直接插入排序
B. 选择排序
C. 基数排序
D. 快速排序
02. 以下排序算法中时间复杂度为 $O(n \log_2 n)$ 且稳定的是（ ）。
A. 堆排序
B. 快速排序
C. 归并排序
D. 直接插入排序
03. 设被排序的结点序列共有 $n$ 个结点，在该序列中的结点已十分接近有序的情况下，用直接插入排序、归并排序和快速排序对其进行排序，这些算法的时间复杂度应为（ ）。
A. $O(n), O(n), O(n)$
B. $O(n), O(n \log_2 n), O(n \log_2 n)$
C. $O(n), O(n \log_2 n), O(n^2)$
D. $O(n^{2}), O(n \log_2 n), O(n^{2})$
04. 下列排序算法中属于稳定排序的是（①），平均时间复杂度为 $O(n \log_2 n)$ 的是（②），在最好的情况下，时间复杂度可以达到线性时间的有（③）。（注：多选题）
I. 冒泡排序
II. 堆排序
III. 选择排序
IV. 直接插入排序
V. 希尔排序
VI. 归并排序
VII. 快速排序
05. 就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是（ ）。
A. 堆排序<快速排序<归并排序
B. 堆排序<归并排序<快速排序
C. 堆排序>归并排序>快速排序
D. 堆排序>快速排序>归并排序
06. 排序越数与序列的初始状态无关的排序算法是（ ）。
I. 快速排序
II. 简单选择排序
III. 冒泡排序
IV. 基数排序
A. I、III
B. II、IV
C. I、II、IV
D. I、IV
07. 排序越数与序列的初始状态有关的排序算法是（ ）。
A. 直接插入排序
B. 2路归并排序
C. 快速排序
D. 堆排序
08. 对 $n$ 个元素进行排序，其排序越数肯定为 $n - 1$ 趣的排序算法是（ ）。
A. 直接插入排序和快速排序
B. 冒泡排序和快速排序
C. 简单选择排序和直接插入排序
D. 简单选择排序和冒泡排序
09. 若序列的初始状态为 $\{1,2,3,4,5,10,6,7,8,9\}$，要想使得排序过程中的元素比较次数最少，则应该采用（ ）方法。
A. 插入排序
B. 选择排序
C. 希尔排序
D. 冒泡排序
10. 对于元素个数相同的不同初始序列，总比较次数大致相同的排序算法是（ ）。
A. 折平插入排序和简单选择排序
B. 基数排序和归并排序
C. 冒泡排序和快速排序
D. 堆排序
11. 一般情况下，以下查找效率最低的数据结构是（ ）。
A. 有序顺序表
B. 二叉排序树
C. 堆
D. 半衡二叉树
12. 一台计算机具有多核 CPU，可以同时执行相互独立的任务。归并排序的各个归并段可以并行执行，在下列排序算法中，不可以并行执行的有（ ）。
I. 基数排序
II. 快速排序
III. 冒泡排序
IV. 堆排序
A. I、III
B. I、II
C. I、III、IV
D. II、IV
13. 【2009统考真题】若数据元素序列{11, 12, 13, 7, 8, 9, 23, 4, 5}是采用下列排序算法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。
A. 冒泡排序
B. 插入排序
C. 选择排序
D. 2路归并排序
14. 【2010统考真题】对一组数据(2, 12, 16, 88, 5, 10)进行排序，若前3趟排序结果如下：
第一趟排序结果：2, 12, 16, 5, 10, 88
第二趟排序结果：2, 12, 5, 10, 16, 88
第三趟排序结果：2, 5, 10, 12, 16, 88
<!-- page: 388 -->
2027年数据结构考研复习指导
则采用的排序算法可能是（）。
A. 冒泡排序
B. 希尔排序
C. 归并排序
D. 基数排序
15.【2012统考真题】在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序算法中，每趟排序结束都至少能够确定一个元素最终位置的方法是（）。
I. 简单选择排序 II. 希尔排序 III. 快速排序 IV. 堆排序 V. 2路归并排序
A. 仅I、III、IV B. 仅I、III、V C. 仅II、III、IV D. 仅III、IV、V
16.【2017统考真题】在内部排序时，若选择了归并排序而未选择插入排序，则可能的理由是（）。
I. 归并排序的程序代码更短
II. 归并排序的占用空间更少
III. 归并排序的运行效率更高
A. 仅 II
B. 仅 III
C. 仅 I、II
D. 仅 I、III
17.【2017统考真题】下列排序算法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是（）。
I. 插入排序 II. 选择排序 III. 冒泡排序 IV. 希尔排序 V. 堆排序
A. 仅 I、II
B. 仅 II、III
C. 仅 III、IV
D. 仅 IV、V
18.【2019统考真题】选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是（）。
I. 数据的规模 II. 数据的存储方式 III. 算法的稳定性 IV. 数据的初始状态
A. 仅 III
B. 仅 I、II
C. 仅 II、III、IV
D. I、II、III、IV
19.【2020统考真题】对大部分元素已有序的数组排序时，直接插入排序比简单选择排序效率更高，其原因是（）。
I. 直接插入排序过程中元素之间的比较次数更少
II. 直接插入排序过程中所需的辅助空间更少
III. 直接插入排序过程中元素的移动次数更少
A. 仅 I
B. 仅 III
C. 仅 I、II
D. I、II 和 III
20.【2022统考真题】对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是（）。
I. 大部分元素已有序
II. 待排序元素数量很少
III. 要求空间复杂度为 $O(1)$
IV. 要求排序算法是稳定的
A. 仅I、II
B. 仅III、IV
C. 仅I、II、IV
D. I、II、III、IV
21.【2023统考真题】下列排序算法中，不稳定的是（）。
I. 希尔排序
II. 归并排序
III. 快速排序
IV. 堆排序
V. 基数排序
A. 仅 I、II
B. 仅 II、V
C. 仅 I、III、IV
D. 仅 III、IV、V
22.【2025统考真题】在下列排序算法中，最坏情况下元素移动次数最少的是（）。
A. 起泡排序
B. 直接插入排序
C. 快速排序
D. 简单选择排序
23.【2025统考真题】对含9个关键字的初始序列进行排序，若序列的变化情况如下表所示，则下列排序算法中，采用的是（）。
| 初始序列 | 5, 25, 40, 30, 10, 20, 45, 15, 35 |
| --- | --- |
| 第1趟排序后的序列 | 5, 10, 20, 30, 15, 35, 45, 25, 40 |
| 第2趟排序后的序列 | 5, 10, 15, 25, 20, 30, 40, 35, 45 |
<!-- page: 389 -->
第8章 排序
377
A. 希尔排序
B. 基数排序
C. 归并排序
D. 折年插入排序