6 冒泡排序与选择排序
正在加载视频播放器…
GESP C++ 四级：冒泡排序与选择排序精讲
核心目标：理解两种排序算法的原理与执行流程，掌握标准代码实现，理解时间复杂度、交换次数和稳定性，能读懂排序过程并解决综合应用问题。
冒泡排序靠“相邻比较、逐步交换”，每轮把最大元素送到末尾；选择排序靠“标记最小值、最后交换”，每轮把最小元素放到前面。两者时间复杂度都是 O(n²)，冒泡稳定、选择不稳定，选择排序的交换次数更少。
一、考纲定位
根据CCF官方考纲，四级知识内容明确包含 “排序概念和稳定性” 与 “经典排序（冒泡排序、插入排序、选择排序等）” 。
具体考核要求包括：
- 理解排序算法的基本概念与评价指标
- 掌握冒泡排序、插入排序、选择排序的实现及稳定性分析
- 能进行简单算法复杂度的估算（含多项式、指数复杂度）
- 能运用排序算法解决综合应用问题
在四级考试中，排序相关考点通常出现在选择题和程序阅读题中，同时以排序为工具的综合编程题也是高频题型。
二、冒泡排序
2.1 核心思想
冒泡排序的基本流程是：每一轮从头开始两两比较，将较大的项放在较小项的右边，这样每轮下来保证该轮最大的数在最右边。
形象理解：每一轮就像“气泡”从水底往上冒，最大的元素一轮一轮被“冒”到数组末尾。
2.2 执行流程图解
以数组 [5, 3, 8, 1] 为例，升序排列：
第一轮（确定最大值到末尾）：
5 3 8 1 → 比较5和3，交换 → 3 5 8 1
3 5 8 1 → 比较5和8，不交换 → 3 5 8 1
3 5 8 1 → 比较8和1，交换 → 3 5 1 8
第一轮结束，8已到末尾
第二轮（确定次大值）：
3 5 1 8 → 比较3和5，不交换 → 3 5 1 8
3 5 1 8 → 比较5和1，交换 → 3 1 5 8
5已到倒数第二位
第三轮（确定第三大值）：
3 1 5 8 → 比较3和1，交换 → 1 3 5 8
排序完成。
2.3 标准代码实现
for (int i = 0; i < n - 1; i++) { // 外层：共 n-1 轮
for (int j = 0; j < n - 1 - i; j++) { // 内层：每轮比较相邻元素
if (arr[j] > arr[j + 1]) { // 前面的更大，交换
int t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
代码要点：
- 外层循环
i控制轮数，共n-1轮。 - 内层循环
j控制每轮比较次数，第i轮比较n-1-i次，因为末尾i个元素已经排好。 arr[j] > arr[j + 1]是升序排列，若改为<则为降序。
2.4 优化：提前终止
如果某一轮没有发生任何交换，说明数组已经有序，可以提前结束。
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 本轮无交换，数组已有序
}
优化效果：最好情况下（数组已正序），时间复杂度从 O(n²) 降为 O(n)。
三、选择排序
3.1 核心思想
选择排序改进了冒泡排序，将必要的交换次数从 O(n²) 减少到 O(n)，但是比较次数仍保持为 O(n²)。每一轮在未排序部分中找到最小元素，然后与未排序部分的第一个元素交换。
形象理解：每轮像“选班长”一样，从剩下的人里选出最小的，放到队伍最前面。
3.2 执行流程图解
以数组 [5, 3, 8, 1] 为例，升序排列：
第一轮（在全部元素中找最小值）：
5 3 8 1 → 最小值为1（下标3），与下标0交换 → 1 3 8 5
第二轮（在下标1~3中找最小值）：
1 3 8 5 → 最小值为3（下标1），已在正确位置 → 1 3 8 5
第三轮（在下标2~3中找最小值）：
1 3 8 5 → 最小值为5（下标3），与下标2交换 → 1 3 5 8
排序完成。
3.3 标准代码实现
for (int i = 0; i < n - 1; i++) { // 外层：共 n-1 轮
int minIdx = i; // 假设当前位置是最小值
for (int j = i + 1; j < n; j++) { // 在未排序部分找最小值
if (arr[j] < arr[minIdx]) {
minIdx = j; // 记录最小值下标
}
}
if (minIdx != i) { // 如果最小值不在当前位置，交换
swap(arr[i], arr[minIdx]);
}
}
代码要点：
- 外层循环
i表示当前要确定的位置。 - 内层循环
j从i+1开始，在未排序部分找最小值。 - 每轮最多只交换一次，交换次数为 O(n)。
四、两种排序对比
4.1 核心区别一览
| 对比项 | 冒泡排序 | 选择排序 |
|---|---|---|
| 核心操作 | 相邻比较，边比较边交换 | 先找最小值，最后交换 |
| 每轮交换次数 | 可能多次 | 最多一次 |
| 总交换次数 | O(n²) | O(n) |
| 比较次数 | O(n²) | |
| 最好时间复杂度 | O(n)（优化后） | |
| 最坏时间复杂度 | O(n²) | |
| 平均时间复杂度 | ||
| 空间复杂度 | O(1) | |
| 稳定性 | 稳定 | 不稳定 |
4.2 稳定性分析
冒泡排序是稳定的：当 a == b 时，由于只有大于才做交换，故 a 和 b 的位置没有机会交换，所以算法稳定。
选择排序是不稳定的：假设 a == b，且 a 在 b 前面，而某轮循环中最小值在 b 后面，而次最小值需要跟 a 交换，这时候 b 就在 a 前面了。
真题示例：
以下排序算法中，稳定的是（ ）。
A) 选择排序 B) 冒泡排序 C) 快速排序 D) 堆排序
答案：B
4.3 性能差异的本质
选择排序之所以比冒泡排序“快”，在于交换次数大幅减少。冒泡排序每比较一次就可能交换一次，而选择排序是一轮比较完后才交换一次。当数据量较大、交换操作代价较高时，选择排序的优势更明显。
五、复杂度估算
四级要求掌握简单算法复杂度的估算。
5.1 两种排序的复杂度
| 复杂度类型 | 冒泡排序 | 选择排序 |
|---|---|---|
| 比较次数 | O(n²) | O(n²) |
| 交换次数 | O(n) | |
| 最好时间复杂度 | O(n)（优化后） | O(n²) |
| 最坏/平均时间复杂度 | O(n²) | |
| 空间复杂度 | O(1) | |
5.2 复杂度估算方法
对于嵌套循环，时间复杂度通常为各层循环次数的乘积。
- 冒泡排序：外层
n-1次，内层平均n/2次，总计约(n-1) × n/2，即 O(n²)。 - 选择排序：外层
n-1次，内层平均n/2次，总计约 O(n²)。
5.3 真题示例
对包含 n 个元素的数组进行冒泡排序，平均时间复杂度一般为（ ）。
A) O(n) B) O(n log n) C) O(n²) D) O(n³)
答案：C
六、GESP 四级排序真题精讲
真题1：排序（2025年6月）
题目描述：体育课上 n 名同学排成一队，第 i 位同学身高为 hi，体重为 wi。按照“身高更高者优先，身高相同则体重更重者优先”的规则，判断队伍中有多少对同学站错了位置。
解题思路：使用双重循环检查每一对同学，统计逆序对数量。
#include <iostream>
using namespace std;
struct Stu { int h, w; };
Stu p[1005];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> p[i].h >> p[i].w;
int cnt = 0;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
// 如果第 j 位同学应该排在第 i 位前面，说明站错了
if (p[j].h > p[i].h || (p[j].h == p[i].h && p[j].w > p[i].w)) {
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}
核心考点：双重循环 + 排序规则判断，本质是统计逆序对数量。
真题2：有序网格（2026年9月）
题目描述：对一个二维网格，先对每一行从左到右升序排序，再对每一列从上到下升序排序，最后输出结果。
关键陷阱：必须先排列，再排第二列，顺序不能反。
// 第一步：对每一行冒泡排序
for (int i = 1; i <= n; i++) {
for (int last = m; last > 1; --last) {
for (int j = 1; j < last; ++j) {
if (a[i][j] > a[i][j + 1]) {
swap(a[i][j], a[i][j + 1]);
}
}
}
}
// 第二步：对每一列冒泡排序
for (int j = 1; j <= m; ++j) {
for (int last = n; last > 1; --last) {
for (int i = 1; i < last; ++i) {
if (a[i][j] > a[i + 1][j]) {
swap(a[i][j], a[i + 1][j]);
}
}
}
}
核心考点：二维数组 + 冒泡排序思想 + 行排序与列排序的顺序。
真题3：区间排序（2024年9月）
题目描述：对序列进行多次升序排序，每次选择一个区间 [l, r] 并对区间内所有数字进行升序排序，每次排序在上次结果的基础上进行。
解题思路：每次对指定区间执行冒泡排序即可。
for (int k = 0; k < q; k++) {
int l, r;
cin >> l >> r;
// 对区间 [l, r] 冒泡排序（注意下标从1开始）
for (int i = l; i < r; i++) {
for (int j = l; j <= r - (i - l + 1); j++) {
if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
}
}
七、易错点汇总
7.1 冒泡排序易错点
- 内层循环边界错误：第
i轮比较次数应为n-1-i，写错会导致重复比较或漏比较。 - 外层循环边界错误：应为
i < n - 1，不是i < n。 - 交换条件写反：升序用
>，降序用<，写反则排序方向错误。 - 忘记优化：数据已有序时仍执行全部轮次，效率降低。
7.2 选择排序易错点
- 内层循环起点错误：应从
i + 1开始，不是从 0 开始。 - 忘记记录下标：找最小值时需要记录下标而非值，否则无法交换。
- 每轮交换条件：
minIdx != i时才交换，避免不必要的交换。 - 最小值初始化错误：
minIdx = i，不是0。
7.3 通用易错点
- 数组下标从0还是从1开始：统一使用一种，不要混用。
- 稳定性判断：冒泡稳定，选择不稳定，这是高频选择题考点。
- 时间复杂度混淆：两种排序平均和最坏都是 O(n²)，但冒泡优化后最好为 O(n)。
- 交换次数混淆：选择排序交换次数为 O(n)，冒泡为 O(n²)。
八、速查表
| 需求 | 冒泡排序 | 选择排序 |
|---|---|---|
| 核心思想 | 相邻比较，逐步交换 | 找最小值，最后交换 |
| 代码结构 | 双层循环，内层相邻比较 | 双层循环，内层找最小值 |
| 每轮交换 | 可能多次 | 最多一次 |
| 总交换次数 | O(n²) | O(n) |
| 最好时间复杂度 | O(n)（优化后） | O(n²) |
| 平均/最坏 | O(n²) | |
| 稳定性 | 稳定 | 不稳定 |
| 适用场景 | 教学、小数据量 | 交换代价大的场景 |
| 升序条件 | arr[j] > arr[j+1] |
arr[j] < arr[minIdx] |
| 降序条件 | arr[j] < arr[j+1] |
arr[j] > arr[maxIdx] |
九、总结
冒泡排序与选择排序是GESP四级排序模块的两大核心算法。
- 冒泡排序：相邻比较，逐步交换，每轮把最大元素送到末尾。
- 选择排序：找最小值，最后交换，每轮把最小元素放到前面。
- 两种排序平均和最坏时间复杂度都是 O(n²)。
- 冒泡排序最好时间复杂度为 O(n)（优化后），选择排序始终为 O(n²)。
- 选择排序的交换次数为 O(n)，冒泡为 O(n²)，这是选择排序的核心优势。
- 冒泡排序稳定，选择排序不稳定，这是高频选择题考点。
- 冒泡排序内层边界是
n-1-i，选择排序内层起点是i+1。 - 选择排序找最小值时记录的是下标，不是值。
- 二维数组排序时，先排列再排行的顺序不能反。
- 多练“排序过程模拟”“稳定性判断”“排序综合应用”三类题。
复习建议：先把两种排序的标准代码写熟，确保闭卷能默写；再练习“阅读程序写结果”类题目，手动模拟排序过程；最后攻克“有序网格”“排序”等综合编程题。考试中先判断题目要求的是排序过程、复杂度、稳定性还是综合应用，再套用对应知识作答。