翻编程书的时候排序算法往往排在很前面而冒泡排序基本都是第一个出场的。很多教程把它当成热身操一笔带过面试官也爱拿它当签到题。但你要是真以为它简单到没东西可讲那就错了。我见过不少工作两三年的同事临时被要求手写冒泡排序照样写错循环边界、忘了优化标志位甚至把稳定性说反。这篇文章我就把自己对冒泡排序的理解、四种常见语言的写法、优化思路和踩坑记录都整理出来。新手可以把它当入门教程老手也可以对照看看有没有漏掉细节。1. 冒泡排序的核心思想先把原理彻底搞懂1.1 名字的由来与算法的整体气质冒泡排序这个名字起得非常形象。你把一个数组竖起来看越大的元素越重它就会像水里的气泡一样一路往上浮最终到达属于它的位置。这个过程不断重复所有元素就按从下到上、从小到大的顺序排好了。算法本身的逻辑只需要一句话从头到尾扫描序列相邻两个元素两两比较如果顺序不对就交换位置。每一趟扫描都会把一个当前最大或最小的元素送到它最终该在的位置就像水面上冒出一个气泡。等所有气泡都冒完了排序也就完成了。这套逻辑决定了冒泡排序的几个先天特征实现极其简单代码量少不需要额外申请大块内存而且是稳定的排序算法。缺点也显而易见——慢。数据量一上来它和快排、归并这种 O(n log n) 级别的排序算法差距会非常明显。所以现实中很少用它来排大数据集更多是作为教学入门、面试热身或者处理那种只有十几个元素的超小规模数据。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不交换第一趟结束时最大的 8 已经落在了最后一位这就是冒出来的第一个气泡。注意这一趟总共比较了 4 次也就是 n-1 次。第二趟开始时因为 8 已经是最后一个元素了不需要再参与比较只需要处理前 4 个元素比较 1 和 4不交换比较 4 和 24 2交换数组变为 [1, 2, 4, 5, 8]比较 4 和 5不交换第二趟结束时第二大的 5 落到了倒数第二位。比较次数是 3 次。第三趟对前 3 个元素比较 2 次第四趟对前 2 个元素比较 1 次。四趟跑完整个数组有序。五元素的数组总共比较 4 3 2 1 10 次。从这个流程能看出一个规律每完成一趟就会多一个元素在最终位置下一趟需要处理的范围就缩短一个。这正是两层循环的由来。1.3 两层循环各自的职责冒泡排序的代码骨架无论用什么语言写都是两层循环加一个 if 交换。外层循环控制的是“要跑几趟”。n 个元素最多需要 n-1 趟因为每趟确定一个元素的位置确定 n-1 个之后剩下的最后一个元素自然就归位了。有没有可能提前结束有可能。如果某一趟从头扫到尾一次交换都没发生说明所有元素都已经按序排列可以提前退出。这就是后面要讲的优化点。内层循环控制的是“这一趟比较哪些相邻对”。第 i 趟从0开始计数开始时数组末尾已经有 i 个元素是排好的所以只需要比较前 n-1-i 对相邻元素。写成循环条件就是 j n - 1 - i对应比较 arr[j] 和 arr[j1]。这里最常翻车的就是边界条件。很多人第一次写会写成 j n结果 arr[j1] 直接越界程序崩溃或者出现未定义行为。也有人写成 j n - i看起来好像没问题但 i 0 时 j 最多取到 n-2j1 n-1 还没越界不对让我重新算一下j n - i 时j 的取值是 0 到 n-i-1j1 最大是 n-i。当 i0 时j1 最大是 n就越界了。所以必须是 n-i-1 或者写成 n-1-i差一个 1 就是天堂和地狱的区别。2. 四种语言的落地实现与代码逐行拆解2.1 C语言版最贴近内存本质的写法C语言的写法最朴素也最能体现数组和内存操作的本质。直接看代码#include stdio.h void bubble_sort(int arr[], int n) { 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; } } } } int main() { int arr[] {5, 1, 4, 2, 8}; int n (int)(sizeof(arr) / sizeof(arr[0])); bubble_sort(arr, n); for (int k 0; k n; k) printf(%d , arr[k]); return 0; }几个关键点值得说道说道。第一C语言中数组作为函数参数传递时会退化为指针。所以在函数内用 sizeof(arr) / sizeof(arr[0]) 是拿不到数组长度的——sizeof(arr) 得到的只是一个指针的大小。正确做法是在调用前用 sizeof 算出元素个数作为单独参数传进去。main 函数里那句sizeof(arr) / sizeof(arr[0])是安全的因为这时候 arr 还是真正的数组。第二交换三个数用临时变量 temp 承接这是最原始也最稳的写法。有些同学喜欢用异或交换的骚操作arr[j] ^ arr[j1]; arr[j1] ^ arr[j]; arr[j] ^ arr[j1]省一个临时变量。但除非你对位运算极度熟悉否则我不推荐可读性差而且如果两个值恰好是同一块内存这里不可能发生但其他场景可能异或交换会直接把数据清零。第三外层循环是 i n-1不是 i n。因为 i 表示已经确定好的元素个数最多 n-1 趟。写多了没意义还会白白多做无用功。2.2 C版模板化与标志位优化C 版本我会写得稍微讲究一点用模板支持不同类型的容器同时把标志位优化直接包含进去。#include iostream #include vector #include algorithm template typename T void bubble_sort(std::vectorT arr) { size_t n arr.size(); if (n 2) return; for (size_t i 0; i 1 n; i) { bool swapped false; for (size_t j 0; j 1 n - i; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; } } int main() { std::vectorint arr {5, 1, 4, 2, 8}; bubble_sort(arr); for (int v : arr) std::cout v ; return 0; }为什么用 vector 而不是普通数组一是自动管理长度不需要单独传 n二是模板函数能轻松支持不同类型的 vector后面想排 double、string 都可以直接复用。这里有个边界细节内层循环条件我写的是j 1 n - i等价于j n - i - 1。在 size_t 这种无符号类型下写成 j 1 再比较的好处是避免 n - i - 1 在极端情况下变成负数。当 i 接近 n 的时候n - i - 1 理论上还是大于等于 0 的但代码可读性更好也不会触发无符号数下溢的隐患。标志位 swapped 是第一个优化点。每趟开始前把它置为 false只要这趟发生过交换就置为 true。趟结束时如果 swapped 还是 false说明数组已经有序直接跳出外层循环。天然有序的数组第一趟只要比较 n-1 次就能确认有序并退出复杂度从 O(n²) 直接降到 O(n)。2.3 Java版泛型、Comparable 与封装Java 的写法会更“重”一些因为要处理泛型和比较器的问题。import java.util.Arrays; public class BubbleSort { public static T extends Comparable? super T void bubbleSort(T[] arr) { 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].compareTo(arr[j 1]) 0) { T temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } if (!swapped) { break; } } } public static void main(String[] args) { Integer[] arr {5, 1, 4, 2, 8}; bubbleSort(arr); System.out.println(Arrays.toString(arr)); } }泛型边界T extends Comparable? super T这串东西看起来吓人其实表达的是T 类型必须实现了 Comparable 接口并且该接口允许比较 T 的父类型。这样不管是 Integer 还是自定义实现了 Comparable 的类都能传入。如果只是写T extends ComparableT有些继承体系比较复杂的类会传不进来。容易踩的坑在 main 方法里我声明的是 Integer[]而不是 int[]。因为 Java 的泛型只支持引用类型不支持基本类型。你如果传 int[] 进来编译器直接报错没有任何回旋余地。解决办法要么是把 int[] 改成 Integer[]要么单独写一个处理 int[] 的重载方法后者可以用 Arrays.sort 内部同款手动装箱思路但没必要排序前装箱成本并不高。2.4 Python版简洁背后要留神的地方Python 版本看着最爽五行核心代码就能搞定但有两个隐藏细节值得注意。def bubble_sort(arr): n len(arr) if n 2: return arr for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr data [5, 1, 4, 2, 8] bubble_sort(data) print(data)第一个细节是交换写法。Python 里arr[j], arr[j 1] arr[j 1], arr[j]是元组解包赋值等号右侧会先计算出一个临时元组再按顺序解包赋给左侧两个变量。这个操作是安全的不需要临时变量也不是异或那种花活。但如果你拆开写成两步arr[j] arr[j 1]再arr[j 1] arr[j]那就坏了第一个赋值直接把 arr[j] 覆盖成 arr[j1]第二个赋值等于把同一个值又写回去数据直接丢了。我曾经见过新手在这上面卡了半小时。第二个细节是原地修改与返回值。Python 的列表是引用传递函数内修改 arr 的元素外面的列表同样会变。我这个函数最后还 return arr看起来像是返回了一个新列表实际上返回的还是同一个对象的引用。这样写的好处是方便链式调用比如result bubble_sort(data)两边都能看到排序结果。但如果你误写成arr sorted(arr)那函数内部只是让局部变量指向了一个新列表外部原列表纹丝不动。这两种行为差别很大写库函数的时候一定要在文档里说清楚。3. 复杂度、稳定性与优化把冒泡的老底掀开3.1 时间复杂度到底怎么推出来的很多人背结论说冒泡排序时间复杂度是 O(n²)但问为什么就说不清了。其实推导非常直观n 个元素的数组第一趟比较 n-1 次第二趟 n-2 次第三趟 n-3 次一直到第 n-1 趟比较 1 次。总的比较次数是(n-1) (n-2) ... 1 n(n-1)/2这是一个经典的等差数列求和公式。结果展开是 n²/2 - n/2取最高阶项并去掉常数系数就是 O(n²)。交换次数在最坏情况下和比较次数同量级。数组完全逆序的时候每一对相邻元素都需要交换交换次数也是 n(n-1)/2。在大 O 记号下比较和交换合并思考整体时间复杂度就是 O(n²)。但这里有个容易让人忽略的点加了标志位优化之后最好情况的时间复杂度是 O(n)。比如输入一个已经有序的数组第一趟扫描 n-1 次发现一次交换都没有立刻退出循环总操作次数是 O(n)。平均情况仍然是 O(n²)因为随机排列的数组大约有一半的相邻对需要交换比较次数始终跑满。空间复杂度是 O(1)因为所有的交换都在原数组上进行没有额外申请与 n 相关的内存。这一点在嵌入式、单片机这类内存紧张的环境里是个不小的优势。3.2 稳定性是什么意思为什么冒泡是稳定的稳定性说的是如果数组里有两个值相等的元素排序之后它们原本的相对顺序能不能保持。能保持就叫稳定排序不能保持就叫不稳定排序。这个性质在有些场景中非常重要。比如一个学生列表先按班级排好再按成绩排。如果排序算法是稳定的第二次按成绩排完之后同分的同学仍然保持着班级顺序如果算法不稳定同分的同学班级顺序可能就乱了。数据库的 ORDER BY 多字段排序、基数排序的底层都依赖稳定排序。冒泡排序为什么稳定因为我们的比较条件是arr[j] arr[j1]只有前一个比后一个大才交换。两个相等的元素相遇时这个条件不成立不会交换。相等元素在排序过程中最多相互错身一次之后就保持相对顺序锁定了。对比选择排序就能立刻看出差别选择排序每趟找到最小值然后和前面元素交换如果这个最小值前面有和它相等的元素交换之后这些相等元素的相对顺序就可能被破坏所以选择排序不稳定。3.3 两个实用优化标志位和记录最后交换位置标志位优化刚才已经提过核心就是在每趟循环里记一个 swapped没有交换就提前退出。这是冒泡排序最基础、最该默认开启的优化几乎零成本。第二个优化更有意思记录每一趟最后发生交换的位置。原理是某对元素最后一次发生交换的位置在 index那么 index 之后的所有元素在上一趟已经在正确位置不需要再参与了。下一趟只需要扫描到 last_swap 这个位置就行。这个优化对“大部分有序只有开头一小段乱序”的数组特别有效。直接看 Python 实现def bubble_sort_v2(arr): n len(arr) end n - 1 while end 0: last_swap 0 for j in range(end): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] last_swap j end last_swap return arr注意这个版本天然包含了标志位优化的效果。如果某一趟没有任何交换last_swap 保持为 0end 被赋值为 0while 条件不成立循环直接结束。不用再额外写一个布尔标志代码反而更简洁。还有一个进阶版本叫鸡尾酒排序本质是双向冒泡先从左往右把最大值沉到末尾再从右往左把最小值浮到开头如此反复。对大部分元素已经有序、只有中间一段乱序的数组鸡尾酒排序比标准冒泡排序快不少。但代码复杂度也上来了实际收益有限面试里能口头说出来就足够展示对算法的理解了。4. 实战翻车现场边界条件与常见问题排查4.1 循环边界错一位翻车现场第一名冒泡排序写不对十有八九是循环边界问题。我总结过几种典型错误。错误一内层循环写成 j n - i。前面推过i 等于 0 时j 最大取到 n-i-1也就是 n-1不对如果条件是 j n - ij 最大是 n - i - 1那 j1 最大是 n - i。当 i 0 时j1 n越界访问数组最后一个下标之外的内存。C 语言里不会直接报错但读出来的可能是垃圾值然后写入垃圾值数组被搞乱Java、Python 里会直接抛 ArrayIndexOutOfBoundsException 或 IndexError。错误二外层循环写成 i n - 1多跑一趟。这个错误不会导致崩溃但会增加无用的比较次数。尤其没有标志位优化的时候多跑一趟等于多出 n 次无意义的比较数据量大点就明显变慢。错误三交换逻辑写反把大的往前放。这个属于理解了升序降序但代码没走心跑一次测试就能发现。建议写完排序后先用倒序数组测试如果输出不是升序立刻能定位到方向问题。我自己摸索出来的排查习惯是测试用例至少准备五组——空数组、单元素数组、已经有序数组、完全逆序数组、有大量重复值的数组。前两种专门测边界后三种分别验证最坏情况、最好情况和稳定性。这五组跑完排序函数的正确性基本能放心。4.2 sizeof、泛型与基本类型数组三个语言层面的坑C 语言里最隐蔽的坑是 sizeof 陷阱。新手写了一个void bubble_sort(int arr[])然后在函数体里写int n sizeof(arr) / sizeof(arr[0])期望算出数组长度得到的却是一个完全错误的值。原因在于函数参数列表中数组类型会被调整成指针类型sizeof(arr)拿到的是指针的大小32 位系统是 464 位系统是 8再除以 int 的大小 4n 要么是 1 要么是 2。解决办法前面已经说了在 main 里算好长度传进去这是 C 语言最朴实也最常见的做法。C 版本如果直接拿模板函数处理普通数组也会遇到问题。比如int arr[] {5,1,4,2,8}; bubble_sort(arr);我的模板签名是bubble_sort(std::vectorT)这里类型不匹配编译不过。如果确实需要支持普通数组模板签名要改为接受数组引用template typename T, size_t N void bubble_sort(T (arr)[N])这时 N 是编译期推断出来的天然正确。但这种写法不灵活普通数组和 vector 的 API 也不一样所以我一般只对 vector 提供模板版本普通数组用 C 语言风格写一个单独处理。Java 的坑在前面提过泛型方法不能直接接收 int[]必须用 Integer[]。很多初学者在 main 里写int[] arr {...}; bubbleSort(arr);编译报错然后怀疑是泛型写错了其实不是。原因是 int 是基本类型不能作为泛型类型参数。如果想排 int[]要么包装成 Integer[]要么写一个public static void bubbleSort(int[] arr)的重载版本后者在性能敏感的场合反而更好因为省掉了装箱开销。Java 标准库的 Arrays.sort 就是这样为所有基本类型都提供了重载。4.3 面试中围绕冒泡排序最常被追问的问题面试官让你写冒泡排序往往不只是看看你能不能背出代码还会顺藤摸瓜问几个延伸问题。我整理了出现频率比较高的四个。第一个冒泡排序稳定吗为什么答案前面已经说清楚关键是比较条件用 而不是 相等不交换相对顺序才能保持。第二个能不能把时间复杂度优化到 O(n log n)这个问题问的是你对排序算法天花板的认知。纯冒泡排序做不到比较排序的下界就是 O(n log n)。但可以让冒泡排序在某些特定输入下退化为 O(n)这就是标志位优化的价值。如果输入完全有序优化版直接检测到无交换一趟完成。第三个冒泡排序和插入排序实际谁更快这是个很有价值的延伸问题。两者最坏情况都是 O(n²)最好情况都是 O(n)但插入排序的常数更小因为它在数据基本有序时每趟几乎不需要移动元素。实测下来对一万个接近有序的随机数插入排序可能比冒泡快五到十倍。所以真实项目中如果要手写排序优先选插入排序而不是冒泡。第四个冒泡排序适合用在哪些场景总结下来就三类数据量极小比如十几个元素、数组几乎有序且期望稳定、教学或者面试用于理解算法基础。除此以外真实生产环境直接用标准库的排序函数C 的 std::sort、Java 的 Arrays.sort、Python 的 list.sort 都是经过深度优化的工业级实现远比自己手写冒泡可靠。5. 写冒泡排序这么多年我最想提醒你的几件事5.1 新手写完后的自测清单我不知道别人怎么带新人的但我带人的时候要求写排序类代码必须过一遍自测清单。这份清单不是给别人看的是给自己养成习惯的。第一空数组测试。很多算法一上来处理空数组就会越界比如直接访问 arr[0]。我的版本里先判断 n 2 直接返回就是为了规避这类问题。第二单元素数组。第三有序数组验证标志位优化能不能提前退出。第四逆序数组验证最坏情况下的正确性。第五重复元素数组验证稳定性。第六随机大数组用来感受一下 O(n²) 的威力——一万个元素也许还行十万个元素就能明显感觉到卡顿。这六组测试跑完你的冒泡排序不敢说性能多好但正确性基本有保障。以后写任何排序算法都可以套用这个思路。5.2 这个小算法给后续工程习惯带来的影响最后说点个人体会。冒泡排序是我见过的唯一一个“用五分钟学会却能在几十年开发生涯里不断从中翻出新东西”的算法。年轻时我总觉得它简单、没用心里惦记的是快排、堆排这些高级货。后来做工程做久了才明白算法本身的价值有时候不在它有多快而在于它的分析框架能训练你什么。每次看到冒泡排序我脑子里会自动跳出一连串问题这个排序稳定吗为什么稳定最坏情况多少次交换能不能提前退出如果把循环边界写错会发生什么这些思考习惯是在一遍遍手写和调试冒泡排序的过程中自然长出来的。后来的职业生涯里处理数据库排序字段、设计分布式系统的局部排序逻辑碰到的问题追到本质都逃不开这些基础概念。所以我的建议是别因为它简单就跳过去认真手写一遍加优化跑测试分析复杂度再横向比较一下其他排序算法。这一套动作做完冒泡排序带给你的东西远不止那几十行代码本身。