★ FEATURED ARTICLE 排序算法是每个程序员绕不开的基础课面试时手指比脑子还快就能写出来。但你会发现让一个人背着写一遍冒泡排序的 Java 代码大多数人都能写对可一旦追问“为什么内层循环要减掉i”“为什么交换次数还能继续优化”“它到底稳定在哪”很多人就卡壳了。这篇就用我平时带新人和自己复习时的习惯把冒泡排序从原理到边界、从优化到调试一步步拆开讲透。内容不仅面向刚学 Java 的入门者也适合想把这个老算法讲给别人的开发者或者正在准备面试、想把手写排序写得干净漂亮的朋友。1. 算法思路拆解它为什么叫“冒泡”1.1 核心机制相邻比较把大值一路推到队尾冒泡排序的核心动作只有两件事比较相邻两个元素如果顺序不符合要求就交换位置。就像班里排队让最高的人从队伍头逐个和旁边的人比谁高谁往后挪走完一整趟最高的人就被“挤”到了队伍末尾。这个过程中值比较大的元素会像气泡一样慢慢“浮”到数组后方所以叫冒泡排序。每一趟结束后当前未排序部分的最大值就确定位置了。接下来再对前面剩下的人重复同样的操作直到整个队伍都按身高排好。用数组语言描述就是外层循环控制需要执行的趟数内层循环在每一趟里完成相邻比较和交换。这里有一个容易被忽略的关键点冒泡排序比较的是相邻元素这决定了它是一种稳定的排序算法。什么叫稳定就是如果数组里有两个值相等的元素排序后它们原始的相对顺序不会改变。比如[3a, 2, 3b]这里的3a和3b数值都是 3但因为只用相邻比较3a永远不会越过3b交换位置所以3a依然在3b前面。这一点在按多关键字排序时很重要比如先按分数排再按学号排稳定性保证第一次排序的相对结果不会被打乱。1.2 复杂度画像为什么它适合教学却不太适合大规模排序不优化的情况下冒泡排序的比较次数是固定的。对于一个长度为n的数组第一趟要比较n-1次第二趟n-2次一直到最后一趟1次总比较次数是n(n-1)/2。交换次数的上限也是这个数量级比如待排序数组是完全逆序的每个比较几乎都要伴随一次交换。所以最坏和平均时间复杂度都是O(n²)空间复杂度是O(1)因为只用了几个临时变量属于原地排序。O(n²)意味着什么当n是 10 万时最坏情况要执行大约 50 亿次比较这在现代 CPU 上也要数秒甚至更久对真实业务来说是完全不值得的。但在n小于几百、或者数据基本有序的场景里配上优化手段它的表现并不会很难看而且代码简洁不容易藏 bug。我平时更愿意把冒泡排序当作“理解算法复杂度”的第一块教材。它足够简单让你一眼看清楚嵌套循环为什么会导致平方级复杂度它又足够完整包含了稳定排序、原地排序、早期退出优化这些后续理解高级排序时需要的基本概念。学透它之后再去看快排、归并的复杂度推导就不会那么吃力了。2. 写对边界条件细节里藏着半个算法2.1 双层循环下标的数学推导很多人手写冒泡排序时出问题基本都出在循环边界上。先给出一版经典实现public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) { return; } for (int i 0; i arr.length - 1; i) { // 外层循环趟数 for (int j 0; j arr.length - 1 - i; j) { // 内层循环本趟比较的对数 if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }外层i为什么要小于length - 1因为只剩下一个元素时它不用再参与排序自己一定就是最小的。换句话说把n个元素排好序最多需要n-1趟因为每一趟至少能把一个最大值放到最终位置。内层j为什么要小于length - 1 - i因为经过i趟之后数组末尾已经有i个元素是排好序的它们已经就位不需要再参与后续比较了。比如第一趟i0内层要比较length-1对最后一趟ilength-2内层只需要比较 1 对。有一个我见过很多次的错误内层循环不小心写成了j arr.length - 1没有减i。这不会立刻报错因为数组不会越界但每一趟都会把已经排好的末尾元素再参与比较排序结果虽然还是对的效率却差了不少而且逻辑上就不严谨了。另一个更危险的问题是内层写成j arr.length访问arr[j 1]时就会抛出ArrayIndexOutOfBoundsException。这类错误在建表排查时非常典型后面我专门整理了速查表。2.2 用标志位提前退出最好情况降到 O(n)基础的冒泡排序有一个明显浪费就算数组已经有序它依然会老实执行完n(n-1)/2次比较。举个例子[1, 2, 3, 4, 5]是排好的但上面的代码还是会一趟一趟地比较毫无意义。优化思路很简单每一趟开始时假定数组已经有序如果这一趟过程中发生过任何一次交换说明还没有完全排好如果一趟走完一次交换都没发生那就可以直接结束。实现上只需要加一个布尔变量public static void bubbleSortOptimized(int[] arr) { if (arr null || arr.length 2) { return; } for (int i 0; i arr.length - 1; i) { boolean swapped false; for (int j 0; j arr.length - 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; } } }注意一个细节swapped必须定义在每一轮外层循环的里面也就是每趟开始重置为false。如果定义在外层循环外面第一趟交换过一次之后它就一直是true后面的“提前退出”永远不会触发优化就失效了。这个位置问题是实际写代码时特别容易踩的坑我教过的几个同事都栽在这里过。加了这段之后最好情况数组完全有序只需要跑第一趟比较n-1次就能发现没有交换然后结束时间复杂度降到O(n)。这个性质在面试里经常被问到答对的人不多因为多数人只记得平均和最坏情况。2.3 升级到泛型与对象排序避坑点在哪里上面的代码只处理int[]。真实项目里排序的对象往往是自定义类型比如用户对象按年龄排学生对象按分数排。这时候最好把冒泡排序封装成泛型方法用一个Comparator传入比较规则。public static T void bubbleSort(T[] arr, Comparator? super T comparator) { if (arr null || arr.length 2) { return; } for (int i 0; i arr.length - 1; i) { boolean swapped false; for (int j 0; j arr.length - 1 - i; j) { if (comparator.compare(arr[j], arr[j 1]) 0) { T temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } if (!swapped) { break; } } }有几个要注意的地方。第一用comparator.compare(a, b) 0判断 a 是否排在 b 后面第二交换对象数组的引用和基本类型数组的交换在原理上一样第三当数组包含null元素时直接调用compare会抛空指针异常所以真实场景里要先明确 null 放到最前还是最后在比较器里写清楚规则。还有一种情况是数组本身是null方法开头必须做空判断否则调用arr.length就会报错。另外泛型数组的创建在 Java 里比较麻烦比如new T[10]直接写是不行的。如果调用方传进来的是Integer[]那直接用T[]接收即可不需要自己创建数组。这也是为什么实际项目里更常用ListT搭配Collections.sort而不是手写泛型排序但作为练习和理解底层原理泛型版本值得写一遍。3. 手写一遍完整实现从零到可运行3.1 带日志版本的冒泡排序一眼看懂每趟变化学习阶段我强烈建议写一个带日志的版本。不要只写“排序成功”而是每一趟结束都打印当前数组这样你能直观看到最大值是怎么一步步“沉”到末尾的。我之前带新人时会让他们必做这一步效果远好过对着代码空想。package demo.sort; import java.util.Arrays; public class BubbleSortDemo { public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) { return; } for (int i 0; i arr.length - 1; i) { boolean swapped false; System.out.println(第 (i 1) 趟开始前的数组 Arrays.toString(arr)); for (int j 0; j arr.length - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } System.out.println(第 (i 1) 趟结束后的数组 Arrays.toString(arr)); if (!swapped) { System.out.println(第 (i 1) 趟无交换直接结束); break; } } } public static void main(String[] args) { int[] arr {5, 1, 4, 2, 8}; System.out.println(原始数组 Arrays.toString(arr)); bubbleSort(arr); System.out.println(最终结果 Arrays.toString(arr)); } }运行这段代码你会看到类似下面的输出原始数组[5, 1, 4, 2, 8] 第 1 趟开始前的数组[5, 1, 4, 2, 8] 第 1 趟结束后的数组[1, 4, 2, 5, 8] 第 2 趟开始前的数组[1, 4, 2, 5, 8] 第 2 趟结束后的数组[1, 2, 4, 5, 8] 第 3 趟开始前的数组[1, 2, 4, 5, 8] 第 3 趟结束后的数组[1, 2, 4, 5, 8] 第 3 趟无交换直接结束 最终结果[1, 2, 4, 5, 8]第一趟里8 作为最大值被一路交换到最后面。第二趟本应处理前 4 个元素但过程中 4 和 2 交换后数组就已经有序了。第三趟开始时还没有意识到已经有序跑完发现全程没有一次交换于是触发swapped false提前 break。整个过程非常清晰颗粒度刚刚好比抽象地背“每趟确定一个最大值”直观得多。我还会在这台环境里加一个交换次数的计数器看每个数据集到底发生了多少次交换。这个有助于你对“逆序数组基本每比较一次就交换一次”这句话产生感性认识而不是只记数字结论。3.2 测试用例设计不要只靠主方法 print 验证在主方法里println看结果在简单练习里没问题。但如果你封装的排序方法要给别人用最好写真正的单元测试。测试用例怎么设计我总结了一个比较全的清单普通乱序数组{5, 1, 4, 2, 8}完全逆序数组{9, 8, 7, 6, 5}完全有序数组{1, 2, 3, 4, 5}含重复元素{4, 2, 2, 8, 2}含负数和零{-3, 0, -8, 7, 1}空数组{}单元素数组{42}所有元素相同{7, 7, 7, 7}每种数据都要断言排序后数组正确。以 JUnit 5 为例Test void testRandomArray() { int[] arr {5, 1, 4, 2, 8}; BubbleSortDemo.bubbleSort(arr); int[] expected {1, 2, 4, 5, 8}; assertArrayEquals(expected, arr); } Test void testDuplicateElements() { int[] arr {4, 2, 2, 8, 2}; BubbleSortDemo.bubbleSort(arr); int[] expected {2, 2, 2, 4, 8}; assertArrayEquals(expected, arr); } Test void testEmptyArray() { int[] arr {}; BubbleSortDemo.bubbleSort(arr); assertArrayEquals(new int[] {}, arr); }有人觉得这种测试太简单但排序算法的边界条件恰恰就藏在这些极端输入里。空数组能不能不报错单元素能不能不进入无意义的循环全部相等的数组能不能提前退出这些问题不实际跑一遍很难注意到。写一个排序方法时先把这些用例跑绿比以后再回来排查要省时间。3.3 手写过程中最容易出问题的四个位置手写代码时我会特别盯住四个关键位置。第一个是空判断。很多人的排序方法直接进入循环一旦传进来null访问arr.length就抛空指针错误这在生产环境是低级却又常见的 bug。第二个是临时变量temp的作用域和值。交换arr[j]和arr[j1]时先把其中一个值存到temp然后分三步完成交换这三步的先后顺序绝对不能搞错。有的新手喜欢写成arr[j] arr[j1]; arr[j] arr[j1];结果把两个元素变成同一个值这是少了中间变量的典型错误。第三个是比较方向。如果要从大到小排序把改成就行。这个地方太容易反了我甚至建议在方法命名上写清楚是升序还是降序比如bubbleSortAsc和bubbleSortDesc。第四个是swapped标志位的位置。开头强调过必须放在外层循环内部每趟重置不然优化失效。使用Arrays.toString()打印数组时别直接打印数组变量本身比如System.out.println(arr)那样输出的是一串看不懂的引用地址如[I1b6d3586初学者经常在这个小地方摸不着头脑。4. 常见问题速查与独家避坑心得4.1 典型报错与逻辑 bug 速查表我在协助排查排序相关代码时遇到最多的几类问题整理成了下面这个表每个都给出了现象、原因和修复方式照着排查就行。现象原因修复方法ArrayIndexOutOfBoundsException内层循环边界写成j arr.length访问arr[j1]越界改为j arr.length - 1 - i排序后数组没有完全有序内层边界漏掉-i导致某些元素交换不到位或外层循环趟数不足外层为i length-1内层为j length-1-i排序过程无法提前结束swapped标志位定义在外层循环外面永远不会重置为false把boolean swapped false移到外层循环内部数组全部变成相同数字交换时没有使用temp暂存变量赋值覆盖了另一个元素用三步交换temp arr[j]; arr[j] arr[j1]; arr[j1] temp;空数组或null报空指针方法开头没有做空判断 / 长度小于 2 判断加 if (arr null从大到小排列时结果反了比较运算符方向写反升序用arr[j] arr[j1]降序改为arr[j] arr[j1]实际排障时我习惯先打印原始数组和每趟结果马上就能定位是哪个阶段出了问题。如果直接看最终结果你会发现数组已经部分排好序但又不是完全有序这种半完成状态通常就是循环边界不对。4.2 面试追问中真正拉开差距的三个知识点手写冒泡排序只是热身题面试官真正考察的是追问环节。第一个高频追问是“稳定吗为什么稳定”。回答要提到冒泡排序只交换相邻逆序元素相等的元素不会彼此交换所以原始相对顺序能保留。第二个是“最好情况时间复杂度是多少前提是什么”。加了提前退出优化后最好情况是O(n)对应输入已经有序的情况要是没加优化最好情况也是O(n²)这个前提必须说清楚。第三个是“能不能在一次遍历里同时确定最大值和最小值”。这就是冒泡排序的变体叫鸡尾酒排序或双向冒泡排序先从前往后排一个最大值再从后往前排一个最小值来回交替。它可以稍微减少一些遍历次数但时间复杂度依然是O(n²)。如果被问到“Java 自带排序为什么不用冒泡”可以从两个角度回答。第一Arrays.sort对基本类型使用双枢轴快速排序对对象类型使用 TimSort 之类的稳定排序它们在大数据量下的性能远超冒泡排序。第二冒泡排序的比较和交换操作在 CPU 缓存利用方面并不占优它每趟都要反复访问相邻元素但数据规模大时缓存命中率并不好。当然这个问题里不需要展开底层实现点到即可核心是让面试官看到你知道不同算法有不同适用场景。4.3 实战中的性能体验与选型建议拿一组一万个随机整数来测试不优化的冒泡排序在我的开发机普通办公笔记本上耗时大约几百毫秒到一秒之间。看起来还能接受但把数据量加到十万时间会急剧上升到几十秒换成百万级数据基本就不适合继续等了。这不是 Java 本身慢而是平方级算法的本质限制。数据量翻倍耗时大约是原来的四倍这个增长趋势会让再好的硬件也无济于事。所以我给出的选型建议是这样的如果排序数据的规模小于几百或者数据本身已经趋近于有序冒泡排序加上提前退出优化写起来简单代码也好理解可以用。如果数据规模大、或者需要稳定的稳定排序且不想额外写复杂算法优先用Arrays.sort或Collections.sort不要自己造轮子。冒泡排序真正的舞台是教学、面试基本功、以及帮助你理解“嵌套循环 条件交换”这一类底层算法模式。另外还有一点经验。项目里如果对对象列表排序而且对稳定性有要求比如先按时间排序再按优先级排序我会用稳定的Collections.sort而不是手写冒泡。手写冒泡更多是用在单纯为了理解原理或者在一些非常特殊的受限硬件环境里比如内存很小、不能分配额外数组又要求原地稳定排序这种情况在平时的应用开发中很少遇到。我在实际带人写这个算法时最深的体会是“跑起来看结果”比“背模板”重要太多。只要你能亲手打印出每一趟的结果亲眼看到最大值是怎么一步一步移动到最后面的边界条件为什么要减一提前退出什么时候触发这些细节就不再是死记硬背了。最后分享一个小技巧在学习冒泡排序的时候可以顺手画一张数组下标和元素值的变化图每次交换就在图上划一条线画完两三趟你就会发现所谓“冒泡”的本质就是一趟确定一个元素的最终位置。这个理解建立起来了再看其他排序算法会顺很多。
阅读完成 · 觉得有帮助？
