“请你当场写一段冒泡排序。”——这是我做技术面试时经常问的第一道算法题。让我意外的是真正能在纸上把冒泡排序写对、写清楚的人比想象中少得多。不少人一上来就写两层for循环第二层循环的结束条件随手写个arr.length或者把外层循环写成i n看起来能跑但要么多跑一轮要么在边界上稀里糊涂。更别说问他“这轮交换为什么必须用临时变量”“如何证明它稳定”了。所以这篇博文不打算只丢一段标准代码。我把它拆成了六个部分冒泡排序到底在什么场景下还有使用价值、每一层循环的语义是什么、三种常见优化各自怎么实现、为什么你的排序会越排越乱、以及它和其他排序算法相比到底该在什么时候选。读完后你再写冒泡排序应该能写出带解释的版本而不是默写模板。1. 冒泡排序的适用场景它不只是课堂作业冒泡排序的原理很简单从头到尾依次比较相邻元素如果前一个比后一个大就交换它们。每一轮结束当前范围内的最大值就像气泡一样“冒”到末尾。重复 n-1 轮之后整个数组就是有序的。很多人对它的第一反应是“教学玩具”复杂度 O(n²)、交换频繁、性能差出来工作之后几乎用不上。这话有道理但不完全对。我自己在实际项目中就偶尔会用到它因为在以下三种场景里它反而比写个快速排序更顺手。第一种是数据量极小的情况。内存里只有十几个、几十个元素的配置列表用完即弃排序一次的时间开销可以忽略不计。你专门引入一个复杂排序反而增加了代码阅读成本。第二种是数组近乎有序的情况。比如一个实时更新的排行榜大部分元素的相对位置没变只有几个新变化的数据乱序。这个时候如果加上了“提前退出”的优化冒泡排序可以在接近 O(n) 的时间里完成比递归式的快速排序少很多无谓开销。第三种是嵌入式或极简运行环境。某些受限环境里没有完整的 JDK 类库连Arrays.sort都不存在你只能手写排序。在这种场景里最不容易写错、最好验证的原地稳定排序其实就是冒泡排序。但数据规模一旦大到十万级别冒泡排序就比较吃力了。简单估算一下在最坏情况下比较次数接近 n(n-1)/2也就是约 50 亿次比较这个量级在普通机器上很难在可接受时间内跑完。所以选型的时候我心里会过一遍标准数据量小、数据近似有序、无法调用库函数至少满足一条才考虑冒泡否则就直接用 Java 自带的排序。我还记得曾经给一个小型排名功能做过排序列表最多二三十个对象我当时图省事写了冒泡。上线后运行得很平稳。后来业务膨胀到几千个数据我立刻换成了其他排序。这不是说冒泡一无是处而是你要清楚它的边界在哪里。2. 手写基础版外层循环、内层循环和变量交换的语义先给出一段最基础的 Java 实现没有任何优化但结构完整适合作为讨论起点。public class BubbleSort { 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]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } } }我先把这段代码的每个部分讲清楚因为这才是面试官真正想听的东西。外层循环用i表示“已经排到末尾的元素个数”。第一轮结束时最大的数一定到arr[n-1]第二轮结束后第二大的数一定到arr[n-2]。以此类推到第 n-1 轮结束时只剩第一个元素没处理它必然是全局最小的不需要再比较。所以外层循环只需要运行 n-1 次这就是i n - 1而不是i n的原因。如果你写i n最后一轮内层循环的条件会变成j n - 1 - (n - 1)也就是j 0内层根本不会执行。虽然不会数组越界但属于纯粹的无效循环让人看了会觉得你边界没想清楚。内层循环用j表示当前这一轮要比较的相邻对中的左下标。第一轮需要比较所有n-1对也就是(0,1), (1,2), ..., (n-2, n-1)。第二轮开始末尾元素已经确定只需要比较n-2对。所以内层条件是j n - 1 - i。如果你写成j n - 1数组不会越界但每一轮都会重复比较已经归位的尾部元素白白增加耗时。我拿一个具体例子走一遍。对[5, 1, 4, 2, 8]做第一轮冒泡比较 5 和 1交换数组变成[1, 5, 4, 2, 8]比较 5 和 4交换数组变成[1, 4, 5, 2, 8]比较 5 和 2交换数组变成[1, 4, 2, 5, 8]比较 5 和 8不交换数组保持[1, 4, 2, 5, 8]第一轮结束8 到了末尾。第二轮比较[1, 4, 2, 5]最大的 5 被推到倒数第二个位置。如此反复最终得到[1, 2, 4, 5, 8]。交换操作我建议永远用三变量方式int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp;这种写法足够直白任何维护者一眼就能看懂。网上还有“不加临时变量”的异或交换比如a a ^ b; b a ^ b; a a ^ b;这种技巧在 Java 里没有任何实际收益。它可读性差而且如果两个值相等交换后其中一个会变成 0。还存在整数加法交换的溢出风险。工程代码要的是稳定和清晰不是奇技淫巧。如果你在面试中把这段讲透面试官至少能确认你是真的理解排序过程而不是背代码。3. 三种优化实测提前结束、双向冒泡、界限收缩基础版好理解但工程里我们会加优化。这一节我要说的三种优化网上文章不少但很少说明它们各自对什么输入有效、代码应该注意什么。我挨个讲。3.1 提前结束一轮没发生交换直接收工如果一个数组在某一轮扫描中没有发生任何交换那就说明相邻元素之间全部是顺序正确的整个数组已经有序不需要再继续后面几轮。这个优化只需要加一个布尔标志。public static void bubbleSort(int[] arr) { int n arr.length; boolean swapped; for (int i 0; i n - 1; i) { 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; } } }这个优化对“整体有序但少量逆序”的数据效果非常明显。最理想情况下一个本来就排好序的数组第一轮扫描 n-1 次后发现没有交换直接退出整体复杂度降为 O(n)。我在项目中遇到的最常见的调用场景恰恰就是这种“观察活数据排序修正少量乱序”的情况。3.2 双向冒泡鸡尾酒排序普通冒泡每一轮只把最大值往右推。但有些数据分布是“小值在右边大值在左边”比如[45, 2, 3, 4, 5, 1]。普通冒泡要很多轮才能把 1 一步步挪到开头。双向冒泡的思路是每轮先从左往右冒一个最大值到右端再从右往左冒一个最小值到左端让左右边界同时收缩。我贴一段可以实际运行的实现public static void cocktailSort(int[] arr) { int left 0; int right arr.length - 1; boolean swapped true; while (left right swapped) { swapped false; for (int j left; j right; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } right--; for (int j right; j left; j--) { if (arr[j] arr[j - 1]) { int temp arr[j]; arr[j] arr[j - 1]; arr[j - 1] temp; swapped true; } } left; } }实现上有几个坑。第一第二个反向循环的边界条件是j left因为 left 位置在上一轮之后已经确定不需要再比较arr[left]和arr[left - 1]。第二循环条件是left right swapped一旦某一轮没有交换整个数组就已经有序继续扫描没有意义。这个版本更复杂不是每次都能收益。我实测过它在“数据整体呈振荡结构、两端有序中间乱”的输入上效果最好能减少约一半的扫描轮数但对完全逆序的数组优化的意义并不大。如果你的代码是团队共同维护的我建议只在明确做了性能测试、确认瓶颈在这里的时候才引入双向冒泡否则提前终止优化已经够用了。3.3 界限收缩记住最后一次交换的位置在某些分布里数组后面一段已经排好只有前面一段还在乱序。比如[6, 5, 4, 3, 1, 2, 7, 8, 9]。第一轮做完后9 到末尾8 可能在原地7 也在原地但我们下一轮仍然会把后面的 7、8、9 重新扫描一遍浪费不少比较次数。记录最后一次交换位置可以让下一轮扫描只走到那个位置为止。因为最后一次交换发生之后后面的所有元素都已经归位不需要再碰。public static void bubbleSort(int[] arr) { int n arr.length; int lastSwap n - 1; while (lastSwap 0) { int bound lastSwap; lastSwap 0; for (int j 0; j bound; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; lastSwap j; } } } }这里我特意把外层for改成了while。因为我们要跟踪的是一个会不断收缩的边界而不是固定轮数。lastSwap初始值为n - 1保证第一轮覆盖全数组。进入循环后先把bound记录为当前交换边界然后开始扫描。扫描过程中如果发生交换就把lastSwap更新为j因为下一次扫描只需要走到这个位置就可以了。这三种优化并不是互斥的。你可以把提前终止和界限收缩组合在一起通常代码结构会变复杂一些我自己的建议是先加“提前终止”大多数场景收益最明显只有当你通过数据分布分析发现“尾部大段有序”时再考虑界限收缩双向冒泡则放在最后因为它最不容易一次写对。为了直观一点我把它们的基本表现放在一张表里。实现方式最坏比较次数最好比较次数额外空间稳定性基础版冒泡O(n²)O(n²)O(1)稳定提前终止冒泡O(n²)O(n)O(1)稳定双向冒泡O(n²)O(n)O(1)稳定界限收缩冒泡O(n²)O(n)O(1)稳定请注意这些优化的收益依赖输入数据本身的特征。如果你拿随机打乱的数据测试三种优化几乎都不改变 O(n²) 的复杂度下限真正的价值在于处理“基本有序”或“局部有序”的真实场景。4. 常见错误与调试思路为什么越排越乱、为什么倒数第二个数总不对我审过不少冒泡排序的手写代码常见的错误其实非常集中。先把它们列出来你对照检查自己的实现。4.1 内层循环条件写成了j arr.length这么写不会越界因为内层条件始终是j n - 1 - i而n - 1 - i最大不超过 n-1所以代码能跑。但它会带来两个问题一是尾部已经归位的元素会被反复拿出来比较造成完全没有必要的时间浪费二是如果你在循环体里动态修改数组长度就会出现不可预料的越界。很多初学者一开始图省事默认arr.length实际上丢掉了冒泡排序“每轮缩小范围”的关键思想。4.2 交换时用错了索引这是最让人头疼的错误之一。有人在外层循环里写if (arr[i] arr[i 1])但i代表的是轮数不是相邻对的左下标。一旦你这么写排序过程就完全走样了。正确的方式始终是让内层循环的下标j参与比较和交换。4.3 把写成了这看起来只是符号差异却会破坏排序稳定性。稳定性指的是两个相等元素在排序前和排序后的相对顺序不变。冒泡排序用时相等元素不会交换稳定性成立。如果你用相等元素会被强制交换一次它们的相对位置被破坏。对纯数字数组来说肉眼看不出来但如果你排的是包含“序号”字段的对象列表比如按分数排序的学生记录稳定性就是关键需求。4.4 忘记处理空数组和空引用代码int n arr.length遇到null会直接抛NullPointerException。如果你的排序方法是内部工具不处理也可以但最好在方法开头做个判断if (arr null || arr.length 2) { return arr; }空数组和只有一个元素的数组天然有序不需要任何比较。这个细节看起来不起眼但在批处理逻辑里能省去不少空指针排查时间。4.5 调试思路先最小化再打印过程如果你发现排序结果不对我建议按这个顺序排查先用最小输入复现比如[3, 1, 2]手工就能推演。打印每轮结束后的数组状态。最简单的做法是在每轮外层循环结束时加一行输出观察最大的元素是否按预期“冒”到末尾。写一个简单的isSorted辅助方法在排序前后调用快速确认结果是否有序。准备几组边界测试数据已排序数组、逆序数组、带重复元素的数组、带负数的数组、含Integer.MAX_VALUE的数组。我这里给一个可以直接用的校验函数private static boolean isSorted(int[] arr) { for (int i 1; i arr.length; i) { if (arr[i] arr[i - 1]) { return false; } } return true; }配合这个函数你可以在每次交换后主动校验但注意频繁调用会明显拖慢性能。实际调试时我一般只在排序结束时校验一次再把冒泡中每一轮的状态打印出来对照。5. 与其他排序的对比何时用冒泡、何时直接调 Arrays.sort我见过不少人在项目里明明可以直接调用Arrays.sort却非要用自己手写的冒泡排序美其名曰“我有完整实现”结果数据稍大就卡顿。所以我特别想在这个话题里做一次清晰的对比。先看一张通用对照表排序方式最坏时间复杂度最好时间复杂度额外空间稳定性交换次数特征冒泡排序O(n²)O(n)带提前终止O(1)稳定最多约 n²/2 次交换插入排序O(n²)O(n)O(1)稳定交换次数受逆序对数量影响选择排序O(n²)O(n²)O(1)不稳定最多 O(n) 次交换Java 内置排序远优于 O(n²)接近 O(n)视算法而定引用类型一般稳定内部经过大量调优插入排序和冒泡排序一样是 O(n²)但插入排序在“几乎有序”的数据上表现往往比冒泡排序更好因为它只需要较少比较就能找到插入位置而且它本质上就是扑克牌整理的方式代码也更短。选择排序的优点是交换次数很少适合交换成本极高的场景但它不稳定而且即使数据已经排好序也要跑满 n² 次比较不适合渐进有序的输入。所以在技术面试里如果问题只是“手写一个排序”很多有经验的人会选择插入排序而不是冒泡。我自己在带新人时也常提醒不要因为“冒泡听起来经典”就默认它是最优选择。那什么时候真的不用内置排序我总结成三条题目明确禁止调用库函数。运行环境不提供完整类库。你确实需要稳定排序并且数据量很小、自己实现比引入额外依赖更轻量。如果你的项目可以用 JDK绝大多数情况下直接Arrays.sort就好。内置排序对基本类型用的是高度优化的快速排序对引用类型用的则是一种基于归并思想、针对现实数据分布做过大量调优的稳定排序。你不需要重复造轮子只需要把注意力放在业务逻辑上。对于自定义对象如果你确实需要手写一个稳定排序冒泡的稳定性反而成了优势。前提是你要在比较时只做“大于”判断不要做“大于等于”这样相等元素永远不会被交换。6. 真实项目里的经验泛型版、稳定性与边界判断最后一节我想分享几个实际项目里积累的细节。第一个是如果你真的决定在项目里用冒泡排序我建议写一个泛型版本不要只写int[]的版本。泛型版本不光能排数字还能排任何实现了Comparable或你提供了Comparator的对象。下面这段代码我经常作为模板使用public static T extends Comparable? super T void bubbleSort(T[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; boolean swapped; for (int i 0; i n - 1; i) { swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j].compareTo(arr[j 1]) 0) { T temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } if (!swapped) { break; } } }这段代码有几个值得注意的地方泛型边界写成T extends Comparable? super T可以让任何实现Comparable及其父类也能参与比较比较时用compareTo(...) 0而不是 0这样才能保证同成绩对象的相对顺序不被改变。第二个细节是关于空值的处理。泛型数组里可能出现null直接用arr[j].compareTo会抛空指针。你可以在排序前把null统一放到数组末尾或者在比较逻辑里做空值兜底。这是很多人写手写排序时会忽略的坑尤其当你处理外部传入的数据时。第三个细节是性能测试的方法。如果你要验证优化效果千万不要在交互式环境里随便跑几个小数组就下结论。我建议至少用一万到十万数量级的数组分别准备“已排序”“逆序”“随机”三组数据然后用System.nanoTime()测量排序耗时。注意 JVM 有预热机制第一轮运行结果往往偏慢建议先跑若干次再取平均值。我自己在实际项目里用过冒泡排序的场景已经很少但只要满足“小数据、近乎有序、需要稳定、不想引依赖”这几个条件它仍然是我第一个想到的算法。我甚至更喜欢在代码注释里把“为什么这里不用快速排序”写清楚因为这类基础算法的选型逻辑对后来维护代码的人同样是重要的信息。最后分享一个我个人的习惯每当有人让我“写个排序”我不会马上动手而是先反问三个问题——数据规模多大是不是要求稳定能不能用 JDK 自带的排序这三个问题问完很多所谓的“排序难题”就已经不是难题了。冒泡排序作为一种基本功它能帮我们理解比较、交换、边界、稳定性这些底层概念。但真正带到工程里的不是某一段代码而是你在动手之前对场景的判断。