Java 冒泡排序：从零实现到提前终止

5 分钟搞懂最基础也最经典的排序算法

引言

冒泡排序（Bubble Sort）是大多数程序员的第一个排序算法。原理简单到一句话能讲清——重复遍历，相邻比较，逆序就换。但简单的算法里藏着两个关键优化点：提前终止、有序标志位。

1. 核心思想

冒泡排序 = 相邻比较 + 逆序交换

• 遍历数组，依次比较相邻两个元素
• 如果前者大于后者，交换位置
• 一轮遍历后，最大的元素会”冒”到数组末尾
• 重复上述过程，直到整个数组有序

时间复杂度：**O(n²)（最坏/平均情况），O(n)**（最佳情况，已排序数组）。

2. Java 实现

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        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[] array = {64, 34, 25, 12, 22, 11, 90};
        System.out.print("排序前：");
        for (int num : array) System.out.print(num + " ");
        bubbleSort(array);
        System.out.print("\n排序后：");
        for (int num : array) System.out.print(num + " ");
    }
}

运行结果：

排序前：64 34 25 12 22 11 90
排序后：11 12 22 25 34 64 90

3. 关键优化点

优化 1：提前终止

内层循环加一个 swapped 标志位。如果一整轮没有任何交换，说明数组已经有序，直接 break 退出。

**这能把已排序数组的时间复杂度从 O(n²) 降到 O(n)**——这是冒泡排序和插入排序在”基本有序”数据上的关键差距。

优化 2：缩小内层范围

内层循环条件 j < n - 1 - i 而不是 j < n - 1——因为每轮结束后，数组末尾的 i 个元素已经是有序的，不需要再比较。

4. 适用场景

冒泡排序不是高性能排序算法，生产环境不要用。它的价值在于：

• 入门学习：理解排序的”比较-交换”基本动作
• 教学场景：直观展示”为什么需要优化”
• 近乎有序的小数据：借助提前终止优化，冒泡可能比快排更快

**实际项目用 Arrays.sort()**（底层是归并+TimSort），不要自己写。

总结

冒泡排序 = 相邻比较 + 逆序交换。简单但藏着两个关键优化：swapped 标志位提前终止、内层范围递减。

下一步：用同样的思路学一遍选择排序和插入排序，对比三者的实现差异和性能差距。

---