03. D
#### 03. D
选择排序在每趟结束后可以确定一个元素的最终位置，不对。插入排序，第 $i$ 趟后前 $i + 1$ 个元素应该是有序的，不对。第二趟 $\{20, 15\}$ 和 $\{21, 25\}$ 是反序的，因此不是归并排序。快速排序每趟都将基准元素放在其最终位置，然后以它为基准将序列划分为两个子序列。观察题中的排序过程，可知是快速排序。
#### 04. C
以 46 为基准元素，首先从后往前扫描比 46 小的元素，并与之进行交换，而后从前往后扫描比 46 大的元素并将 46 与该元素交换，得到 $(40, 46, 56, 38, 79, 84)$。此后，继续重复从后往前扫描与从前往后扫描的操作，直到 46 处于最终位置。
#### 05. D
当待排序数据为基本有序时，每次选取第 $n$ 个元素为基准，会导致划分区间分配不均匀，不利于发挥快速排序算法的优势。相反，当待排序数据分布较为随机时，基准元素能将序列划分为两个长度大致相等的序列，这时才能发挥快速排序的优势。
#### 06. D
这里问的是平均性能，选项 A、B 的平均性能都会达到 $O(n^{2})$，而希尔排序虽然大大降低了直接插入排序的时间复杂度，但其平均性能不如快速排序。另外，虽然众多排序算法的平均时间复杂度也是 $O(n\log_2n)$，但快速排序算法的常数因子是最小的。
#### 07. A
若为插入排序，则前三个元素应该是有序的，显然不对。而冒泡排序和选择排序经过两趟排序后应该有两个元素处于最终位置（最左/右端），无论是按从小到大还是从大到小排序，数据序列中都没有两个满足这样的条件的元素，因此只可能选择选项 A。
【另解】先写出排好序的序列，并和题中的序列进行对比。
<!-- page: 359 -->
第8章 椿序
347
题中序列：2 1 4 9 8 10 6 20
已排好序序列：1 2 4 6 8 9 10 20
在已排好序的序列中，与题中序列相同的元素有4、8和20，最左和最右两个元素与题中的序列不同，所以不可能是冒泡排序、选择排序或插入排序。
## 08. C
从后往前冒泡的过程为，第一趟{1,8,9,10,4,5,6,20,2}，第二趟{1,2,8,9,10,4,5,6,20}，第三趟{1,2,4,8,9,10,5,6,20}，第四趟{1,2,4,5,8,9,10,6,20}，第五趟{1,2,4,5,6,8,9,10,20}，经过第五趟冒泡后，序列已经全局有序，因此选择选项C。实际每趟冒泡发生交换后可以判断是否会产生新的逆序对，若不会产生，则本趟冒泡之后序列全局有序，所以最少5趟即可。
## 09. B
第一趟从左往右的排序结果为4,7,3,5,6,8,9,1,2,10；第二趟从右往左的排序结果为1,4,7,3,5,6,8,9,2,10；第三趟从左往右的排序结果为1,4,3,5,6,7,8,2,9,10；第四趟从右往左的排序结果为1,2,4,3,5,6,7,8,9,10；第五趟从左往右的排序结果为1,2,3,4,5,6,7,8,9,10，此时序列已有序，但仍需进行一趟无交换的排序才能确定序列已有序，因此共需6趟排序。
## 10. A、D
当每趟的枢轴值都把表等分为长度相近的两个子表时，速度是最快的；当表本身已经有序或逆序时，速度最慢。选项D中的序列已按关键字排好序，因此它是最慢的，而选项A中第一趟枢轴值21将表划分为两个子表{9,17,5}和{25,23,30}，而后对两个子表划分时，枢轴值再次将它们等分，所以该序列是快速排序最优的情况，速度最快。针对其他选项，可以进行类似的分析。
## 11. B
对各序列分别执行一趟快速排序，可做如下分析（以选项A为例）：枢轴值为92，因此35移动到第一个位置，96移动到第六个位置，30移动到第二个位置，再将枢轴值移动到30所在的单元，即第五个位置，所以选项A中序列移动的次数为4。同样，可以分析出选项B中序列的移动次数为8，选项C中序列的移动次数为4，选项D中序列的移动次数为2。
## 12. C
显然，若按从小到大排序，则最终有序的序列是{11,18,23,68,69,73,93}；若按从大到小排序，则最终有序的序列是{93,73,69,68,23,18,11}。对比可知说法I、II中没有处于最终位置的元素，所以说法I、II都不可能。说法III中73和93处于从大到小排序后的最终位置，而且73将序列分割成大于73和小于73的两部分，所以说法III是有可能的。说法IV中73和93处于从小到大排列后的最终位置，73也将序列分割成大于73和小于73的两部分。
## 13. B、C
快速排序过程构成一个递归树，递归深度即递归树的高度。枢轴值每次都将子表等分时，递归树的高为 $\log_{2}n$；枢轴值每次都是子表的最大值或最小值时，递归树退化为单链表，树高为 $n$。
## 14. D
快速排序的最好情况是每次划分将待排序列划分为等长的两部分。因此，第一趟将第1个元素与后面的7个元素进行比较，将原序列划分为长度为3和4的两个子表，比较7次；第二趟对两个子表进行划分，将长度为3的子表划分为长度为1的两个子表（不用继续划分），比较2次，将长度为4的子表划分为长度为1和2的两个子表，比较3次；第三趟将长度为2的子表划分为长度为1的子表，比较1次。至此，排序结束，共进行的比较次数是 $7 + 2 + 3 + 1 = 13$。
## 15. D
<!-- page: 360 -->
2027年数据结构考研复习指导
快速排序的递归次数与元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；若划分后分区不平衡，则递归次数多。递归次数与分区处理顺序无关。
## 16. A
对于绝大部分内部排序而言，只适用于顺序存储结构。快速排序在排序的过程中，既要从后往前查找，也要从前往后查找，因此宜采用顺序存储。
## 17. C
对 $n$ 个元素进行第一趟快速排序后，会确定一个基准元素，根据这个基准元素在数组中的位置，有两种情况：① 基准元素在数组的首端或尾端，接下来对剩下的 $n - 1$ 个元素构成的子序列进行第二趟快速排序，再确定一个基准元素。这样，在两趟排序后就至少能确定两个元素的最终位置，其中至少有一个元素是在数组的首端或尾端。② 基准元素不在数组的首端或尾端，第二趟快速排序对基准元素划分开的两个子序列分别进行一次划分，两个子序列各确定一个基准元素。这样，两趟排序后就至少能确定三个元素的最终位置。基于上述结论，观察题中的四个选项，选项 A 的 2, 3, 6, 7, 9 符合第一种或第二种情况；选项 B 中 2, 9 符合第一种情况；选项 D 中 5, 9 符合第一种情况；最后看选项 C，只有 9 处于最终位置，因此不可能是快速排序第二趟的结果。
## 18. D
基于上题中分析得出的结论，观察题中的四个选项，选项 A 的 28, 72 符合第一种情况；选项 B 的 2, 72 符合第一种情况；选项 C 的 2, 28, 32 符合第一种或第二种情况；最后看选项 D，只有 12 和 32 处于最终位置，既不符合第一种情况，又不符合第二种情况。
## 19. D
第一趟划分后得到的序列中只有一个枢轴，因此可将当前序列和最终排好序的序列进行比较，如下表所示。枢轴会出现在两个序列的相同位置，可以看出枢轴只可能是 77、81，选项只有 81。在当前序列中，77 左边有比它大的元素 80，因此 77 不是枢轴；而 81 左边都是比它小的元素，右边都是比它大的元素，因此 81 是枢轴。
| 当前序列 | 68 | 11 | 70 | 23 | 80 | 77 | 48 | 81 | 93 | 88 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 最终序列 | 11 | 23 | 48 | 68 | 70 | 77 | 80 | 81 | 88 | 93 |
## 20. A
依题意，对数组 $M$ 进行第一趟快速排序后，会将 $M$ 划分为三部分：小于枢轴值的块 $P$，枢轴元素，大于枢轴值的块 $Q$。$P$ 和 $Q$ 块内都是无序的，但是 $P$ 块内的数据 $\leqslant$ 枢轴值，$Q$ 块内的数据 $\geqslant$ 枢轴值，因此 $P$ 块内的数据 $\leqslant Q$ 块内的数据，即 $P$ 与 $Q$ 块间有序。
## 二、综合应用题
## 01. 【解答】
本题可采用基于快速排序的划分思想来设计算法，只需遍历一次即可，其时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。假设表为 L[1...n]，基本思想是：先从前往后找到一个偶数元素 L(i)，再从后往前找到一个奇数元素 L(j)，将二者交换；重复上述过程直到 i 大于 j。
算法的实现如下：
void move(ElemType A[], int len) {
//对表 A 按奇偶进行一趟划分
int i = 0, j = len - 1; // i 表示左端偶数元素的下标；j 表示右端奇数元素的下标
while (i &lt; j) {
while (i &lt; j &amp;&amp; A[i] % 2 != 0) i++; // 从前往后找到一个偶数元素
while (i &lt; j &amp;&amp; A[j] % 2 != 1) j--; // 从后往前找到一个奇数元素
if (i &lt; j) {
<!-- page: 361 -->
第8章 椿序
349
```txt
Swap(A[i], A[j]); //交换这两个元素
i++; j--;
}
## 02. 【解答】
显然，本题最直接的做法是用排序算法对数组先进行从小到大的排序，然后直接提取 L(k) 便得到了第 k 小的元素，但其平均时间复杂度将达到 $O(n \log_2 n)$ 以上。此外，还可采用小顶堆的方法，每次堆顶元素都是最小值元素，时间复杂度为 $O(n + k \log_2 n)$。下面介绍一个更精彩的算法，它基于快速排序的划分操作。
这个算法的主要思想如下：从数组 L[1...n] 中选择枢轴 pivot（随机或直接取第一个）进行和快速排序一样的划分操作后，表 L[1...n] 被划分为 L[1...m-1] 和 L[m+1...n]，其中 L(m) = pivot。
讨论 $m$ 与 $k$ 的大小关系：
1）当 $m = k$ 时，显然 pivot 就是所要寻找的元素，直接返回 pivot 即可。
2）当 $m < k$ 时，所要寻找的元素一定落在 $L[m+1...n]$ 中，因此可对 $L[m+1...n]$ 递归地查找第 $k-m$ 小的元素。
3）当 $m > k$ 时，所要寻找的元素一定落在 $L[1 \dots m-1]$ 中，因此可对 $L[1 \dots m-1]$ 递归地查找第 $k$ 小的元素。
该算法的时间复杂度在平均情况下可以达到 $O(n)$，而所占空间的复杂度则取决于划分的方法。算法的实现如下：
int kth_elem(int a[], int low, int high, int k) {
int pivot = a[low];
int low_temp = low; //由于下面会修改 low 与 high，在递归时又要用到它们
int high_temp = high;
while (low &lt; high) {
while (low &lt; high &amp;&amp; a[high]) &gt; = pivot)
--high;
a[low] = a[high];
while (low &lt; high &amp;&amp; a[low] &lt; = pivot)
++low;
a[high] = a[low];
}
a[low] = pivot;
//上面为快速排序中的划分算法
//以下是本算法思想中所述的内容
if (low == k) //由于与 k 相同，直接返回 pivot 元素
return a[low];
else if (low &gt; k) //在前一部分表中递归寻找
return kth_elem(a, low_temp, low-1, k);
else //在后一部分表中递归寻找
return kth_elem(a, low+1, high_temp, k);
}
## 03. 【解答】
算法思想：顺序扫描线性表，将红色条块交换到线性表的最前面，蓝色条块交换到线性表的最后面。为此，设立三个指针，其中， $j$ 为工作指针，表示当前扫描的元素， $i$ 以前的元素全部为红色， $k$ 以后的元素全部为蓝色。根据 $j$ 所指示元素的颜色，决定将其交换到序列的前部或尾部。初始时 $i = 0$，$k = n - 1$，算法的实现如下：
typedef enum{RED, WHITE, BLUE} color; //设置枚举数组
<!-- page: 362 -->
2027年数据结构考研复习指导
```c
void Flag_Arrange(color a[], int n) {
int i = 0, j = 0, k = n - 1;
while (j &lt;= k)
switch (a[j]) { //判断条块的颜色
case RED: Swap(a[i], a[j]); i++; j++; break;
//红色，则和 i 交换
case WHITE: j++; break;
case BLUE: Swap(a[j], a[k]); k--;
//蓝色，则和 k 交换
//这里没有 j++语句，以防止交换后 a[j] 仍为蓝色
}
}
例如，将元素值正数、负数和零排序为前面都是负数，接着是0，最后是正数，也用同样的方法。思考：为什么case RED语句不用考虑交换后a[j]仍为红色，而case BLUE语句中却需要考虑交换后a[j]仍为蓝色？
## 04. 【解答】
### 1）算法的基本设计思想
由题意可知，将最小的 $\lfloor n / 2 \rfloor$ 个元素放在 $A_{1}$ 中，其余的元素放在 $A_{2}$ 中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将 $n$ 个整数划分为两个子集。根据划分后枢轴所处的位置 $i$ 分别处理：
① 若 $i = \lfloor n / 2 \rfloor$，则分组完成，算法结束。
② 若 $i < \lfloor n / 2 \rfloor$，则枢轴及之前的所有元素均属于 $A_{1}$，继续对 $i$ 之后的元素进行划分。
③ 若 $i > \lfloor n / 2 \rfloor$，则枢轴及之后的所有元素均属于 $A_{2}$，继续对 $i$ 之前的元素进行划分。
基于该设计思想实现的算法，无须对全部元素进行全排序，其平均时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。
### 2）算法实现
int setPartition(int a[], int n) {
int pivotkey, low = 0, low0 = 0, high = n - 1, high0 = n - 1, flag = 1, k = n/2, i;
int s1 = 0, s2 = 0;
while (flag) {
pivotkey = a[low]; //选择枢轴
while (low &lt; high) { //基于枢轴对数据进行划分
while (low &lt; high &amp;&amp; a[high] &gt;= pivotkey) --high;
if (low != high) a[low] = a[high];
while (low &lt; high &amp;&amp; a[low] &lt;= pivotkey) ++low;
if (low != high) a[high] = a[low];
} // end of while (low &lt; high)
a[low] = pivotkey;
if (low == k - 1) //若枢轴是第 n/2 小的元素，划分成功
flag = 0;
else { //是否继续划分
if (low &lt; k - 1) {
low0 = ++low;
high = high0;
}
else {
high0 = --high;
low = low0;
}
}
}
for (i = 0; i &lt; k; i++) s1 += a[i];
<!-- page: 363 -->
第8章 排序
351
3）本算法的平均时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。
## 8.4 选择排序
选择排序的基本思想是：每一趟（如第 $i$ 趟）在后面 $n - i + 1$（$i = 1,2,\dots ,n - 1$）个待排序元素中选取关键字最小的元素，作为有序子序列的第 $i$ 个元素。直到第 $n - 1$ 趟排序完成，待排序元素只剩下 1 个，无须再选。选择排序中的堆排序是历年统考考查的重点。
## 8.4.1 简单选择排序
根据上述选择排序的思想，可直观得出简单选择排序的算法思想：假设排序表为 L[1...n]，第 $i$ 趟排序从 L[i...n] 中选出关键字最小的元素，并将其与 L(i) 交换。每一趟排序均可确定一个元素的最终位置，经过 $n - 1$ 趟排序后，整个表即有序。
简单选择排序的过程较为直观，具体示例可参考配套视频。其代码实现如下：
简单选择排序算法的性能分析如下。
空间效率：仅使用常数个辅助单元，空间复杂度为 $O(1)$。
**考点思路** 简单选择排序的性能分析（2025）
时间效率：排序过程中，总移动次数很少，最多不超过 $3(n - 1)$ 次，最好情况下为 0 次，即序列初始有序；但总比较次数与序列初态无关，始终为 $n(n - 1)/2$ 次，因此时间复杂度恒为 $O(n^{2})$。
稳定性：在交换过程中，若被选中的最小元素与当前位置元素之间存在相同关键字的记录，则会改变其相对顺序。例如，表 $L = \{2, 2, 1\}$，经过一趟排序后 $L = \{1, 2, 2\}$，也是最终排序结果，显然，2 与 2 的相对次序已发生改变。因此，简单选择排序是不稳定的排序算法。
适用性：简单选择排序适用于顺序存储和链式存储的线性表，尤其适合关键字较少的情况。
## 8.4.2 堆排序
堆的定义如下，$n$ 个关键字序列 L[1...n] 称为堆，当且仅当该序列满足以下条件之一：
① $\mathrm{L}(\mathrm{i})\geqslant \mathrm{L}(2\mathrm{i})$ 且 $\mathrm{L(i)}\geqslant \mathrm{L}(2\mathrm{i} + 1)$ 或
② $\mathrm{L(i)}\leqslant \mathrm{L}(2\mathrm{i})$ 且 $\mathrm{L(i)}\leqslant \mathrm{L}(2\mathrm{i} + 1)$ （$1\leqslant i\leqslant \lfloor n / 2\rfloor$）
**考点思路** 堆的性质与特点（2020）
可将堆视为一棵完全二叉树。满足条件①的堆称为大根堆（大顶堆），其最大元素位于根结点，且任意非根结点的值均不大于其双亲结点。满足条件②的堆称为小根堆（小顶堆），其最小元素位于根结点，性质与大根堆恰好相反。图 8.5 所示为一个大根堆。</n;i++)>
<!-- page: 364 -->
2027年数据结构考研复习指导
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.5 一个大根堆示意图
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
最新统考大纲新增了“城的应用”考点，堆的主要应用包括堆排序、Top-K问题和优先队列（见本节综合题7），Top-K问题和优先队列均利用了堆的结构特性，本节主要介绍堆排序。 堆排序的基本思路是：首先将待排序序列L[1...n]构建成初始堆（以大顶堆为例），此时堆顶即为最大值。随后，交换堆顶元素与堆底元素，使最大值归位；接着将剩余 $n - 1$ 个元素重新调整为堆，再取出新的堆顶。重复此过程，直至堆中仅剩一个元素。因此，堆排序需解决两个问题：①如何将无序序列构造成初始堆？②输出堆顶后，如何高效调整剩余元素为新堆？ 考点论证 初始建堆的操作（2018、2021） 堆排序的关键在于初始堆的构建。建堆的基本策略是：按自底向上的顺序（从最后一个分支结点到根结点），依次对每个分支结点执行自上而下的筛选操作；若其不满足堆的性质，则调整其对应的子树。对于含 $n$ 个结点的完全二叉树，最后一个分支结点的编号为 $\lfloor n / 2 \rfloor$ 。因此，建堆过程从 $i = \lfloor n / 2 \rfloor$ 开始，依次向前处理至 $i = 1$ 。具体而言：对每个结点 $i$ ，若其关键字小于左右子结点中的较大者（大根堆情形），则将其与该较大的子结点交换；交换后可能破坏下层子树的堆性质，因此需要继续沿该路径向下调整，直至当前子树重新满足堆的定义。通过依次对各分支结点执行上述的向下调整操作，最终可将整个无序序列构建成一个完整的堆。 如图8.6所示，初始时调整 $L(4)$ 子树， $09 < 32$ ，交换后满足堆定义；接着调整 $L(3)$ 子树， $78<$ 左右孩子中的较大者87，交换后满足堆定义；再调整 $L(2)$ 子树， $17<$ 左右孩子中的较大者45，交换后满足堆定义；继续调整根结点 $L(1)$ ， $53<$ 左右孩子中的较大者87，交换后破坏了 $L(3)$ 子树的堆，于是对 $L(3)$ 重新调整， $53<$ 左右孩子中的较大者78，交换后，该完全二叉树满足堆定义。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)初始i=4
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)i=3
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c)i=2
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d)i=1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(e)结果
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.6 自下往上逐步调整为大根堆 <!-- page: 365 --> 第8章 椿序 353