Java 冒泡排序：最简单的排序，没有之一
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]在这个图解中，i和j是冒泡排序中两层循环的“指针”，它们各自承担着完全不同的职责。
（1）.i—— “趟数计数器”（外循环）
- 它代表什么：表示已经有多少个最大的元素被排到了数组末尾。
- 它的作用：控制总共需要执行多少轮“冒泡”过程。
- 取值范围：在
n=5的数组中，i从0开始，到3结束（即i < n-1）。- 因为每冒泡一趟，末尾就固定一个数。排好 4 个数后，剩下的 1 个自然就在最前面了，所以只需要
n-1趟。
- 因为每冒泡一趟，末尾就固定一个数。排好 4 个数后，剩下的 1 个自然就在最前面了，所以只需要
- 结合图解看：
- 第 1 趟（
i=0）：末尾 0 个已排好，目标是把最大的 8 冒到最后。 - 第 2 趟（
i=1）：末尾已经有 1 个（8）排好了，目标是把剩下的最大数 7 冒到倒数第二位。 - 第 3 趟（
i=2）：末尾已经有 2 个（7，8）排好了，继续处理剩余部分。
- 第 1 趟（
（2）.j—— “比较指针”（内循环）
它代表什么：表示当前正在进行“两两比较”时，左边那个元素的下标位置。
它的作用：在每一趟中，从数组的最左边开始，逐一进行相邻元素的两两比较（
arr[j]和arr[j+1]），并决定是否交换。取值范围：
j从0开始，到n - 2 - i结束。- 为什么要减去
i？因为末尾的i个元素已经是最大的且排好序了，指针不需要再去碰它们，这样可以少做无用功。 - 为什么要减 2？因为比较的是
j和j+1，为了保证j+1不越界，j最大只能到倒数第二个位置（即n-2）。
- 为什么要减去
结合图解看（
n=5）：- 第 1 趟（
i=0）：j从 0 到5-2-0=3。即依次比较下标(0,1)、(1,2)、(2,3)、(3,4)，把 8 一路换到最后。 - 第 2 趟（
i=1）：j从 0 到5-2-1=2。只比较下标(0,1)、(1,2)、(2,3)，不去碰下标 4（因为 8 已经在那了），把 7 换到下标 3 的位置。 - 第 3 趟（
i=2）：j从 0 到5-2-2=1。只比较(0,1)和(1,2)，不去碰末尾的 7 和 8。
- 第 1 趟（
(3). 一句话总结它们的配合
i负责“缩小战场”（每过一轮，末尾就多一块已排序的“禁区”），j负责“在战场内扫荡”（从左往右挨个比，把当前战区内最大的那个赶到战区的最后边界）。
如果用伪代码写出来，它们的嵌套关系就是：
for i = 0 到 n-2: // i 控制趟数 for j = 0 到 n-2-i: // j 控制当前趟的比较位置（边界随 i 缩小） 比较 arr[j] 和 arr[j+1]，若逆序则交换1.3 三个关键观察
- 每趟结束后，末尾的元素一定是有序的——最大的已经"沉底"了
- 第 i 趟只需要比较到 n-1-i——因为后面 i 个已经排好
- 如果某趟没有发生任何交换，说明数组已经有序——可以提前终止（这就是最优 O(n) 的来源）
2. 完整 Java 实现
importjava.util.Arrays;publicclassBubbleSort{/** * 冒泡排序（带提前终止优化） * @param arr 待排序数组（原地修改） */publicstaticvoidbubbleSort(int[]arr){if(arr==null||arr.length<2){return;}intn=arr.length;for(inti=0;i<n-1;i++){booleanswapped=false;for(intj=0;j<n-1-i;j++){if(arr[j]></