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趟。结合图解看：第 1 趟（i=0）：末尾 0 个已排好，目标是把最大的 8 冒到最后。第 2 趟（i=1）：末尾已经有 1 个（8）排好了，目标是把剩下的最大数 7 冒到倒数第二位。第 3 趟（i=2）：末尾已经有 2 个（7，8）排好了，继续处理剩余部分。（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。(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.length2){return;}intn=arr.length;for(inti=0;in-1;i++){booleanswapped=false;for(intj=0;jn-1-i;j++){if(arr[j]/
Java 冒泡排序：最简单的排序，没有之一
发布时间：2026/6/20 23:42:46
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趟。结合图解看：第 1 趟（i=0）：末尾 0 个已排好，目标是把最大的 8 冒到最后。第 2 趟（i=1）：末尾已经有 1 个（8）排好了，目标是把剩下的最大数 7 冒到倒数第二位。第 3 趟（i=2）：末尾已经有 2 个（7，8）排好了，继续处理剩余部分。（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。(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.length2){return;}intn=arr.length;for(inti=0;in-1;i++){booleanswapped=false;for(intj=0;jn-1-i;j++){if(arr[j]/
