8.3 交换排序
## 8.3 交换排序
所谓交换，是指根据序列中两个元素关键字的比较结果，互换它们在序列中的位置。基于交换思想的排序算法有很多，本书主要介绍冒泡排序与快速排序。其中，冒泡排序实现简单，一般较少直接考查；而快速排序则因效率高、应用广，通常是考查的重点。
## 8.3.1 冒泡排序
冒泡排序的基本思想是：从后往前（或从前往后）依次比较相邻元素的关键字，若为逆序（A[i-1]>A[i]），则交换它们的位置。每一趟排序都会将当前未排序部分中的最小（或最大）元素放到其最终位置——最小元素如气泡上浮至水面（或最大元素如石头下沉至水底）。具体而言，第一趟冒泡将最小元素移至序列首部（或最大元素移至尾部）；第二趟对剩余子序列重复此过程，已确定位置的元素不再参与比较。如此最多进行 $n - 1$ 趟冒泡，即可完成整个排序。
图8.3所示为冒泡排序的过程，第一趟冒泡时： $27 < \overline{49}$ ，不交换； $13 < 27$ ，不交换； $76 > 13$ ，交换； $97 > 13$ ，交换； $65 > 13$ ，交换； $38 > 13$ ，交换； $49 > 13$ ，交换。通过第一趟冒泡后，元素13被移至第一个位置，及其最终位置；第二趟对后续子序列采用同样方法进行排序，如此重复，到第五趟结束后，未发生任何交换，说明序列已有序，算法提前终止。
冒泡排序算法的代码如下：
① 本章有多处要两两交换元素，为使代码更简洁，使用函数 swap(int &a, int &b)，其定义如下：int temp = a; a = b; b = temp;
<!-- page: 353 -->
第8章 排序
341
| 49 | 13 | 13 | 13 | 13 | 13 | 13 |
| --- | --- | --- | --- | --- | --- | --- |
| 38 | 49 | 27 | 27 | 27 | 27 | 27 |
| 65 | 38 | 49 | 56 | 56 | 56 | 56 |
| 97 | 65 | 38 | 49 | 49 | 49 | 49 |
| 76 | 97 | 65 | 49 | 49 | 49 | 49 |
| 13 | 76 | 97 | 65 | 65 | 65 | 65 |
| 27 | 27 | 76 | 97 | 76 | 76 | 76 |
| 49 | 49 | 49 | 76 | 97 | 97 | 97 |
| 初始状态 | 第 一 越 前 | 第 二 越 前 | 第 三 越 前 | 第 四 越 前 | 第 五 越 前 | 最 终 状态 |
图8.3 冒泡排序示例
冒泡排序的性能分析如下。
空间效率：仅使用常数个辅助单元，空间复杂度为 $O(1)$。
时间效率：最好情况下（初始序列有序），仅需第一趟冒泡，共 $n - 1$ 次比较，0次移动，时间复杂度为 $O(n)$；最坏情况下（序列初始逆序），需 $n - 1$ 趟排序，第 $i$ 趟进行 $n - i$ 次比较，且每次比较后都需3次移动来完成交换元素位置。这种情况下，
$$
\triangleq \text{比较次数} = \sum_{i = 1}^{n - 1} (n - i) = \frac{n(n - 1)}{2}, \text{移动次数} = \sum_{i = 1}^{n - 1} 3(n - i) = \frac{3n(n - 1)}{2}
$$
因此，最坏情况下的时间复杂度为 $O(n^{2})$。平均时间复杂度也为 $O(n^{2})$。
稳定性：比较相邻元素时，相等元素不会被交换，因此冒泡排序是稳定的排序算法。
适用性：冒泡排序适用于顺序存储和链式存储的线性表。
**注意**
冒泡排序每趟产生的有序子序列具有全局有序性——已排序部分的所有元素均小于（或大于）未排序部分的所有元素。与直接插入排序的局部有序不同，冒泡排序每趟能将一个元素精确放置到其最终位置。
## 8.3.2 快速排序
**特点指标** ▶ 快速排序的思想（2024）
快速排序的基本思想是：在待排序表 $L[1...n]$ 中任取一个元素作为枢轴（pivot，也称基准，通常取首元素），通过一趟排序将原表划分为两个独立的子表 $L[1...k-1]$ 和 $L[k+1...n]$，使得左子表中所有元素的关键字均小于枢轴，右子表中所有元素的关键字均大于或等于枢轴。此时，枢轴元素被放在了其最终位置 $L(k)$ 上，这个过程称为一次划分。随后，分别对两个子表递归地执行相同的划分操作，直至每个子表仅包含一个元素或为空，此时整个序列已完全有序。
一趟快速排序的划分过程本质上是一个双向交替扫描与元素移动的过程，下面通过实例来介绍，附设两个指针 $i$ 和 $j$，初值分别为 low 和 high，取第一个元素 49 为枢轴 pivot。
$j$ 从右向左扫描，找到第一个小于枢轴的元素 27，将其复制到 $i$ 所指位置。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
$i$ 从左向右扫描，找到第一个大于枢轴的元素 65，将其复制到 $j$ 所指位置。 <!-- page: 354 --> 2027年数据结构考研复习指导
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
j 继续向左扫描，找到小于枢轴的元素 13，将其复制到 i 所指位置。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
i 继续向右扫描，找到大于枢轴的元素 97，将其复制到 j 所指位置。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
如此交替进行，直到 i 与 j 相遇（i==j）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
考虑点击>> 快速排序的中间过程的分析（2014、2019、2023）
此时，i 左侧的所有元素均小于 49，右侧的所有元素均大于或等于 49。将枢轴 49 放入 i 所指位置，即完成第一趟划分。原序列被分割为两个子序列，分别位于枢轴的左右两侧。
第一趟后：{27 38 13} 49 {76 97 65 49}
接下来，对这两个子序列分别递归地应用同样的快速排序过程。若某子序列仅包含一个元素，则该子序列自然有序，无须进一步处理。
第二趟后：{13} 27 {38} 49 {49 65} 76 {97}
第三趟后：13 27 38 49 49 {65} 76 97
第四趟后：13 27 38 49 49 65 76 97
整个递归调用的层次结构可以用一棵二叉树来表示，如图 8.4 所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)第一层快排处理后:
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)第二层快排处理后
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c)第三层快排处理后
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d)第四层快排处理后：最终结果 图 8.4 快速排序的递归执行过程 <!-- page: 355 --> 第8章 排序 343 假设划分操作已封装为函数 Partition()，其功能是对子表 A[low..high] 进行一趟划分，并返回枢轴元素的最终位置 k。在此基础上，快速排序的递归实现如下：**特点组合** ▶（算法题）快速排序中划分操作的应用（2016） 考研所考查的划分操作，通常以子表的第一个元素作为枢轴来对表进行划分，将比枢轴小的元素逐步移至左侧，比枢轴大的元素移至右侧，最终使枢轴归位。典型实现如下：void QuickSort(ElemType A[], int low, int high) { //递归跳出的条件 //Partition() 就是划分操作，将表 A[low...high] 划分为满足上述条件的两个子表 int pivotpos = Partition(A, low, high); //划分 QuickSort(A, low, pivotpos - 1); //依次对两个子表进行递归排序 QuickSort(A, pivotpos + 1, high); } }快速排序的性能高度依赖于划分的平衡性，其性能分析如下。 **特点组合** ▶ 快速排序中递归次数的影响因素分析（2010） 空间效率：由于采用递归实现，算法需借助系统栈保存每层递归的上下文信息，栈的容量等于递归调用的最大层数。最好情况下（每次划分均分）为 $O(\log_2 n)$；最坏情况下（划分极不平衡），需进行 $n - 1$ 次递归调用，栈的容量为 $O(n)$；平均情况下为 $O(\log_2 n)$。 时间效率：最坏情况发生在初始序列基本有序或基本逆序时，每趟划分仅减少一个元素，总比较次数约为 $n(n - 1)/2$，时间复杂度为 $O(n^2)$。最好情况是每次划分都将序列等分为两部分，此时时间复杂度为 $O(n \log_2 n)$。值得注意的是，快速排序的平均运行时间非常接近其最优情况，远优于最坏情况，因此它是所有内部排序算法中平均性能最优的排序方法。 有很多方法可以提高划分的平衡性：一种是三数取中法，从子序列的首、尾及中间三个位置各取一个元素，以其中位数作为枢轴；或者随机选取子序列中的某个元素作为枢轴。 稳定性：在划分过程中，若右侧区域有两个关键字相等，且均小于枢轴，则交换到左侧区域后，它们的相对位置会发生改变，因此快速排序是不稳定的排序算法。例如，表 $L = \{3, 2, 2\}$，经过一趟排序后 $L = \{2, 2, 3\}$，也是最终排序结果，显然，2 与 2 的相对次序已发生了变化。 **特点组合** ▶ 快速排序适合采用的存储方式（2011） 适用性：快速排序要求能够随机访问元素，因此仅适用于顺序存储的线性表。 **注意** 快速排序在每趟划分后并不产生全局有序的子序列。然而，每趟划分都能确保当前所选的枢轴元素被精确放置到其在整个序列中的最终位置上。这一特性是快速排序高效性的关键所在。 <!-- page: 356 --> 2027年数据结构考研复习指导 ## 8.3.3 本节试题精选 ### 一、单项选择题 01. 对 $n$ 个不同的元素利用冒泡法从小到大排序，在（ ）情况下元素交换的次数最多。 A. 从大到小排列好的 B. 从小到大排列好的 C. 元素无序 D. 元素基本有序 02. 若用冒泡排序算法对序列 $\{10, 14, 26, 29, 41, 52\}$ 从大到小排序，则需进行（ ）次比较。 A. 3 B. 10 C. 15 D. 25 03. 用某种排序算法对线性表 $\{25, 84, 21, 47, 15, 27, 68, 35, 20\}$ 进行排序时，元素序列的变化情况如下： 1）25, 84, 21, 47, 15, 27, 68, 35, 20 2）20, 15, 21, 25, 47, 27, 68, 35, 84 3）15, 20, 21, 25, 35, 27, 47, 68, 84 4）15, 20, 21, 25, 27, 35, 47, 68, 84 则所采用的排序算法是（）。 A. 选择排序 B. 插入排序 C. 2路归并排序 D. 快速排序 04. 一组记录的关键码为 $(46, 79, 56, 38, 40, 84)$，则利用快速排序算法，以第一个记录为基准，从小到大得到的一次划分结果为（）。 A. $(38, 40, 46, 56, 79, 84)$ B. $(40, 38, 46, 79, 56, 84)$ C. $(40, 38, 46, 56, 79, 84)$ D. $(40, 38, 46, 84, 56, 79)$ 05. 快速排序算法在（ ）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序 06. 就平均性能而言，目前最好的内部排序算法是（）。 A. 冒泡排序 B. 直接插入排序 C. 希尔排序 D. 快速排序 07. 数据序列 $F = \{2, 1, 4, 9, 8, 10, 6, 20\}$ 只能是下列排序算法中的（ ）两趟排序后的结果。 A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 08. 对元素序列 $\{8, 9, 10, 4, 5, 6, 20, 1, 2\}$ 采用冒泡排序（从后往前次序进行，要求升序），需要进行元素交换的趟数至少是（ ）（不考虑无元素交换的最后一趟）。 A. 3 B. 4 C. 5 D. 8 09. 双向冒泡排序是指对一个序列在正反两个方向交替进行扫描，第一趟把最大值放在序列的最右端，第二趟把最小值放在序列的最左端，之后在缩小的范围内进行同样的扫描，放在次右端、次左端，直至序列有序。对数组 $\{4, 7, 8, 3, 5, 6, 10, 9, 1, 2\}$ 进行双向冒泡排序，则排序趟数是（）。（第一趟从左往右开始，从左往右或从右往左都称为一趟。） A. 7 B. 6 C. 8 D. 9 10. 对下列关键字序列用快速排序进行排序时，每次选取的基准元素都为待处理序列的第一个元素，速度最快的情形是（），速度最慢的情形是（）。 A. $\{21, 25, 5, 17, 9, 23, 30\}$ B. $\{25, 23, 30, 17, 21, 5, 9\}$ C. $\{21, 9, 17, 30, 25, 23, 5\}$ D. $\{5, 9, 17, 21, 23, 25, 30\}$ 11. 对下列 4 个序列，以第一个关键字为基准用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是（）。 <!-- page: 357 --> 第8章 排序 345 A. 92, 96, 88, 42, 30, 35, 110, 100 B. 92, 96, 100, 110, 42, 35, 30, 88 C. 100, 96, 92, 35, 30, 110, 88, 42 D. 42, 30, 35, 92, 100, 96, 88, 110 12. 下列序列中，（ ）可能是执行第一趟快速排序后所得到的序列（按从大到小排序和从小到大排序来分别讨论）。 I. {68, 11, 18, 69, 23, 93, 73} II. {68, 11, 69, 23, 18, 93, 73} III. {93, 73, 68, 11, 69, 23, 18} IV. {68, 11, 69, 23, 18, 73, 93} A. I、IV B. II、III C. III、IV D. 只有 IV 13. 对 $n$ 个关键字进行快速排序，最大递归深度为（ ），最小递归深度约为（ ）。 A. 1 B. $n$ C. $\log_2 n$ D. $n \log_2 n$ 14. 对8个元素的序列进行快速排序，在最好情况下的关键字比较次数是（ ）。 A. 7 B. 8 C. 12 D. 13 15. 【2010统考真题】采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。 A. 递归次数与初始数据的排列次序无关 B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关 16. 【2011统考真题】为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。 A. 顺序存储 B. 数列存储 C. 链式存储 D. 索引存储 17. 【2014统考真题】下列选项中，不可能是快速排序第二趟排序结果的是（ ）。 A. 2, 3, 5, 4, 6, 7, 9 B. 2, 7, 5, 6, 4, 3, 9 C. 3, 2, 5, 4, 7, 6, 9 D. 4, 2, 3, 5, 7, 6, 9 18. 【2019统考真题】排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟。下列序列中，不可能是快速排序第二趟结果的是（ ）。 A. 5, 2, 16, 12, 28, 60, 32, 72 B. 2, 16, 5, 28, 12, 60, 32, 72 C. 2, 12, 16, 5, 28, 32, 72, 60 D. 5, 2, 12, 28, 16, 32, 72, 60 19. 【2023统考真题】使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的框轴是（ ）。 A. 11 B. 70 C. 80 D. 81 20. 【2024统考真题】使用快速排序算法对含 $n$（$n \geqslant 3$）个元素的数组 $M$ 进行排序，若第一趟排序将 $M$ 中除框轴外的 $n-1$ 个元素划分为均不为空的 $P$ 和 $Q$ 两块，则下列叙述中，正确的是（ ）。 A. $P$ 与 $Q$ 块间有序 B. $P$ 与 $Q$ 均块内有序 C. $P$ 和 $Q$ 的元素个数大致相等 D. $P$ 中和 $Q$ 中均不存在相等的元素 ## 二、综合应用题 01. 已知线性表按顺序存储，且每个元素都是不相同的整数型元素，设计把所有奇数移动到所有偶数前边的算法（要求时间最短，辅助空间最小）。 02. 试编写一个算法，使之能够在数组L[1...n]中找出第 $k$ 小的元素（从小到大排序后处于第 $k$ 个位置的元素）。 03. 荷兰国旗问题：设有一个仅由红、白、蓝三种颜色的条块组成的条块序列，存储在 <!-- page: 358 --> 2027年数据结构考研复习指导 一个顺序表中，请编写一个时间复杂度为 $O(n)$ 的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。请完成算法实现： 04. 【2016 统考真题】已知由 $n (n \geqslant 2)$ 个正整数构成的集合 $A = \{a_{k} | 0 \leqslant k < n\}$，将其划分为两个不相交的子集 $A_{1}$ 和 $A_{2}$，元素个数分别是 $n_{1}$ 和 $n_{2}$，$A_{1}$ 和 $A_{2}$ 中的元素之和分别为 $S_{1}$ 和 $S_{2}$。设计一个尽可能高效的划分算法，满足 $|n_{1} - n_{2}|$ 最小且 $|S_{1} - S_{2}|$ 最大。要求： 1）给出算法的基本设计思想。 2）根据设计思想，采用 C 或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释。 3）说明所设计算法的平均时间复杂度和空间复杂度。 ## 8.3.4 答案与解析 ### 一、单项选择题 #### 01. A 冒泡排序最少进行 1 趟冒泡，最多进行 $n - 1$ 趟冒泡。初始序列为逆序时，需进行 $n - 1$ 趟冒泡，并且元素交换的次数最多。初始序列为正序时，进行 1 趟冒泡（无交换）就可结束算法。 #### 02. C 冒泡排序始终在调整“逆序”，因此交换次数为排列中逆序的个数。对逆序序列进行冒泡排序，每个元素向后调整时都需要进行比较，因此其需要比较 $5 + 4 + 3 + 2 + 1 = 15$ 次。int Partition(ElemType A[], int low, int high) { //一趟划分 ElemType pivot = A[low]; //将当前表中第一个元素设为枢轴，对表进行划分 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; //枢轴元素存放到最终位置 return low; //返回存放枢轴的最终位置 }