03. 【解答】
## 03. 【解答】 在基于比较的排序算法中，插入排序、快速排序和归并排序只有在将元素全部排完序后，才能得到前 $k$ 个最小的元素序列，算法的效率不高。 冒泡排序、堆排序和简单选择排序可以，因为它们在每一趟中都可以确定一个最小的元素。采用堆排序最合适，对于 $n$ 个元素的序列，建立初始堆的时间不超过 $4n$，取得第 $k$ 个最小元素之前的排序序列所花的时间为 $k\log_2n$，总时间为 $4n + k\log_2n$；冒泡和简单选择排序完成此功能所花的时间为 $kn$，当 $k \geqslant 5$ 时，通过比较可以得出堆排序最优。 ## 注意 求前 $k$ 个最小元素的顺序排列可采用的排序算法有冒泡排序、堆排序和简单选择排序。 ## 04. 【解析】 1）除最后一个分支结点外，其余每个分支结点都有4个孩子，所以该树是完全4叉树。插入元素65后，再删除堆顶元素的树形分别如下图1和图2所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图1 插入65后的树形
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2 删除堆顶元素后的树形 2）父结点的编号为 $(k - 1) / 4$，第 $i$ 个孩子的编号为 $4k + i$，$i = 1,2,3,4$。 3）与二叉堆类似，插入和删除操作都有向上、向下调整的过程，操作时间都与树的高度有关。因此，插入和删除操作的时间复杂度都为 $O(\log_m n)$，其中 $n$ 为元素个数。 ## 05. 【解答】 算法的思想是：每趟在原始链表中摘下关键字最大的结点，把它插入结果链表的最前端。在原始链表中摘下的关键字越来越小，在结果链表前端插入的关键字也越来越小，因此最后形成的结果链表中的结点将按关键字非递减的顺序有序链接。 单链表的定义如第2章所述，假设它不带表头结点。 <!-- page: 374 --> 2027年数据结构考研复习指导## 06. 【解答】 将顺序表 L[1...n] 视为一个完全二叉树，扫描所有分支结点，遇到孩子结点的关键字小于根结点的关键字时返回 false，扫描完后返回 true。算法的实现如下：void selectSort(LinkedList&amp; L) { //对不带表头结点的单链表 L 执行简单选择排序 LinkNode *h=L,*p,*q,*r,*s; L=NULL; while(h!=NULL) { //持续扫描原链表 p=s=h;q=r=NULL; //指针 s 和 r 记忆最大结点和其前驱：p 为工作指针，q 为其前驱 while(p!=NULL) { //扫描原链表寻找最大结点 s if(p-&gt;data&gt;s-&gt;data){s=p;r=q;} //找到更大的，记忆它和它的前驱 q=p;p=p-&gt;link; //继续寻找 } if(s==h) h=h-&gt;link; //最大结点在原链表前端 else r-&gt;link=s-&gt;link; //最大结点在原链表表内 s-&gt;link=L;L=s; //结点 s 插入结果链前端 } }## 07. 【解答】 1）题目要求整个队列所占用的空间不变，入队操作和出队操作的时间复杂度始终保持为 $O(\log_2 n)$，则应采用顺序存储结构，即用数组实现大根堆。 2）优先队列的数据结构定义如下： 3）入队操作：bool IsMinHeap(ElemType A[], int len) { if(len%2==0) { //len 为偶数，有一个单分支结点 if(A[len/2] &gt; A[len]) //判断单分支结点 return false; for(i=len/2-1;i&gt;=1;i--) //判断所有双分支结点 if(A[i] &gt; A[2*i] || A[i] &gt; A[2*i+1]) return false; } else { //len 为奇数时，没有单分支结点 for(i=len/2;i&gt;=1;i--) //判断所有双分支结点 if(A[i] &gt; A[2*i] || A[i] &gt; A[2*i+1]) return false; } return true; }出队操作： 当数据全部扫描完毕，数组A[0]～A[9]保存的就是最小的10个数。 【方法2】定义含10个元素的大根堆H，元素值均为该堆元素类型能表示的最大数MAX。 当数据全部扫描完毕，堆H中保存的就是最小的10个数。 2）算法平均情况下的时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。 # 8.5 归并排序、基数排序和计数排序 ## 8.5.1 归并排序 **特点组注** 2路归并操作的功能（2022） 归并排序不同于基于交换或选择的排序方法，其核心思想是“归并”——即将两个或多个有序序列合并为一个更长的有序序列。具体地，对于含有 $n$ 个记录的待排序表，可将其视为 $n$ 个长度为1的有序子表；然后两两归并，得到 $\lceil n / 2 \rceil$ 个长度为2（或1）的有序子表；继续两两归并……如此重复，直至合并成一个长度为 $n$ 的有序表为止，这种排序算法称为2路归并排序。 图8.9展示了一个2路归并排序的示例，经过三趟归并后合并为一个完整的有序序列。void enqueue(PriorityQueue *pq, int value, int priority) { if(pq-&gt;size &gt;= MAX SIZE) { 队列已满，无法入队; return; } 将新元素添加到堆的末尾； 向上调整堆； }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.9 2路归并排序示例 **特点组注** （算法题）归并排序思想的应用（2011） 归并操作由函数 Merge() 实现，其功能是将同一顺序表中前后相邻的两个有序子表合并为一个有序表。首先将这两个子表的所有元素复制到辅助数组B中。随后，设置两个指针分别指向B中两段的起始位置，依次比较当前元素的关键字，将较小者放入原数组A的对应位置。其中一段的所有元素均已复制完毕后，将另一段的剩余部分直接复制到A中。具体实现如下： <!-- page: 376 --> 2027年数据结构考研复习指导# 注意 在上述代码中，最后两个 while 循环仅有一个会执行。 在非递归的归并排序中，一趟归并操作是指：将当前序列划分为若干长度为 $h$ 的有序段，然后两两归并，形成长度为 $2h$ 的有序段。若序列总长度为 $n$ ，则每趟需调用 $\lceil n / (2h) \rceil$ 次 Merge() 函数。整个排序过程共需进行 $\lceil \log_2 n \rceil$ 趟归并。 递归形式的2路归并排序基于分治策略，其过程如下。 分解：将含 $n$ 个元素的待排序表从中间分为两个子表，每个子表含约 $n/2$ 个元素。 递归求解：对两个子表分别递归地进行归并排序。 合并：合并两个已排序的子表得到排序结果。 2路归并排序的递归实现如下： ## 考虑递归 ### 2路归并比较次数的分析（2024） 2路归并排序算法的性能分析如下： 空间效率：归并操作需要一个与待排序表等长的辅助数组，因此空间复杂度为 $O(n)$ 。 时间效率：每趟归并需要遍历所有 $n$ 个元素，时间复杂度为 $O(n)$ ：共需进行 $\lceil \log_2 n \rceil$ 趟，总时间复杂度为 $O(n \log_2 n)$ 。 稳定性：在归并过程中，当两个元素关键字相等时，优先取自前一段，从而保持了相同关键字元素的相对次序。因此2路归并排序是稳定的排序算法。 适用性：归并排序仅需顺序访问元素，因此适用于顺序存储和链式存储的线性表。 # 注意 一般而言，对 $N$ 个元素进行 $k$ 路归并排序时，排序的趟数 $m$ 满足 $k^m = N$ ，从而 $m = \log_k N$ ，又考虑到 $m$ 为整数，因此 $m = \lceil \log_k N \rceil$ 。这与前述的2路归并排序算法是一致的。 <!-- page: 377 --> 第8章 椿序 365 ## 8.5.2 基数排序 基数排序是一种很特别的排序算法，它不依赖于元素间的比较，而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。 假设长度为 $n$ 的线性表中，每个结点 $a_{j}$ 的关键字由 $d$ 个分量 $(k_{j}^{d-1}, k_{j}^{d-2}, \dots, k_{j}^{1}, k_{j}^{0})$ 组成，满足 $0 \leqslant k_{j}^{i} \leqslant r - 1$（$0 \leqslant j < n, 0 \leqslant i \leqslant d - 1$）。其中 $k_{j}^{d-1}$ 为最高位关键字，$k_{j}^{0}$ 为最低位关键字。 为实现多关键字排序，通常有两种方法：第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列；第二种是最低位优先（LSD）法，按关键字位权重递增依次进行排序，最后形成一个有序序列。 以下描述以基数 $r$ 进行的最低位优先基数排序过程。算法使用 $r$ 个队列 $Q_{0}, Q_{1}, \dots, Q_{r-1}$。对每一位 $i = 0, 1, \dots, d-1$，依次执行一次分配和收集操作（每轮本质上是一次稳定的排序）： ① 分配：初始化所有队列为空，然后依次扫描线性表中的每个结点 $a_{j}$（$j = 0, 1, \dots, n-1$），若 $a_{j}$ 在当前位上的关键字值为 $k$，则将其加入队列 $Q_{k}$。 ② 收集：按 $Q_{0}$，到 $Q_{r-1}$ 的顺序，依次将各队列中的结点连接起来，形成新的线性表。 **参考信息：** 基数排序的中间过程的分析（2013、2021） 通常采用链式基数排序。例如，对以下10个记录进行排序： $$ \longrightarrow \boxed{278} \longrightarrow \boxed{109} \longrightarrow \boxed{063} \longrightarrow \boxed{930} \longrightarrow \boxed{589} \longrightarrow \boxed{184} \longrightarrow \boxed{505} \longrightarrow \boxed{269} \longrightarrow \boxed{008} \longrightarrow \boxed{083} $$ 假设所有关键字均为小于1000的正整数，基数 $r = 10$，在排序过程中需借助10个链队列，关键字由3位子关键字构成：$\mathrm{K}^{1}\mathrm{K}^{2}\mathrm{K}^{3}$，分别代表百位、十位和个位，共需进行三趟分配与收集操作。第一趟分配用最低位子关键字 $\mathrm{K}^{3}$（个位）进行，将所有记录按个位数字分配到 $Q_{0}$ 到 $Q_{9}$ 中，如图8.10(a)所示，随后按队列顺序收集，结果如图8.10(b)所示。ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType)); //辅助数组B void Merge(ElemType A[], int low, int mid, int high) { //表A的两段A[low_mid]和A[mid+1_high]各自有序，将它们合并成一个有序表 int i, j, k; for (k=low; k&lt;=high; k++) B[k]=A[k]; //将A中所有元素复制到B中 for (i=low, j=mid+1, k=i; i&lt;=mid&amp;&amp;j&lt;=high; k++) { if (B[i]&lt;=B[j]) //比较B的两个段中的元素 A[k]=B[i++]; //将较小值复制到A中 else A[k]=B[j++]; } while (i&lt;=mid) A[k++] = B[i++]; //若第一个表未检测完，复制 while (j&lt;=high) A[k++] = B[j++]; //若第二个表未检测完，复制 }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 第一趟分配后
(b) 第一趟收集后
第二趟分配用次低位子关键字 $\mathrm{K}^{2}$（十位）进行，将所有十位相等的记录分配到同一个队列，如图8.11(a)所示。第二趟收集后的结果如图8.11(b)所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.10 第一趟链式基数排序操作
(a) 第二趟分配后
(b) 第二趟收集后
图8.11 第二趟链式基数排序操作
<!-- page: 378 -->
2027年数据结构考研复习指导
第三趟分配用最高位子关键字 $\mathrm{K}^{1}$（百位）进行，将所有百位相等的记录分配到同一个队列，如图8.12(a)所示，第三趟收集后的结果如图8.12(b)所示，至此整个排序结束。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 第三趟分配后
(b) 第三趟收集后
图8.12 第三趟链式基数排序操作
基数排序算法的性能分析如下。
空间效率：一趟排序需要的辅助空间为 $r$（$r$ 个队列；$r$ 个队头指针和 $r$ 个队尾指针），但这些结构在后续各趟排序中可重复使用，因此空间复杂度为 $O(r)$。
**考虑语法** 元素的移动次数与序列初态无关的排序算法（2015）
时间效率：共需进行 $d$ 趟分配与收集。每趟分配需遍历 $n$ 个元素，所需时间为 $O(n)$；每趟收集需处理 $r$ 个队列，所需时间为 $O(r)$。总时间复杂度为 $O(d(n + r))$，它与序列的初始状态无关。
稳定性：由于每趟分配按原序列顺序入队，收集按队列编号顺序出队，相同关键字的元素相对次序不会改变，因此基数排序是稳定的排序算法。
适用性：基数排序适用于顺序存储和链式存储的线性表，链式结构尤其适合。
## *8.5.3 计数排序
**考虑语法** （算法题）计数排序思想的应用（2013、2015、2018）
计数排序也是一种不依赖于比较的排序算法。其核心思想是：对每个待排序元素 $x$，统计小于 $x$ 的元素个数，从而确定 $x$ 在有序序列中的位置。例如，若有8个元素小于 $x$，则 $x$ 应排在第9位。当存在重复元素时，需对算法稍做调整，以保证排序的稳定性。
### 注意
计数排序并不在统考大纲的范围内，但其排序思想在历年真题中多次涉及。
在计数排序的实现中，假设输入是一个数组 $\mathsf{A}[\mathsf{n}]$，序列长度为 $\mathsf{n}$。算法还需两个辅助数组：B[n]用于存放排序结果，C[k]用于存储计数值。具体做法是：以A中的元素值作为C的下标（索引），而C[x]保存的是值为x的元素出现的次数。算法实现如下：
**考虑语法** 计数排序相关的思想和代码的分析（2021）
void CountSort(ElemType A[], ElemType B[], int n, int k) {
int i, C[k];
for (i = 0; i &lt; k; i++)
C[i] = 0; //初始化计数数组
for (i = 0; i &lt; n; i++)
C[A[i]] = C[A[i]] + 1; //C[A[i]]保存的是等于A[i]的元素个数
for (i = 1; i &lt; k; i++)
C[i] = C[i] + C[i - 1]; //C[x]保存的是小于或等于x的元素总数
for (i = n - 1; i &gt;= 0; i--) { //从后往前遍历输入数组
B[C[A[i]] - 1] = A[i]; //将元素A[i]放置到输出数组B[]的正确位置
<!-- page: 379 -->
第8章 排序
367
```txt
C[A[i]] = C[A[i]] - 1; //更新计数数组，确保相同元素的相对顺序
}
第一个 for 循环将计数数组 C 初始化为 0。第二个 for 循环遍历输入数组 A，对每个元素 x = A[i]，将 C[x] 加 1；循环结束后，C[x] 保存的是值等于 x 的元素个数。第三个 for 循环通过累加计算后，使 C[x] 变为小于或等于 x 的元素总数，即 x 在最终有序序列中的最后可能出现的位置（从 1 开始计数）。第四个 for 循环从后往前遍历 A：对于每个 A[i]，将其放入输出数组 B 的 C[A[i]] - 1 位置（下标从 0 开始），然后将 C[A[i]] 减 1。若 A 中无重复元素，则 C[A[i]] - 1 即为 A[i] 在 B 中的唯一正确位置；若存在重复元素，“从后往前遍历+计数递减”的策略确保在 A 中先出现的相同元素，在 B 中仍排在前面，从而保证排序的稳定性。
假设输入数组 A[] = {2, 4, 3, 0, 2, 3}，第二个 for 循环结束后，辅助数组 C 的状态如图 8.13(a) 所示；第三个 for 循环结束后，C 的状态如图 8.13(b) 所示。图 8.13(c) 至图 8.13(h) 分别展示了第四个 for 循环每次迭代后，输出数组 B 和辅助数组 C 的变化情况。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 8.13 计数排序的过程
由上述过程可知，计数排序利用了数组下标天然有序的特性：将元素值映射为辅助数组的下标，通过统计频次并累加，再反向填充输出数组，从而完成排序。
计数排序算法的性能分析如下。
空间效率：计数排序是一种以空间换时间的算法。输出数组 B 的长度为 n；计数数组 C 的长度为 k，空间复杂度为 $O(n + k)$。若不将输出数组视为辅助空间，则空间复杂度为 $O(k)$。算法要求待排序元素为非负整数，取值范围（如 $0 \sim k - 1$）不宜过大，否则会导致辅助空间浪费。
时间效率：上述代码的第 1 和第 3 个 for 循环耗时 $O(k)$，第 2 和第 4 个 for 循环耗时 $O(n)$，总时间复杂度为 $O(n + k)$。因此，当 $k = O(n)$ 时，计数排序可达线性时间 $O(n)$；但当 $k \gg O(n \log_2 n)$ 时，其效率反而不如基于比较的排序算法（如快速排序、堆排序等）。
稳定性：上述代码的第 4 个 for 循环从后往前遍历输入数组，相同元素在输出数组中的相对次序得以保持，因此计数排序是稳定的排序算法。
适用性：计数排序适用于顺序存储的线性表。
## 8.5.4 本节试题精选
### 一、单项选择题
01. 以下排序算法中，（ ）在一趟结束后不一定能选出一个元素放在其最终位置上。
<!-- page: 380 -->
2027年数据结构考研复习指导
A. 简单选择排序
B. 冒泡排序
C. 归并排序
D. 堆排序
02. 以下排序算法中，（）不需要进行关键字的比较。
A. 快速排序
B. 归并排序
C. 基数排序
D. 堆排序
03. 在下列排序算法中，平均情况下空间复杂度为 $O(n)$ 的是（），最坏情况下空间复杂度为 $O(n)$ 的是（）。
I. 希尔排序
II. 堆排序
III. 冒泡排序
IV. 归并排序
V. 快速排序
VI. 基数排序
A. I、IV、VI
B. II、V
C. IV、V
D. IV
04. 下列排序算法中，排序过程中比较次数的数量级与序列初始状态无关的是（）。
A. 归并排序
B. 插入排序
C. 快速排序
D. 冒泡排序
05. 2路归并排序中，归并越数的数量级是（）。
A. $O(n)$
B. $O(\log_2 n)$
C. $O(n \log_2 n)$
D. $O(n^2)$
06. 若对27个元素只进行三趟多路归并排序，则选取的归并路数最少为（）。
A. 2
B. 3
C. 4
D. 5
07. 将两个各有 $N$ 个元素的有序表合并成一个有序表，最少的比较次数是（），最多的比较次数是（）。
A. $N$
B. $2N - 1$
C. $2N$
D. $N - 1$
08. 用归并排序算法对序列 $\{1,2,6,4,5,3,8,7\}$ 进行排序，共需要进行（）次比较。
A. 12
B. 13
C. 14
D. 15
09. 一组经过第一趟2路归并排序后的记录的关键字为 $\{25, 50, 15, 35, 80, 85, 20, 40, 36, 70\}$，其中包含5个长度为2的有序表，用2路归并排序算法对该序列进行第二趟归并后的结果为（）。
A. $15, 25, 35, 50, 80, 20, 85, 40, 70, 36$
B. $15, 25, 35, 50, 20, 40, 80, 85, 36, 70$
C. $15, 25, 50, 35, 80, 85, 20, 36, 40, 70$
D. $15, 25, 35, 50, 80, 20, 36, 40, 70, 85$
10. 若将中国人按照生日（不考虑年份，只考虑月、日）来排序，则使用下列排序算法时，最快的是（）。
A. 归并排序
B. 希尔排序
C. 快速排序
D. 基数排序
11. 设线性表中每个元素有两个数据项 $k_{1}$ 和 $k_{2}$，现对线性表按以下规则进行排序：先看数据项 $k_{1}$，$k_{1}$ 值小的元素在前，大的元素在后；在 $k_{1}$ 值相同的情况下，再看 $k_{2}$，$k_{2}$ 值小的元素在前，大的元素在后。满足这种要求的排序算法是（）。
A. 先按 $k_{1}$ 进行直接插入排序，再按 $k_{2}$ 进行简单选择排序
B. 先按 $k_{2}$ 进行直接插入排序，再按 $k_{1}$ 进行简单选择排序
C. 先按 $k_{1}$ 进行简单选择排序，再按 $k_{2}$ 进行直接插入排序
D. 先按 $k_{2}$ 进行简单选择排序，再按 $k_{1}$ 进行直接插入排序
12. 对 $\{05, 46, 13, 55, 94, 17, 42\}$ 进行基数排序，一趟排序的结果是（）。
A. $05, 46, 13, 55, 94, 17, 42$
B. $05, 13, 17, 42, 46, 55, 94$
C. $42, 13, 94, 05, 55, 46, 17$
D. $05, 13, 46, 55, 17, 42, 94$
13. 有 $n$ 个十进制整数进行基数排序，其中最大的整数为5位，则基数排序过程中临时建立的队列个数是（）。
A. $n$
B. 2
C. 5
D. 10
14. 下列各种排序算法中，（）需要的附加存储空间最大。
<!-- page: 381 -->
第8章 排序
369
A. 快速排序
B. 堆排序
C. 归并排序
D. 插入排序
15. 【2013 统考真题】已知两个长度分别为 $m$ 和 $n$ 的升序链表，若将它们合并为长度为 $m + n$ 的一个降序链表，则最坏情况下的时间复杂度为（ ）。
A. $O(n)$
B. $O(mn)$
C. $O(\min(m, n))$
D. $O(\max(m, n))$
16. 【2013 统考真题】对给定的关键字序列 110, 119, 007, 911, 114, 120, 122 进行基数排序，第二趟分配、收集后得到的关键字序列为（ ）。
A. 007, 110, 119, 114, 911, 120, 122
B. 007, 110, 119, 114, 911, 122, 120
C. 007, 110, 911, 114, 119, 120, 122
D. 110, 120, 911, 122, 114, 007, 119
17. 【2015 统考真题】下列排序算法中，元素的移动次数与关键字的初始状态无关的是（ ）。
A. 直接插入排序
B. 冒泡排序
C. 基数排序
D. 快速排序
18. 【2021 统考真题】设数组 $S[] = \{93, 946, 372, 9, 146, 151, 301, 485, 236, 327, 43, 892\}$，采用最低位优先（LSD）基数排序将 S 排列成升序序列。第一趟分配、收集后，元素 372 之前、之后紧邻的元素分别为（ ）。
A. 43, 892
B. 236, 301
C. 301, 892
D. 485, 301
19. 【2022 统考真题】使用 2 路归并排序对含 $n$ 个元素的数组 M 进行排序时，2 路归并排序的功能是（ ）。
A. 将两个有序表合并为一个新的有序表
B. 将 M 划分为两部分，两部分的元素个数大致相等
C. 将 M 划分为 $n$ 个部分，每个部分中仅含有一个元素
D. 将 M 划分为两部分，一部分元素的值均小于另一部分元素的值
20. 【2024 统考真题】现有由关键字组成的 3 个有序序列 (3, 5)，(7, 9) 和 (6)，若按从左至右的次序选择有序序列进行 2 路归并排序，则关键字之间的总比较次数是（ ）。
A. 3
B. 4
C. 5
D. 6