Appearance
冒泡排序
核心思想
冒泡排序的核心特点：
- 相邻比较：每次比较相邻的两个元素，如果逆序则交换
- 逐趟"冒泡"：每一趟遍历都会将当前未排序部分的最大元素"冒泡"到末尾
- 提前终止：若某一趟没有发生任何交换，说明序列已有序，可直接结束
以升序排序为例，每一趟的效果：
第 1 趟：将最大元素"冒泡"到 a[n-1]
第 2 趟：将次大元素"冒泡"到 a[n-2]
...
第 n-1 趟：整个序列有序交互可视化
通过下方的交互动画，你可以逐步观察冒泡排序的执行过程：
操作详解
算法思路
从前往后依次比较相邻元素，若前一个大于后一个则交换。一趟下来，最大的元素就被交换到了序列末尾（像气泡一样"浮"到顶端）。重复这一过程，每趟确定一个元素的最终位置，直到整个序列有序。
⚠️ 易错：冒泡排序每趟确定一个元素的最终位置（最大值冒到末尾），这和快排类似。区别在于：冒泡确定的一定是当前未排序部分的最大（或最小）值，而快排确定的是 pivot，不一定是极值。
关键步骤：
- 外层循环控制趟数，最多需要 n-1 趟
- 内层循环在未排序区间内进行相邻元素的比较与交换
- 每趟结束后，未排序区间缩小一个元素
排序过程详解
以序列 {5, 3, 4, 1, 2} 为例（升序）：
初始序列: 5 3 4 1 2
第 1 趟: (5,3)交换→3 (5,4)交换→4 (5,1)交换→1 (5,2)交换→2 → 3 4 1 2 [5]
第 2 趟: (3,4)不换 (4,1)交换→1 (4,2)交换→2 → 3 1 2 [4 5]
第 3 趟: (3,1)交换→1 (3,2)交换→2 → 1 2 [3 4 5]
第 4 趟: (1,2)不换 → 无交换，提前终止 → [1 2 3 4 5][] 中的元素为已排好序的部分。
基本实现（C/C++）：
c
void BubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) { // 最多 n-1 趟
for (int j = 0; j < n - 1 - i; j++) { // 每趟比较范围递减
if (a[j] > a[j + 1]) { // 相邻元素比较
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp; // 交换
}
}
}
}提前终止优化
如果某一趟遍历中没有发生任何交换，说明序列已经有序，后续的趟数可以全部跳过。这是冒泡排序最重要的优化手段，也是考研常考的改进点。
c
void BubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false; // 交换标志
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
swapped = true; // 发生了交换
}
}
if (!swapped) break; // 本趟无交换，提前终止
}
}加入 swapped 标志后，对于已经有序的序列，只需一趟遍历即可结束，此时时间复杂度为 O(n)。
⚠️ 易错：冒泡排序的最好情况是 O(n)（已有序，第一趟无交换直接终止），但前提是代码中有"本趟无交换则提前结束"的优化。如果没有这个优化，即使序列已有序也会跑满 n-1 趟。408 考的是有优化版本。
复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n) | 序列已有序，一趟遍历无交换即终止 |
| 最坏情况 | O(n²) | 序列逆序，每趟都要比较和交换 |
| 平均情况 | O(n²) | 平均比较和交换次数均为 O(n²) |
| 指标 | 值 | 说明 |
|---|---|---|
| 空间复杂度 | O(1) | 只需常数级辅助变量（tmp、swapped） |
| 稳定性 | 稳定 | 相等元素不交换，相对顺序不变 |
| 适用场景 | 基本有序的小规模数据 | 提前终止优化对近乎有序的序列效果显著 |
考研高频考点
- ⭐ 冒泡排序的每趟结果（选择题/填空题高频，给定初始序列要求写出第 k 趟的结果）
- ⭐ 提前终止优化的条件与最好时间复杂度 O(n)（选择题常考）
- ⭐ 冒泡排序的稳定性证明（简答题/判断题，关键在于"相等元素不交换"）
- ⭐ 比较次数与交换次数的计算（最好 n-1 次比较 0 次交换，最坏 n(n-1)/2 次比较和交换）
- 冒泡排序 vs 简单选择排序的对比（交换次数、稳定性差异）
相关知识
- 冒泡排序与直接插入排序都是 O(n²) 算法，但插入排序的移动次数约为冒泡交换次数的 1/3（赋值 vs 三次赋值的交换），实际速度快 3-5 倍
- 冒泡排序是交换排序的代表，快速排序是其改进版——通过分治策略将平均复杂度降到 O(n log n)
- 冒泡排序是稳定排序（相等元素不交换），与同为交换排序但不稳定的快排形成对比