★ FEATURED ARTICLE 冒泡排序大概是所有排序算法里名声最大、实际用途最小、但面试出现频率又最高的一个。很多人学 Java 的第一段排序代码就是它学完立刻觉得这有什么好学的然后转头去刷快速排序和归并排序。但如果你真把冒泡排序吃透会发现它其实是理解排序算法最好的起点——它不依赖任何高级数据结构也不涉及分治、递归这类抽象思想纯粹靠相邻元素两两比较、按需交换这一条规则就把排序这件事的核心逻辑讲清楚了。这篇文章我打算从零开始把这个排序算法彻底拆开揉碎。不管是完全没写过 Java 的初学者还是已经工作几年但没系统梳理过排序细节的人都能在这里找到有用的东西。我会把原理、Java 实现、两种常见优化、复杂度数学账、边界情况和面试题全部过一遍内容比较长建议收藏后慢慢看。1. 冒泡排序在解决什么问题相邻交换背后的直觉1.1 从生活场景理解冒泡的本质先别急着看代码。我每次给别人讲冒泡排序都会先说一个场景想象一班人排队教官要求按身高从矮到高站好但只允许相邻两个人互相比较、位置不对就交换。这个规则下最直观的做法是什么从队伍最前面开始依次比较相邻两个人如果前面的人比后面的人高就让他们换位置。走完一整轮之后最高的人一定被挤到了队伍最后面。接着再来一轮第二高的人会被挤到倒数第二位。如此反复队伍就排好了。这个过程就像水里的气泡往上浮——大的元素慢慢往后移动每一轮都会有一个当前范围内的最大元素冒到它应该在的位置。冒泡排序的名字就是这么来的。理解这个场景非常关键因为后续所有代码、所有优化、所有边界条件都建立在这条规则之上每一轮只负责把一个最大值送到它该待的位置。这一点想通了后面看代码就不会晕。1.2 一次完整流程示例把最大值浮到末尾用一个具体例子走一遍。假设数组是[5, 1, 4, 2, 8]现在要从小到大排序。第一轮从头开始比较比较 5 和 15 1交换数组变成[1, 5, 4, 2, 8]比较 5 和 45 4交换数组变成[1, 4, 5, 2, 8]比较 5 和 25 2交换数组变成[1, 4, 2, 5, 8]比较 5 和 85 8不交换数组保持[1, 4, 2, 5, 8]第一轮结束最大值 8 已经到末尾了。注意看其实这一轮里 1 也被交换到了更靠前的位置但这个属于附带效果不是本轮的核心目标。第二轮继续从头开始但最后一个位置已经确定是 8不需要再比较它了所以第二轮只需要处理前四个元素[1, 4, 2, 5]比较 1 和 4不交换比较 4 和 24 2交换变成[1, 2, 4, 5]比较 4 和 5不交换第二轮结束5 到了倒数第二的位置。第三轮处理前三个元素把 4 送到倒数第三的位置。第四轮处理前两个元素把 2 送到正确位置。五个元素只需要四轮每轮都能确定一个最大值。1.3 为什么叫冒泡排序而不是沉底排序这是很多人没想过的问题。从上面流程看大元素确实在往下沉看起来更像沉底排序。但冒泡这个名字强调的是过程不是结果。相邻交换的过程中大元素会像气泡一样一格一格往上冒过其他元素每一轮扫描就像气泡不断上升最终冒出水面。小元素相对轻可能会被带着向前移动也就是所谓前移。记住这个视角有个实际作用当你调试代码时如果看到某个大元素没有逐格移动大概率是交换逻辑写错了。冒泡排序的交换永远是相邻交换任何一次跳过中间元素的交换操作都不该出现在这个算法里。2. Java第一版实现从伪代码到可运行代码2.1 两层循环结构拆解明确了流程写代码就顺理成章了。外部循环控制需要几轮内部循环控制每一轮比较到哪里。这里有三个关键点初学者最容易栽跟头我一个个说。第一外层循环的次数。假如数组长度是n最坏情况下需要n - 1轮。为什么不是n轮因为每轮都会确定一个最大值的位置当有n - 1个元素都到了正确位置剩下那一个自然也在正确位置了。所以外层循环i从 0 到n - 2也就是i n - 1。第二内层循环的范围。第i轮开始之前数组末尾已经有i个元素是确定的所以这一轮只需要比较到n - 1 - i的位置。用代码说就是j n - 1 - i。第三比较方式。当前元素arr[j]和下一个元素arr[j1]比较如果前者大于后者就交换这样升序排列。这里用而不是原因后面讲稳定性的部分会详细说先记住结论相等元素不该交换。2.2 完整代码与swap细节最基础版本的 Java 实现如下public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) { return; } 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]) { swap(arr, j, j 1); } } } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; }关于swap方法提醒一句如果你在面试现场写代码优先用临时变量法就是上面这个。不要写arr[i] arr[i] ^ arr[j]; arr[j] arr[i] ^ arr[j]; arr[i] arr[i] ^ arr[j];这种异或交换。虽然它能省一个临时变量但代码可读性差而且如果i和j指向同一个位置异或交换会把数组元素变成 0是典型的面试炫技翻车写法。我在实际帮人排查代码时见过好几次这种问题老老实实用临时变量最稳妥。开头那个判空逻辑也不是形式主义。arr null如果不检查下一行arr.length直接空指针异常length 2时不检查数组只有一个元素也会进入循环虽然不会报错但完全没有意义。防御式编程应该成为肌肉记忆。2.3 边界条件为什么是 length-1-i这段是给真正想搞懂的人看的。很多文章只给结论不给推导过程导致初学者背了一堆边界条件一换题目就懵。这里我推导一遍。数组长度为n有效下标范围是0到n-1。第i轮i从 0 开始数结束时数组最后i 1个位置已经确定了最大值序列。所以这一轮中最后一个需要参与比较的下标是n - 1 - i。而我们每次要比较arr[j]和arr[j 1]所以j最大只能取到n - 2 - i也就是代码里j n - 1 - i的原因。打个比方每轮结束后数组末尾被占领的区域越来越大前面待排序的区域越来越小。内层循环的作用范围就是当前还没有被占领的前半段区域。把这条推导记住以后写任何排序的边界条件都不会犯迷糊。3. 带着标志位优化提前发现有序数组3.1 场景触发几乎排好的数组浪费时间基础版本跑通之后就该想优化问题了。最典型的一个场景数组[1, 2, 3, 4, 5]已经是有序的了。基础版会怎么办它依然会老老实实跑完n - 1轮每轮内部把所有相邻元素比较一遍总共比较n(n-1)/2次。但这些比较完全没有意义——数组本来就有序没有任何交换发生。有次我给某段业务代码做性能分析发现一个数据量不大但被频繁调用的方法里冒泡排序每次都要完整跑完。那个数据集恰好大部分时候都是接近有序的浪费的时间非常可观。针对这种场景一个标志位就能解决问题。3.2 swapped标志位的实现优化思路特别简单每一轮开始时设一个布尔变量swapped标记本轮是否发生过交换。如果一轮扫描下来一次交换都没有说明数组已经有序直接跳出循环。public static void bubbleSortOptimized(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); swapped true; } } if (!swapped) { break; } } }这个标志位放在外层循环内部、内层循环之前每轮开始都重置为false。一旦发生交换就置为true。内层循环结束后检查如果还是false说明这一轮所有相邻元素都不需要交换数组已经全部有序后面几轮完全没必要继续跑。这个优化的价值在没有增加额外空间和复杂度的前提下把完全有序数组这类最好情况的时间复杂度从 O(n²) 降到了 O(n)。一个for循环从头扫到尾发现没交换直接结束只做了一次比较效率提升是数量级的。3.3 优化后的最好时间复杂度变成了 O(n)这里值得把复杂度分析单独拿出来说。基础版不管数组是否有序都不能提前结束所以最好、最坏、平均情况都是 O(n²)。加了标志位之后最好情况变成了数组本来就完全有序的场景外层循环第一轮内层从头扫到尾n-1次比较一次交换都没发生swapped一直是false直接break。总比较次数约n次所以时间复杂度是 O(n)。比较次数和交换次数要分开算。最好情况下比较次数是n-1交换次数是 0最坏情况下数组完全逆序比较次数是n(n-1)/2交换次数同样是n(n-1)/2因为每次比较都满足交换条件。但要注意这个优化并没有改变最坏情况的复杂度。真正完全逆序的数组每一轮都有交换发生swapped每轮都是true循环照样要跑满n-1轮。标志位只是让算法在面对有序、近似有序数据时变聪明了而不是让最坏情况变好。4. 进阶优化记录最后一次交换位置缩小扫描区间4.1 标志位没解决的无意义比较标志位优化解决了数组已经有序的问题但还有一个隐蔽的浪费没解决。看这个例子[1, 5, 6, 7, 8, 2]经过第一轮冒泡8 会跑到末尾数组变成[1, 5, 6, 7, 2, 8]。第二轮扫描到末尾前的区域这时 2 会一路向左交换直到遇到 1。第二轮实际发生交换的位置大概在前四个位置。问题来了第三轮、第四轮如果还用j n - 1 - i这个边界会把前几轮已经确定有序的尾部区域也重新比较一遍。虽然这部分区域确实被确定了但其中有些元素的相邻关系很早之前就已经稳定比较它们纯属浪费。更典型的是这个数组[3, 4, 5, 6, 7, 1]。第一轮结束后7 到末尾但 1 还在最前面剩下的区域基本整个都需要继续处理。可如果数组是[1, 2, 3, 4, 5, 0]这种第一轮结束后 5 到末尾第二轮扫描中0 会一路交换穿过整个数组最后一次交换发生在起始位置附近。这意味着第二轮之后数组其实已经有序了但标志位要到第三轮才能发现——因为第二轮本身发生了交换。思路就来了如果某一轮的交换只发生在前半段那后半段肯定已经有序下一轮根本不需要比较到n-1-i只需要比较到这一轮最后一次交换发生的位置就行。4.2 实现思路与代码用一个变量记录本轮最后一次交换发生在哪个下标。下一轮的内层循环只需要跑到这个下标为止因为在这个下标之后的所有元素本轮一次交换都没参与显然已经有序。public static void bubbleSortOptimized2(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; int lastSwapIndex n - 1; while (lastSwapIndex 0) { int currentSwapIndex 0; for (int j 0; j lastSwapIndex; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); currentSwapIndex j; } } lastSwapIndex currentSwapIndex; } }这里的关键是currentSwapIndex j而不是j 1。因为最后一次交换发生在位置j和j1之间交换完成后j1位置放入的是这一轮的最大值它的位置已经确定。但j位置不一定确定下一轮需要继续从0扫到j。所以把j记录为下一轮的上界。举个例子[1, 2, 4, 3, 5]第一轮中只有4和3发生了交换最后一次交换发生在j 2的位置currentSwapIndex记为 2。下一轮lastSwapIndex 2内层循环只需要比较j 0, 1两个位置。此时[1, 2, 3, 4, 5]已经有序第二轮一次交换都没有currentSwapIndex保持 0lastSwapIndex变为 0循环结束。注意一个细节currentSwapIndex每轮都要重置为 0。如果不重置上一轮的旧值会被带到下一轮导致上界判断错误。我见过不少人在这个细节上翻车写出来代码逻辑看着对一跑就死循环或者漏排。4.3 对比两版优化的实际效果两个优化从不同维度减少工作量swapped标志位解决的是是否还需要继续的问题lastSwapIndex解决的是每次扫到哪里才够的问题。实际场景中两者可以合并使用但要理清各自的作用边界。拿一个接近有序但尾部有个小元素乱入的数组测试就能看出差异。比如[2, 3, 4, 5, 6, 1]第一轮 6 到末尾1 移动到第二个位置第二轮 5 到倒数第二1 移动到第三个位置第三轮 4 到倒数第三1 移动到第四个位置第四轮 3 到倒数第四1 移动到第五个位置第五轮 2 和 1 交换整个数组有序。标志位方案要跑满 5 轮而lastSwapIndex方案第二轮上界就缩减到了 1很快就结束。两者对比的差距肉眼可见。不过话说回来数据量小的时候这些优化带来的绝对时间差异几乎感受不到。真正的价值在于让你理解排序算法的瓶颈在哪这个思维方式会在你以后理解快速排序、归并排序时派上用场。5. 复杂度与稳定性冒泡排序的数学账5.1 比较次数和交换次数怎么算复杂度是算法的体检报告冒泡排序这份报告要能读懂数据才算过关。最坏情况下数组完全逆序比如[5, 4, 3, 2, 1]。第一轮比较 4 次交换 4 次第二轮比较 3 次交换 3 次以此类推。总的比较次数是4 3 2 1 10也就是n(n-1)/2。交换次数同样是n(n-1)/2。所以最坏情况时间复杂度和平均情况都是 O(n²)。最好情况刚才说过是数组完全有序用标志位优化之后比较次数约n-1交换 0 次O(n)。空间复杂度方面只有临时变量temp和几个循环变量是 O(1) 原地排序不占用额外空间。这里有个容易混淆的点n(n-1)/2和 O(n²) 的关系。前者是精确的计算公式后者是渐进复杂度描述。常数和低阶项在复杂度分析里会被忽略但当你想比较两个 O(n²) 的算法谁更快时精确公式就有意义了。5.2 稳定性分析为什么用 而不是 稳定性是面试经常问的考点。先解释概念如果数组中有两个相等的元素排序后它们的相对顺序没有改变这个排序算法就是稳定的。比如数组[3a, 2, 3b, 1]用3a和3b区分两个值相等的 3排序后3a仍然在3b前面就说明算法稳定。冒泡排序天然稳定前提是代码里用而不是。当arr[j] arr[j1]时判断为false不进行交换相等元素保持原有相对顺序。如果写成相等元素也会交换位置排序后相对顺序被反转算法就变得不稳定了。这两个操作符的区别在基础排序算法里是判断稳定性的分水岭。面试的时候能主动提一句我用就是为了保持稳定性会比其他候选人显得更有章法。后来我在系统设计里给复杂对象排序时这个特性反而成了选型优势——如果需要多关键字排序稳定排序可以通过多次关键字排序实现每次排序都不破坏上一次的顺序这是不稳定排序做不到的。5.3 适用场景讨论什么情况下才值得用它老实说冒泡排序在生产环境里几乎没有用武之地。任何数据量稍微大一点的场景O(n²) 的复杂度都是灾难。一次排序一万个元素冒泡排序要做大约五千万次比较快速排序大概只需要十几万次差距是几百倍。但有几个边角料场景它还能发挥作用。数据量极小比如排几十个元素且代码要极简时冒泡排序的代码量最少几乎没有出错空间。几乎有序的数组配合优化版实际运行效率非常高因为它能提前退出。还有内存极度受限的嵌入式环境O(1) 空间的优势会凸显出来。除此之外工程上我更倾向于用Arrays.sort或者自己实现快速排序、归并排序。所以纠结冒泡排序有没有实际用途没有太大意义。它的价值是教学层面的——这是最直观、最容易验证正确性的排序算法是理解复杂度分析、稳定性、优化思路的最佳载体。把冒泡排序吃透再去学其他排序算法会发现很多概念是相通的。6. 变体与边界鸡尾酒排序、空数组和相等元素6.1 鸡尾酒排序双向冒泡解决小值在最后的尴尬冒泡排序有个明显短板如果最小的元素恰好在数组最末尾它要经过每一轮扫描才能一格一格往前挪效率特别低。比如[2, 3, 4, 5, 1]1在第一轮从末尾挪到第四个位置第二轮挪到第三个位置依次类推要整整四轮才能到最前面。为了解决这个问题有人提出了双向冒泡也叫鸡尾酒排序。思路是一轮从左往右扫把最大值送到右边下一轮从右往左扫把最小值送到左边。这样交替进行两个方向的大元素和小元素都能快速归位。public static void cocktailSort(int[] arr) { if (arr null || arr.length 2) { return; } int left 0; int right arr.length - 1; while (left right) { boolean swapped false; for (int i left; i right; i) { if (arr[i] arr[i 1]) { swap(arr, i, i 1); swapped true; } } right--; for (int i right; i left; i--) { if (arr[i] arr[i - 1]) { swap(arr, i, i - 1); swapped true; } } left; if (!swapped) { break; } } }鸡尾酒排序在元素已经基本有序、只有少量元素位置不对时效果显著但复杂度和冒泡排序一样是 O(n²)最坏情况没有本质改善。面试中能写出来是加分项但工作中一般没人用它。6.2 边界情况与防御式编程写排序算法边界情况是检验代码完整性的试金石。空数组[]、单元素数组[5]、两个元素数组[2, 1]、含重复元素的数组[1, 3, 3, 2]、完全有序数组、完全逆序数组每一个都应该跑一遍。最开始那个判空逻辑就覆盖了null和长度小于 2 的情况。单元素数组不需要排序直接返回含重复元素时用保证稳定性完全有序数组在优化版下能提前退出。这些情况看着琐碎但写成工具方法时缺一个都可能线上出 bug。有次我看到别人封装的排序工具直接拿arr.length算循环边界忘了空数组的可能结果调用方传了个空数组进来控制台刷了一屏越界异常。防御式编程的思路很简单方法开头先处理不需要干活的情况所有参数非法的情况都挡在门口主逻辑只管自己该管的。这个习惯在写任何算法和方法时都适用。7. 手写代码时最容易踩的坑实战经验与推荐写法7.1 两种常见的越界写法面试手写排序最容易翻车的场景是内层循环边界写错。一个典型错误是写成j n - i外层i 0时j最大取到n - 1此时访问arr[j 1]就是arr[n]直接越界。另一个典型错误是把j的初始值设成1写成for (int j 1; j n - i; j)比较arr[j-1]和arr[j]。这样写逻辑上也能跑通但和常规写法相比考虑的事情更多容易出现下标错位。我建议初学者统一用arr[j]和arr[j1]这对搭配配合j n - 1 - i思路最顺。还有一个隐蔽的坑外层循环写了i n - 1。这会导致多跑一轮虽然不会越界但完全是无效劳动。养成写i n - 1的习惯从 0 开始编号的循环上界一般是n - 1。7.2 面试中的追问与加分项面试官让你手写冒泡排序通常不会只是为了看你背代码。写完基础版之后常见的追问依次是这个算法最好情况复杂度是多少怎么优化稳定性如何怎么让代码更简洁基础版最好情况是 O(n²)这是很多人的第一个知识盲区。如果能主动写出带swapped标志位的优化版然后解释为什么最好情况变成 O(n)这个回答基本就算过关了。如果再能提到lastSwapIndex、鸡尾酒排序说明你不是背的是真懂。还有一个加分细节写完代码后主动说一句我把写成严格大于而不是大于等于是为了保持稳定性。这句话不费什么力气但在面试官眼里代表你理解这个算法的本质而不是只会默写。7.3 我实际使用中更推荐的合并优化写法单独用swapped或单独用lastSwapIndex都有对应的浪费场景。日常写工具类或面试手写时我更喜欢把两者合并兼顾提前退出和缩减扫描范围两个效果public static void bubbleSortFinal(int[] arr) { if (arr null || arr.length 2) { return; } int lastSwapIndex arr.length - 1; while (lastSwapIndex 0) { int currentSwapIndex 0; boolean swapped false; for (int j 0; j lastSwapIndex; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); currentSwapIndex j; swapped true; } } if (!swapped) { break; } lastSwapIndex currentSwapIndex; } }这个版本既不浪费比较次数也能在完全有序时提前结束。代码量也就多了几行可读性依然很好。有读者可能会问swapped和currentSwapIndex是不是冗余如果currentSwapIndex 0说明这一轮最后也没交换那下一次lastSwapIndex就变成 0while条件自然退出swapped其实可以省掉。但加了swapped的检查能让完全有序时少一次无意义的空循环判断逻辑也更直观面试时解释起来不费劲。最后分享一个我自己常用的验证方法写一个随机测试方法每次生成几百个随机数用Arrays.sort的结果和冒泡排序的结果做对比确认排序结果完全一致再交付。这个方法虽然简单却能挡住所有边界错误。你在学习或开发时也建议把用标准实现验证自己的实现当成一个固定动作。冒泡排序本身很简单但它的价值绝不止于代码本身。理解了它你就理解了排序领域的几个最基本概念相邻交换、稳定性、原地排序、最好与最坏情况复杂度、优化如何改变复杂度。这些概念往后的每一个排序算法里都会反复出现。把这些基础打牢再学其他的你会觉得顺滑很多。
阅读完成 · 觉得有帮助？
