冒泡排序 (Bubble Sort)
一句话总结
冒泡排序是对选择排序的优化，通过交换相邻逆序对完成排序，是一种稳定排序算法，支持在数组有序时提前终止。
核心要点
1. 从选择排序的缺陷出发
选择排序存在三个主要问题：
- 不稳定排序：交换操作会改变相同元素的相对位置
- 无视数组有序度：即使输入已有序，时间复杂度仍是 O(n²)
- 时间复杂度无法优化：固定执行约 n²/2 次操作
冒泡排序通过逐步优化选择排序来解决这些问题。
2. 三个优化阶段
阶段一：获得稳定性
- 将选择排序的"交换"改为"数据搬移"
- 把
nums[sortedIndex..minIndex]整体后移一位，让最小值插入正确位置 - 代价：增加了一个 for 循环，实际执行次数增加
阶段二：合并操作（真正的冒泡排序）
- 倒序遍历，发现逆序对就交换相邻元素
- 最小值会像气泡一样逐步"冒"到正确位置
- 消除了额外的数据搬移循环，执行次数回到约 n²/2 次
- 关键：只交换相邻元素，不改变相同元素的相对位置 → 稳定排序
阶段三：提前终止
- 添加
swapped布尔变量记录是否发生交换 - 如果一轮遍历没有交换，说明数组已有序，提前退出
- 对近乎有序的数组效率显著提升
基本原理
冒泡排序的核心思想是通过交换相邻逆序对，让最小值逐步移动到正确位置。
初始: [5, 3, 1, 4, 2]
第1轮 (sortedIndex=0):
i=4: [5,3,1,4,2] → [5,3,1,2,4] (交换4,2)
i=3: [5,3,1,2,4] → [5,3,1,2,4] (1<2,不交换)
i=2: [5,3,1,2,4] → [5,3,1,2,4] (3>1,不交换)
i=1: [5,3,1,2,4] → [3,5,1,2,4] (5>3,交换)
结果: [3,5,1,2,4] → 最小值1已冒泡到位置0? 不对...
实际上代码是倒序遍历，让最小值逐步往前移动：
// 冒泡排序完整版（含提前终止）
void sort(int[] nums) {
int n = nums.length;
int sortedIndex = 0;
while (sortedIndex < n) {
boolean swapped = false;
// 倒序遍历，交换逆序对
for (int i = n - 1; i > sortedIndex; i--) {
if (nums[i] < nums[i - 1]) {
int tmp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = tmp;
swapped = true;
}
}
if (!swapped) break; // 提前终止
sortedIndex++;
}
}
| 特性 | 说明 |
|---|---|
| 核心操作 | 交换相邻逆序对 |
| 稳定性 | 稳定（只交换相邻元素） |
| 提前终止 | 支持（数组有序时 O(n)） |
| 排序方向 | 每次将最小值"冒"到 sortedIndex 位置 |
时间复杂度
| 场景 | 时间复杂度 | 说明 |
|---|---|---|
| 最坏情况 | O(n²) | 数组完全逆序 |
| 平均情况 | O(n²) | 约 n²/2 次比较和交换 |
| 最好情况 | O(n) | 数组已有序，一轮遍历后提前终止 |
| 空间复杂度 | O(1) | 原地排序，仅用常数额外空间 |
代码实现
关键代码片段
// 基础冒泡排序（无提前终止）
void sort(int[] nums) {
int n = nums.length;
int sortedIndex = 0;
while (sortedIndex < n) {
// 倒序遍历，交换逆序对
for (int i = n - 1; i > sortedIndex; i--) {
if (nums[i] < nums[i - 1]) {
int tmp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = tmp;
}
}
sortedIndex++;
}
}
// 优化版：提前终止
void sort(int[] nums) {
int n = nums.length;
int sortedIndex = 0;
while (sortedIndex < n) {
boolean swapped = false;
for (int i = n - 1; i > sortedIndex; i--) {
if (nums[i] < nums[i - 1]) {
int tmp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = tmp;
swapped = true;
}
}
if (!swapped) break;
sortedIndex++;
}
}
实现要点
- 倒序遍历：从数组末尾向 sortedIndex 遍历，让最小值逐步前移
- 相邻交换：只交换
nums[i]和nums[i-1]，保证稳定性 - 提前终止标志：用
swapped变量记录本轮是否发生交换
对比分析
| 维度 | 冒泡排序 | 选择排序 |
|---|---|---|
| 时间复杂度（最坏） | O(n²) | O(n²) |
| 时间复杂度（最好） | O(n)（提前终止） | O(n²)（无法优化） |
| 稳定性 | 稳定 | 不稳定 |
| 交换次数 | 较多（每次逆序都交换） | 较少（每轮只交换一次） |
| 适用场景 | 近乎有序的数组 | 不关心稳定性时 |
应用场景
- 教学演示：最简单的稳定排序算法之一
- 小规模数据排序
- 近乎有序的数组（提前终止优化生效）
- 需要稳定排序且对时间要求不严格的场景
验证方法
- 可通过 LeetCode 912「排序数组」验证（会超时，但验证正确性）
- 测试稳定排序：用
(value, originalIndex)元组验证相同值相对位置不变
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 912. 排序数组 | 中等 |
相关概念
相关实体
- labuladong：本文作者，算法学习平台
总结
冒泡排序是对选择排序的优化，通过交换相邻逆序对实现稳定排序，并支持提前终止来利用数组的有序度。虽然时间复杂度仍是 O(n²)，但在近乎有序的场景下表现更好。