排序算法里冒泡排序是最容易被低估的一个。很多人听到“排序算法”四个字脑子里先想到快排、归并、堆排最后才轮到冒泡排序可一旦真的要手写能一次把冒泡排序写对、写稳、同时讲清楚原理的人其实不多。这算法看着简单里面藏着的边界、稳定性和优化细节足够折腾一阵子。所以我这次不打算只贴一段代码草草了事而是把它当一个真正值得研究的小项目来拆从一趟排序的过程推起把 C、C、Java、Python 四种实现都过一遍再讲优化、复杂度、调试坑和实战选型。无论你是准备面试、带初学者入门还是想确认自己到底有没有把冒泡排序完全吃透这篇内容都能直接拿来用。全程不需要你有很强的算法基础只要跟着敲一遍基本就能形成长期记忆。1. 一趟一轮的完整推导冒泡排序到底在排什么1.1 直观比喻与一趟冒泡的具体过程“冒泡”这个说法其实有点误导。升序排序时更大的元素并不是向上浮而是像石子一样往下沉到数组末尾但我们通常把数组从左到右看作从底到顶末尾当作“水面”所以每一轮最大的元素会跑到最右端看起来就像一个大气泡浮到了水面。这个比喻能帮助记忆每轮至少确定一个元素的最终位置位置从右往左推进。为了讲清楚一趟过程用一个例子[5, 1, 4, 2, 8]。规则很简单从左到右扫描比较相邻两个元素如果左边大于右边就交换一轮结束后参与扫描范围内最大的数一定落在最后一个位置。第一轮的实际动作是这样的5和1比较5 1交换数组变成[1, 5, 4, 2, 8]5和4比较5 4交换数组变成[1, 4, 5, 2, 8]5和2比较5 2交换数组变成[1, 4, 2, 5, 8]5和8比较5 8不交换。这一轮结束后5到了它正确的位置。注意这个例子里的最大值8本来就在最后所以真正“冒”到末尾的是本轮扫描范围内的最大值5。这也是很多初学者的困惑点一轮做完了不一定是整个数组最大值被固定而是这一轮参与扫描区域的最后一个位置被固定但因为扫描区域逐渐缩短最终每个位置都会被覆盖。第二轮从[1, 4, 2, 5, 8]继续1和4比较不交换4和2比较4 2交换得到[1, 2, 4, 5, 8]4和5比较不交换。第二轮结束5的位置也确定了。第三轮扫描时发现1, 2, 4已经有序没有任何交换排序就提前结束。从这个完整过程可以看到冒泡排序的“轮”和“位置”是严格绑定的每一轮都在缩小未确定区域的长度而不是漫无目的地反复扫描。1.2 外层轮数和内层边界是怎么定下来的先看外层循环。n 个元素最多需要 n-1 轮每一轮确定一个位置的最终值前 n-1 个位置确定后最后一个位置自然只剩一个元素不需要再排。所以for i in range(n - 1)是正确的。内层循环为什么是j n - 1 - i关键在“已经确定的位置”不用再碰。比如第一轮i0需要比较的相邻数对是 n-1 对第二轮i1最后一个位置已经固定只需要比较前 n-1 个元素也就是 n-2 对。于是第 i 轮要比较的相邻对数量就是n - 1 - i对应下标 j 从 0 到n - 2 - i写成条件就是j n - 1 - i。这个推导虽然简单但我在帮别人 review 代码时发现最容易出错的就是这里要么不减 i要么减错成n - i要么把 j 的起始写成 1。有一个通用检查技巧把i 0、i n-2分别代进去看一眼。i0时内层要跑 n-1 次in-2时内层只跑 1 次无论哪个取值j1都不能越界。从上面的推导还能直接得到总比较次数第 0 轮 n-1 次第 1 轮 n-2 次……最后一轮 1 次加起来就是 n(n-1)/2。这个数记住就好后面算复杂度会再用到。2. 四种语言实现冒泡排序从 C 到 Python 的同一套逻辑冒泡排序核心就“双层循环 相邻比较 相等不换”三句话但落在不同语言里有不同的表达习惯。下面四段代码我都加了提前退出swapped 标志这是最基础也最实用的优化。先讲 C再讲 C、Java、Python。2.1 C 语言版数组和指针的边界void bubble_sort(int arr[], int n) { if (arr NULL || n 1) { return; } for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) { break; } } }C 语言的实现最贴近底层。这里直接修改传入的数组函数返回值写 void。几个细节值得注意arr NULL || n 1是防御式检查避免空指针和后面n - 1 - i出现无符号负数问题交换用临时变量就可以不需要指针花样swapped变量每次外层循环开始要归零位置不能放错。调用方式就是bubble_sort(arr, n);然后数组本身就被排好了。C 语言没有泛型所以这个函数只能排 int如果要排 double 或者结构体可以改成基于memcpy或者用回调函数但在教学场景下先用 int 把逻辑讲清楚最重要。2.2 C 版模板让排序适配更多类型#include vector #include utility template typename T void bubble_sort(std::vectorT v) { size_t n v.size(); if (n 1) { return; } for (size_t i 0; i 1 n; i) { bool swapped false; for (size_t j 0; j 1 n - i; j) { if (v[j] v[j 1]) { std::swap(v[j], v[j 1]); swapped true; } } if (!swapped) { break; } } }C 用模板 std::vectorT实现可以同时支持 int、double、自定义类型。注意这里我刻意用std::swap而不是手写临时变量后者容易写漏而且对自定义类型的移动语义不友好。另一个重要细节是我把外层条件写成i 1 n而不是i n - 1。因为size_t是无符号类型如果 n0n - 1会变成一个很大的正数外层循环条件成立进去就越界写成i 1 n能避开这个雷。如果你想要更“标准库风格”可以把它改造成迭代器版本但复杂度对新手不友好。实际工程里我会直接用std::sort这个手工函数更多用在学习、考试和嵌入式场景。2.3 Java 版泛型与 Comparablepublic static T extends Comparable? super T void bubbleSort(T[] arr) { int n arr.length; if (n 1) { return; } 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; } } }Java 的对象数组不能直接用比较必须通过compareTo。所以这里用了T extends Comparable? super T这个写法在面试里经常被追问意思是T 本身或者 T 的某个父类实现了Comparable这样用子类数组也能排。如果你不喜欢泛型也可以只写Integer[]版本但泛型版更通用。注意泛型版的代码假设数组元素不为 null因为对 null 调用compareTo会抛空指针。如果你要处理 null需要先做特判比如规定 null 一律认为最小这也是一种常见设计。2.4 Python 版最简洁也有隐藏陷阱def bubble_sort(arr): n len(arr) if n 1: 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 arrPython 的并行赋值让交换写起来非常舒服但注意它等价于先算出右侧的元组再解包赋值。如果你把它拆成三行连续赋值很可能出错后面第五节会专门讲。return arr让函数可以链式调用或直接断言不是必须的但方便测试。2.5 四个版本横向对比维度C 语言版C 版Java 版Python 版交换方式临时变量std::swap临时变量并行赋值主要边界风险空指针/无符号size_t 下溢数组越界range 负数泛型支持无模板Comparable动态类型稳定性稳定稳定稳定稳定适用场景嵌入式/教学考试/嵌入式面试/通用脚本/教学为什么我每个版本都保留了swapped标志因为带上它最好情况才是 O(n)这才是“标准冒泡排序”的完整形态不带的话就算输入已经完全有序也照样跑满 n(n-1)/2 次比较。真上了战场这个标志位往往比花哨的优化更管用。3. 冒泡排序的三种优化什么时候有效什么时候白费劲3.1 基础优化swapped 标志位提前退出标志位逻辑很简单某一轮从头到尾没有任何交换说明相邻元素全部满足数组已经有序可以 break。这就是最好情况 O(n) 的来源。代码量小收益高几乎没有副作用我建议任何时候都带上。这个优化在“几乎有序”的数据上效果尤其明显。比如一个 1000 元素的数组只有前 10 个是乱序普通冒泡要跑近 50 万次比较带标志位的冒泡可能扫两三轮就停了。它没有改变最坏复杂度但把最好情况从 O(n²) 拉到了 O(n)。3.2 进阶优化记住最后一处交换的下标如果数据后半段本来就有序每一轮内层循环其实都在做无意义的比较。我们可以记录这一轮最后一次发生交换的位置last_swap下一轮只需要扫描到这个位置为止后面确定有序的部分直接跳过。void bubble_sort_bound(int arr[], int n) { int end n - 1; while (end 0) { int last_swap 0; for (int j 0; j end; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; last_swap j; } } end last_swap; } }这个版本比基础版多了两行但边界很容易写错。我在 review 时见过把end last_swap写成end last_swap 1的也见过把last_swap初始化成 -1 的。都不致命但会多跑或少跑一轮。如果你不确定可以先用基础版只有明确看到“数组尾部有一长段有序区”时再上这个优化。3.3 方向优化鸡尾酒排序双向冒泡标准冒泡每轮只从左往右扫鸡尾酒排序则一轮从左往右、一轮从右往左交替。这对于“大部分元素集中在某一端”的数据有效比如[2, 3, 4, 5, 1]这种小元素在末尾的情况普通冒泡要把1一路“搬”到最左边而双向扫描一轮就能把它提到最前面。def cocktail_sort(arr): n len(arr) if n 1: return arr left, right 0, n - 1 swapped True while swapped: swapped False for i in range(left, right): if arr[i] arr[i 1]: arr[i], arr[i 1] arr[i 1], arr[i] swapped True if not swapped: break swapped False right - 1 for i in range(right, left, -1): if arr[i - 1] arr[i]: arr[i - 1], arr[i] arr[i], arr[i - 1] swapped True if not swapped: break left 1 return arr鸡尾酒排序的平均复杂度同样是 O(n²)常数可能更大并不是银弹。我用它主要是在“数组几乎有序但有少数元素错位很远”的场景收益比普通冒泡明显。3.4 这些优化和输入数据的关系数据特征普通冒泡标志位记录边界鸡尾酒完全有序O(n²) 比较O(n)O(n)O(n)只有一个元素错位在数组另一端O(n²)接近 O(n²)快一些明显更快随机数据O(n²)O(n²)O(n²)O(n²)完全逆序O(n²)O(n²)O(n²)O(n²)这里要强调一个观点这些优化改变的是常量和提前终止条件不改变渐进复杂度。真正的收益来自“数据不是太难”时能提前停下来。如果数据完全随机还是不要在冒泡上浪费时间直接上快排或内置排序。4. 复杂度、逆序对与稳定性为什么说它是 O(n²)4.1 从比较次数推导到三种情况最坏情况是数组完全逆序。第一轮需要 n-1 次比较第二轮 n-2 次直到 1 次总数等于[ (n-1) (n-2) \cdots 1 \frac{n(n-1)}{2} ]所以最坏时间复杂度是 O(n²)。而且完全逆序时每轮的比较都会触发交换交换次数同样是 n(n-1)/2。最好情况是数组已经有序并且带了swapped标志位只跑第一轮扫描做 n-1 次比较就 break交换次数是 0。注意如果不带标志位最好情况依然是 O(n²)这是很多人容易答错的地方。平均情况要分两部分看标准实现的内层循环比较次数和输入数据无关永远是 n(n-1)/2所以平均比较次数就是 O(n²)交换次数则约等于逆序对数的期望随机序列大概是 n(n-1)/4。这也是为什么我们说“平均 O(n²)”时主要指的是比较次数稳定偏高而不是每次都是最坏交换量。4.2 一次相邻交换只消灭一个逆序对逆序对的定义是i j但a[i] a[j]。冒泡排序每次交换的都是相邻且逆序的两个元素交换之后这两个元素之间的顺序被修正而它们和其他元素的相对位置没有变所以逆序对数严格减少了 1。这意味着冒泡排序的交换次数有一个精确下界它最少也要执行“初始逆序对数”次交换。例如[3, 1, 2]的逆序对是(3,1)和(3,2)两个冒泡排序恰好交换两次。这个结论在面试衍生题里经常出现比如问“冒泡排序的交换次数能否小于逆序对数”答案是不能。4.3 和插入排序、选择排序放在一起看维度冒泡排序插入排序选择排序比较次数随机n²/2 固定n²/4 左右n²/2 固定交换/移动次数逆序对数约 n²/4 移动n-1 次交换有序输入O(n)可提前退出O(n)适应性很强O(n²)不可提前退出稳定性稳定稳定不稳定适用场景教学/特殊场景几乎有序小数组交换代价极高的场景插入排序在很多场景下都是“普通稳定原地排序”里更优选比较次数少移动次数少而且同样能处理几乎有序的数据。选择排序最突出的优势是交换次数固定为 n-1 次适合元素交换成本极高但比较便宜的场景比如排序元素是大结构体时。冒泡的优势则在于“相邻交换”带来的稳定性天然可控以及代码实现最简单、最容易证明正确性。4.4 稳定性为什么相等元素千万不能交换稳定性定义相等元素的相对次序在排序前后不变。为什么重要因为多关键字排序需要它。比如先按姓名拼音排再按年龄排如果第二次排序是稳定排序年龄相同的人还能保持第一次姓名排序的顺序。冒泡排序稳定的原因是它只在a[j] a[j1]时才交换严格大于等于时不动。如果代码手抖写成相等元素就会被交换稳定性立刻消失排序结果虽然看起来还是有序但相同元素的原始顺序被打乱。判断稳定性的通用口诀值相等的两个元素能不能越过彼此不能就稳定能就不稳定。5. 写冒泡排序踩过的坑下标和标志位最容易翻车5.1 内层循环上界写错最常见的越界和后患内层循环上界的错误版本很多最典型的是把上界写成j n当 j 取到 n-1 时j1就越界了。C/C 这种场景是未定义行为Java/Python 会直接抛异常。把上界写成j n - 1但不减 i虽然不会越界但会反复扫描已经排好的尾部标志位优化直接失效。写成j n - 2 - i是等价写法但要确认 i 和 n 的类型是否一致别把有符号和无符号混在一起。检查技巧只有一个把最大轮代入确保最后一个有效 j 满足j 1 n。这个检查一次到位比肉眼反复看强很多。5.2 swapped 标志位的位置和方向标志位方向写反是很隐蔽的坑。伪代码结构应该是for i in range(n - 1): swapped False # 必须放在外层循环开头 for j in range(n - 1 - i): if arr[j] arr[j 1]: swap() swapped True # 只有真的交换才能置 True if not swapped: # 本轮无交换才退出 break常见错误有三种把swapped False初始化写在内层循环里导致每次比较前都被重置标志位永远为 False优化完全失效把swapped True写在 if 外面任何一轮都认为有交换永远不会提前退出把if not swapped: break写成if swapped: break第一轮有交换后就立刻退出排序结果必然错误。第三种错误在快速手写代码时很容易犯因为人脑容易把“有交换就继续”当成“有交换就结束”。5.3 对象比较时用了引用相等Java 里直接写arr[j] arr[j 1]根本编译不过必须用compareTo。C 自定义类型如果没重载operator也一样编译不过。但还有一个更隐蔽的问题有人拿判断对象“相等”这在 Java 中比较的是引用地址不是内容可能导致两个内容相同的对象被错误地交换破坏稳定性。处理原则很简单对象排序一律走compareTo或operator不要依赖语言默认的相等语义。尤其在对结构体、自定义类排序时要明确“值相等”和“引用相等”的区别。5.4 Python 并行赋值写成连续赋值这是 Python 新手最常踩的坑。错误写法# 错误arr[j] 被覆盖后arr[j 1] 拿到了错误的值 arr[j] arr[j 1] arr[j 1] arr[j]执行结果会让两个位置都变成原来的arr[j 1]值元素直接丢失。正确写法必须是并行赋值arr[j], arr[j 1] arr[j 1], arr[j]并行赋值的机制是先把右侧的元组(arr[j 1], arr[j])算出来再从左到右解包所以不存在中间覆盖问题。我在帮助别人调试时发现这个错误不是个小概率事件一旦出现排序结果看起来往往只是“差一点点”很难一眼看出所以特别需要测试用例兜底。5.5 空数组、单元素数组和零轮循环空数组和单元素数组在 Python 里比较安全range(n - 1)在 n0 时生成range(-1)是空区间循环直接不执行n1 时生成range(0)也不执行。但在 C/C 中如果 n 是size_t无符号整数n - 1在 n0 时会变成一个很大的正数外层循环条件成立进到内层j 1就是越界访问属于未定义行为。因此我强烈建议每个语言版本开头都做if (n 1) return;。这不算过度防御而是必要的边界处理。5.6 一套可复现的验证方案真实测试不能只拿一组数据跑一下要覆盖边界和随机数据。我常用的做法是准备这几类输入空数组、单元素数组完全有序数组完全逆序数组大量相等元素的数组随机数组、随机长度。这里给一个 Python 测试脚本逻辑可以直接移植到其他语言import random def verify_bubble_sort(sort_func): cases [ [], [1], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [3, 3, 1, 2, 2], ] for c in cases: assert sort_func(c[:]) sorted(c), (c, sort_func(c[:])) for _ in range(200): a [random.randint(-1000, 1000) for _ in range(random.randint(0, 100))] b a[:] assert sort_func(a) sorted(b), (b, a) print(all passed)注意这里的sort_func如果像我前面写的那样在函数内部原地修改并返回 arr那测试里调用sort_func(c[:])没问题如果它返回 None测试就要改成先拷贝、再排序、再比较。所有语言版本都可以移植这个思路Java 或 C 里就把随机数组生成逻辑用对应语言重写一遍。6. 真实工程与面试里冒泡排序还有没有位置6.1 什么时候我依然会主动用它不是所有排序都值得上快排。冒泡排序真正适用的场景有三个第一数据规模很小n 只有几十个并且需要原地排序代码极短。嵌入式 MCU 固件、简单脚本里一段不到二十行的冒泡排序很好维护。第二数据几乎有序并且你希望排序过程“肉眼可读”带标志位的冒泡扫一轮基本就能停。第三稳定性要求高又不方便引入额外内存冒泡是原地稳定排序不需要辅助数组。但说实话几乎有序时插入排序也是稳定原地而且平均更好。所以冒泡最不可替代的场景还是“教学 极简 确定性强”。如果项目里已经有现成的内置排序函数不要为了“显摆算法功底”而手工造轮子。6.2 什么时候果断放弃当 n 超过几万、百万O(n²) 就是灾难。我在 10 万元素随机数组上实测过标准冒泡大概要跑几十秒甚至更久而std::sort或 Python 内置sorted是毫秒级。差距是几个数量级不是简单的“慢一点”。还有递归深度受限的环境比如某些嵌入式平台快排可能因为递归调用栈溢出不合适但这时候也不能回到冒泡。应该考虑归并排序的迭代版本、堆排序或者按数据特点选择基数排序。冒泡的“简单”救不了“大数据量”这个硬伤。6.3 嵌入式与硬件里的特殊考虑有些 MCU 内存小、没有硬件除法、编译器优化弱冒泡循环结构简单代码量小容易通过静态分析证明不越界。在“数组几乎有序只有少量元素错位”的传感器校准、通信协议帧排序等场景提前退出标志位能直接降低平均耗电和延迟。另外在硬件层面冒泡思想会以排序网络的形式出现比如奇偶归并排序就是受冒泡启发的一种并行比较交换结构。如果你在做 FPGA 或并行排序电路相邻比较器这种最简单的单元反而很常用。这也是为什么经典的“没用”算法仍在教材里活着它的结构足够简单能作为其他复杂结构的基石。6.4 面试时怎么聊才不算掉价面试考手写排序时常见要求是“写一个你熟悉的排序算法”。你写冒泡可以但至少要做到以下四点主动说明复杂度、稳定性和优化点不要只丢一段代码提到“不优化时最佳输入也是 O(n²)加了提前退出标志后才有 O(n)”把稳定性讲清楚只有严格大于才交换相等不换顺手写边界保护空数组、单元素数组。如果面试官追问“还有更快的方式吗”可以从插入排序的对比说起然后转到归并、快排。冒泡只是起点不是终点能把“为什么这个简单算法有存在价值”讲明白比背一段代码有用得多。顺便说一句我在真实项目里最后一次主动选冒泡排序是某个单片机传感器采集模块。采集的几十个温度值本来就只有一两个乱序固件空间还紧巴巴的。当时我用带标志位的冒泡一次遍历基本就结束了代码不到二十行review 也轻松。后来数据量提到几千第一件事就是把它换成二路归并。冒泡不丢人丢人的是不看场景硬上。