Java 冒泡排序：最简单的排序，没有之一

面试官让手写排序？掏出冒泡，至少能及格

引言

冒泡排序（Bubble Sort）是所有排序里最像”废话文学”的那个——原理简单到不用脑子：大的往后冒，小的往前浮，一趟一趟比，直到整个数组有序。

但别因为它简单就轻视——冒泡写不对的人，比写对的人多。尤其是两层循环的边界 + 提前终止优化，能筛掉一半”背代码党”。

这篇文章，我会把冒泡拆到不能再拆：

• 用 ASCII 图演示每一趟的真实变化
• 推导为什么最优情况是 O(n) 而不是 O(n²)
• 列出 5 个高频易错点（不是 3 个）
• 配套 LeetCode 真题 912 和 冒泡变形题

读完这篇，冒泡排序的所有面试坑，你都能避开。

---

1. 核心思想：像水泡一样往上浮

冒泡的精髓用一句话讲：每趟把当前未排序部分的最大元素”冒”到末尾。

1.1 通俗理解

想象一排水泡，最重的水泡往下沉，最轻的往上浮。但冒泡排序反过来——大的往后走，因为大的元素通过相邻交换会逐渐移动到最右端。

1.2 ASCII 图解演示

以数组 [5, 2, 8, 4, 7] 为例，看完整排序过程：

初始：[5, 2, 8, 4, 7]

第 1 趟（i=0，j 从 0 到 3）：
  [5, 2, 8, 4, 7]  →  5 > 2，交换
  [2, 5, 8, 4, 7]  →  5 < 8，不交换
  [2, 5, 8, 4, 7]  →  8 > 4，交换
  [2, 5, 4, 8, 7]  →  8 > 7，交换
  结果：[2, 5, 4, 7, 8]   ← 8 已经冒到最后

第 2 趟（i=1，j 从 0 到 2）：
  [2, 5, 4, 7, 8]  →  2 < 5，不交换
  [2, 5, 4, 7, 8]  →  5 > 4，交换
  [2, 4, 5, 7, 8]  →  5 < 7，不交换
  结果：[2, 4, 5, 7, 8]   ← 7 已经到位

第 3 趟（i=2，j 从 0 到 1）：
  [2, 4, 5, 7, 8]  →  2 < 4，不交换
  [2, 4, 5, 7, 8]  →  4 < 5，不交换
  swapped = false，提前终止！

最终：[2, 4, 5, 7, 8]

1.3 三个关键观察

1. 每趟结束后，末尾的元素一定是有序的——最大的已经”沉底”了
2. 第 i 趟只需要比较到 n-1-i——因为后面 i 个已经排好
3. 如果某趟没有发生任何交换，说明数组已经有序——可以提前终止（这就是最优 O(n) 的来源）

---

2. 完整 Java 实现

import java.util.Arrays;

public class BubbleSort {
    /**
     * 冒泡排序（带提前终止优化）
     * @param arr 待排序数组（原地修改）
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 三步交换法
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 优化：如果本趟没有交换，说明已有序
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

---

3. 复杂度证明（不是只背结论）

3.1 时间复杂度

最坏情况（O(n²)）：数组完全逆序

• 第 1 趟需要 n-1 次比较
• 第 2 趟需要 n-2 次比较
• …
• 第 n-1 趟需要 1 次比较
• 总比较次数 = (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n²)

最好情况（O(n)）：数组已经有序

• 第 1 趟遍历一次，发现没有交换 → swapped = false → break
• 只跑了 1 趟，总比较次数 = n-1 = O(n)

平均情况（O(n²)）：

• 数组随机分布，期望需要约 n²/4 次比较
• 仍是 O(n²) 量级

3.2 空间复杂度

• 只使用了常数个额外变量（i, j, swapped, temp）
• **O(1)**，原地排序

3.3 稳定性

• 比较条件是 arr[j] > arr[j + 1]（严格大于，没有等号）
• 相同元素不会交换
• 稳定排序

---

4. 五个高频易错点（面试必看）

易错点 1：外层循环写 i < n

// ❌ 错误：会多跑一趟
for (int i = 0; i < n; i++) { ... }

// ✅ 正确：n 个元素排 n-1 趟即可
for (int i = 0; i < n - 1; i++) { ... }

原理：n 个元素只需要 n-1 次就能排好（第 n 趟只剩 1 个元素，无需再排）。

易错点 2：内层循环忘记减 i

// ❌ 错误：会重复比较已有序的末尾元素
for (int j = 0; j < n - 1; j++) { ... }

// ✅ 正确：第 i 趟后，末尾 i 个已经有序
for (int j = 0; j < n - 1 - i; j++) { ... }

易错点 3：忘记加 swapped 标志

// ❌ 错误：已经有序的数组也要跑满 n²
public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
        }
    }
}

// ✅ 正确：加 swapped 实现提前终止
boolean swapped = false;
if (!swapped) break;

易错点 4：比较条件写成 >=

// ❌ 错误：相同元素会交换 → 不稳定
if (arr[j] >= arr[j + 1]) swap(arr, j, j + 1);

// ✅ 正确：严格大于，保持稳定
if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);

易错点 5：用 i + 1 取数组越界

// ❌ 错误：j 最大值为 n-1，arr[j+1] = arr[n] 越界
for (int j = 0; j < n - i; j++) {
    if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
}

// ✅ 正确：j 最大值为 n-1-i
for (int j = 0; j < n - 1 - i; j++) {
    if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
}

---

5. 适用场景与禁区

5.1 适用场景

• 数据量极小（n < 100）：冒泡虽然慢，但代码简单，常数小
• 基本有序的数组：配合 swapped 优化，O(n) 跑完
• 教学演示：理解排序的最直观入门
• 嵌入式系统：对稳定性有要求且内存极小时

5.2 不适用场景

• 大数据量（n > 1000）：O(n²) 跑不动
• 生产环境排序：直接用 Arrays.sort() 或 Collections.sort()
• 对性能敏感的实时系统：选择快排或堆排

---

6. 面试常见变形（附解题思路）

变形 1：鸡尾酒排序（双向冒泡）

思路：从左到右冒大 + 从右到左冒小交替进行

public static void cocktailSort(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        for (int j = left; j < right; j++) {
            if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
        }
        right--;
        for (int j = right; j > left; j--) {
            if (arr[j] < arr[j - 1]) swap(arr, j, j - 1);
        }
        left++;
    }
}

优点：对基本有序的数组比单向冒泡更高效。

变形 2：冒泡找第 k 大元素

思路：只跑 k 趟冒泡，第 k 趟结束后，末尾第 k 个就是第 k 大

public static int findKthLargest(int[] arr, int k) {
    int n = arr.length;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
        }
    }
    return arr[n - k];
}

适用：k 较小时（k < n/2），比全排序后取第 k 位更省时间。

变形 3：奇偶排序（适合并行）

思路：分奇数位和偶数位两轮交替比较

public static void oddEvenSort(int[] arr) {
    int n = arr.length;
    boolean sorted = false;
    while (!sorted) {
        sorted = true;
        // 奇数位
        for (int i = 1; i < n - 1; i += 2) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                sorted = false;
            }
        }
        // 偶数位
        for (int i = 0; i < n - 1; i += 2) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                sorted = false;
            }
        }
    }
}

优点：两轮独立，可并行处理（GPU 排序常用）。

---

7. LeetCode 真题实战

题目 1：912. 排序数组（中等）

描述：给你一个整数数组 nums，请你将该数组升序排列。

冒泡解法：直接套用上面的 bubbleSort 模板。

复杂度分析：

• 时间 O(n²)，空间 O(1)
• 在 LeetCode 上 n=50000，冒泡会超时（只能过部分测试用例）

实战建议：这道题冒泡能写对边界条件就算过关，但提交时用快排或堆排才能 AC。

题目 2：剑指 Offer 45. 把数组排成最小的数

这道题不用冒泡，但可以用冒泡的”交换”思想：

• 自定义比较器："3" + "12" vs "12" + "3" → 前者小
• 然后用任意稳定排序（冒泡也行）即可

---

总结

一句话精髓

冒泡 = 相邻比较 + 大的往后 + 提前终止。

三个关键洞察

1. 最优 O(n) 是靠 swapped 标志换来的，没这个标志永远是 O(n²)
2. 稳定排序靠的是严格大于号 >，不是 >=
3. 工程上几乎不用，但面试会考（考的是细节掌握）

下一步行动

1. 把上面 5 个易错点逐个手写一遍，确保每个都不会错
2. 尝试用冒泡解 LeetCode 912，看看到第几个测试用例超时
3. 鸡尾酒排序手写一遍，对比单向冒泡的差异

---