“请你当场写一段冒泡排序。”——这是我做技术面试时经常问的第一道算法题。让我意外的是，真正能在纸上把冒泡排序写对、写清楚的人，比想象中少得多。不少人一上来就写两层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 自带的排序？这三个问题问完，很多所谓的“排序难题”就已经不是难题了。冒泡排序作为一种基本功，它能帮我们理解比较、交换、边界、稳定性这些底层概念。但真正带到工程里的，不是某一段代码，而是你在动手之前对场景的判断。
