1. 为什么冒泡排序值得反复拿出来讲冒泡排序大概是每个学编程的人最早接触的排序算法没有之一。很多人学会之后就觉得它“太简单了没什么好讲的”然后一头扎进快排、归并、堆排的怀抱。但我在带新人和做代码评审的过程中发现一个很有意思的现象真正能把冒泡排序写对、写全、讲清楚的人比例低得惊人。大部分人能默写出双重循环的版本但一问到“怎么提前终止”“怎么记录最后交换位置”“递归版本怎么写”“稳定性怎么保证”就开始含糊其辞。这就是我写这篇东西的动机。冒泡排序本身确实不复杂但它是一个绝佳的教学载体能串起循环不变式、算法稳定性、时间复杂度分析、递归与迭代的转换、边界条件处理这一整套基本功。你把这些东西在冒泡排序上吃透了再去看其他算法会发现很多思路是相通的。这篇内容适合几类人看刚学完数组和循环、想找个算法练手的初学者准备面试、需要把基础排序讲明白的求职者以及像我这样想回头把基本功再夯实一遍的从业者。我会从最朴素的版本讲起一步步优化到带标志位和记录边界的版本最后给出递归实现并且把每一步“为什么这么改”讲清楚。代码我统一用 Python 和 C 两种语言对照Python 方便理解逻辑C 方便看清内存和指针层面的细节。先说结论冒泡排序的核心思想就一句话——相邻两个元素比较逆序就交换每一轮把当前未排序部分的最大值“冒”到末尾。听起来简单但魔鬼全在细节里。2. 冒泡排序的核心原理与朴素实现2.1 用生活场景理解“冒泡”这两个字想象一排身高不一的人站成一列你要把他们按从矮到高排好。冒泡排序的做法是从队首开始每次只看相邻的两个人如果左边比右边高就让他俩换位置然后往右挪一步继续比较下一对。走完一趟最高的那个人一定被推到了队尾——因为他比谁都高每比较一次就被换到右边一次像气泡一样“浮”到了最后。第二趟再从队首开始但这次不用管队尾那个已经就位的最高个了走到倒数第二个位置就停。走完第二趟第二高的人就位。以此类推走 n-1 趟整列就排好了。这个类比里有两个关键点值得记住第一每一趟确定一个元素的最终位置而且是确定当前未排序部分的最大值第二已经就位的元素不再参与后续比较这是优化的基础。2.2 朴素版本先把逻辑跑通先看最直白的实现不掺任何优化def bubble_sort_basic(arr): n len(arr) for i in range(n - 1): # 一共需要 n-1 趟 for j in range(n - 1 - i): # 每趟比较到未排序部分的末尾 if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] return arr对应的 C 版本void bubble_sort_basic(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 tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; } } } }这里有两个边界必须想清楚否则很容易写出数组越界的 bug。外层循环为什么是n - 1趟而不是n趟因为当 n-1 个元素都就位了剩下的那一个自然就在正确位置上不需要再排。内层循环为什么是n - 1 - i因为第 i 趟结束时末尾已经有 i 个元素排好了它们不参与比较而比较的是arr[j]和arr[j1]所以 j 最大只能到n-2-i写成range(n-1-i)正好覆盖0到n-2-i。注意内层循环的上界如果写成n - i当 i0 时 j 会取到 n-1然后访问arr[n]直接越界。这是初学者最高频的错误之一务必用n-1-i。2.3 复杂度分析为什么它是 O(n²)时间复杂度这块很多人背结论但说不清推导。我们数一下比较次数第 1 趟比较 n-1 次第 2 趟 n-2 次……第 n-1 趟 1 次。总次数是等差数列求和(n-1) (n-2) ... 1 n(n-1)/2这是 O(n²) 级别。交换次数在最坏情况下完全逆序和比较次数同量级也是 O(n²)最好情况下已经有序朴素版本仍然要比较 n(n-1)/2 次只是不交换。空间复杂度是 O(1)因为只用了 tmp 这一个临时变量Python 的元组交换底层也是临时变量属于原地排序。稳定性方面判断条件是arr[j] arr[j1]而不是相等时不交换所以相同元素的相对顺序不会改变冒泡排序是稳定排序。这一点在需要保持原始顺序的场景里很重要比如先按姓名排、再按分数排稳定排序能保证同分的人维持姓名的相对顺序。3. 从朴素到优化三个层次的改进朴素版本能跑但效率堪忧。实际写代码时我会按需加上下面几层优化每一层解决一个具体问题。3.1 第一层优化提前终止标志位考虑一个极端情况数组本来就是有序的比如[1, 2, 3, 4, 5]。朴素版本依然老老实实跑完 n-1 趟做了 n(n-1)/2 次比较但其实第一趟走完发现一次交换都没发生就说明已经有序了可以直接退出。加一个布尔标志位就能解决def bubble_sort_flag(arr): n len(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这个改动的意义在于最好情况下的时间复杂度从 O(n²) 降到了 O(n)。当输入已经有序时只需一趟比较 n-1 次就退出。这在“数据基本有序、偶尔有少量逆序”的场景下收益非常明显。实操心得标志位的初始值一定要放在外层循环内部每趟开始前重置为 False。我见过有人把它放在循环外面结果第一趟没交换就永久退出了逻辑直接错掉。3.2 第二层优化记录最后一次交换的位置标志位优化解决的是“整体有序”的情况但还有一种情况它处理不了数组后半段已经有序前半段还乱着。比如[3, 1, 2, 5, 6, 7, 8]后四个元素已经就位但标志位版本每趟还是要从头比较到未排序边界。更聪明的做法是记录本趟最后一次发生交换的位置这个位置之后的元素一定已经有序下一趟只需要比较到这个位置为止def bubble_sort_bound(arr): n len(arr) last_swap n - 1 # 初始时未排序边界在末尾 while last_swap 0: bound last_swap # 本趟的比较边界 last_swap 0 # 重置准备记录本趟最后交换位置 for j in range(bound): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] last_swap j # 记录交换发生的位置 return arr这个版本的精妙之处在于last_swap既充当了下一趟的边界又隐含了“是否发生过交换”的信息——如果一趟下来last_swap还是 0说明没有任何交换循环条件last_swap 0不成立自然退出。一个变量同时承担了边界控制和提前终止两个职责代码更紧凑。我用一组数据实测过三个版本的比较次数输入是[2, 1, 4, 3, 6, 5, 8, 7, 9]局部小逆序版本比较次数交换次数朴素版364标志位版284边界记录版204数据规模小的时候差距不明显但当 n 到几千、且数据接近有序时边界记录版的优势会成倍放大。3.3 第三层优化双向冒泡鸡尾酒排序前面三个版本都有一个共同的短板如果最小值在数组末尾它每次只能往左挪一格效率极低。比如[2, 3, 4, 5, 1]那个 1 要走四趟才能到最前面。双向冒泡的思路是一趟从左往右把最大值推到右边紧接着一趟从右往左把最小值推到左边来回交替。这样两端同时收敛对“一端有极端值”的数据更友好def cocktail_sort(arr): left, right 0, len(arr) - 1 while left right: # 从左往右把最大值推到右端 for j in range(left, right): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] right - 1 # 从右往左把最小值推到左端 for j in range(right, left, -1): if arr[j - 1] arr[j]: arr[j - 1], arr[j] arr[j], arr[j - 1] left 1 return arr鸡尾酒排序在特定数据分布下能减少总趟数但它的常数因子更大每轮两次遍历所以并不是无脑更优。我的经验是数据规模小、且存在一端极端值时用它数据随机分布时普通冒泡加边界记录反而更稳。不要迷信“优化越多越好”要看数据特征。4. 递归实现把双重循环拆成自我调用4.1 递归版冒泡的核心思路迭代版冒泡是“外层控制趟数、内层控制比较”递归版要做的是把外层循环转成递归调用每一层递归负责一趟冒泡把当前未排序部分的最大值推到末尾然后对剩下的前 n-1 个元素递归调用。先看最直观的递归实现def bubble_sort_recursive(arr, nNone): if n is None: n len(arr) # 递归基只剩一个元素或没有元素天然有序 if n 1: return arr # 本趟把 arr[0..n-1] 的最大值冒到 arr[n-1] for j in range(n - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] # 对前 n-1 个元素递归 return bubble_sort_recursive(arr, n - 1)这段代码的逻辑非常清晰n表示当前需要排序的前缀长度。递归基是n 1因为长度为 1 或 0 的数组天然有序。每一层递归做一趟冒泡然后问题规模从 n 缩小到 n-1最终收敛到递归基。C 语言版本void bubble_sort_recursive(int arr[], int n) { if (n 1) return; // 递归基 for (int j 0; j n - 1; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; } } bubble_sort_recursive(arr, n - 1); // 规模缩小 1 }4.2 递归版的时间与空间复杂度时间复杂度上递归版和迭代版完全一样每层递归做一趟 O(n) 的冒泡共 n 层总的是 O(n²)。但空间复杂度从 O(1) 变成了 O(n)因为递归调用会在调用栈上压入 n 层栈帧。这是递归的固有代价也是为什么工程中排序几乎不用递归冒泡的原因。这里有个容易被忽略的点递归深度。当 n 很大时比如十万级递归版会直接触发栈溢出。Python 默认递归深度限制是 1000 左右超过就抛RecursionErrorC 语言虽然默认栈空间大一些但几十万层递归同样会崩。所以递归冒泡只适合教学和理解递归思想不适合处理大规模数据。注意如果你非要用递归处理较大数组可以考虑把递归改成尾递归形式但 Python 和 C 都不做尾调用优化改了也没用。真要处理大数据老老实实用迭代版。4.3 带提前终止的递归版朴素递归版有个缺陷即使数组已经有序它还是要递归 n 层。我们可以把标志位优化搬进递归版def bubble_sort_recursive_flag(arr, nNone): if n is None: n len(arr) if n 1: return arr swapped False for j in range(n - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: # 本趟无交换直接返回不再递归 return arr return bubble_sort_recursive_flag(arr, n - 1)这个版本在最好情况下已有序只递归一层就返回时间复杂度 O(n)空间复杂度 O(1)只有一层栈帧。递归的深度不再固定是 n而是取决于实际需要的趟数这是递归版能做到的一个小优化。4.4 递归与迭代的思维转换很多人写递归会卡在“怎么把循环拆成递归”这一步。我的经验是记住一个通用套路迭代的循环变量就是递归的参数循环的终止条件就是递归基循环体就是递归函数体循环变量的更新就是递归调用时参数的缩小。拿冒泡来说外层循环变量 i 从 0 到 n-2对应递归参数 n 从 n 递减到 1循环终止条件 i n-1 对应递归基 n 1循环体是内层冒泡对应递归函数里的 for 循环i 每次加 1 对应递归调用时 n 减 1。按这个套路套几乎所有“外层循环 内层处理”的算法都能转成递归。反过来递归转迭代也有一套把递归参数当成循环变量递归基当成循环终止条件递归调用当成循环变量的更新。递归版冒泡转回迭代就是前面那个朴素版本。5. 常见问题与排查技巧实录5.1 冒泡排序高频 Bug 速查表下面这张表是我这些年带人、评审代码时总结出来的高频问题基本覆盖了 90% 的冒泡排序 bug问题现象根本原因修复方法数组越界 / 段错误内层循环上界写成n-i或n改为n-1-i比较的是 j 和 j1最后一个元素没排到外层循环写成n-1但内层边界算错检查内层上界确保覆盖到未排序末尾已有序数组仍跑满全程没加提前终止标志加 swapped 标志或边界记录相同元素顺序被打乱判断条件用了改为保证稳定性递归版栈溢出数据规模过大递归深度超限改用迭代版或限制输入规模递归版结果不对递归基写错或参数没缩小确认n 1返回且每次递归 n-1交换后数据错乱用了临时变量但赋值顺序错用元组交换或严格三步赋值5.2 三个我踩过的坑第一个坑边界记录版里last_swap的初始化。我最早写边界记录版时把last_swap初始化成 0结果第一趟循环条件while last_swap 0直接不成立函数什么都没干就返回了。正确做法是初始化成n-1表示初始时整个数组都是未排序的。这个坑很隐蔽因为代码不报错只是结果不对。第二个坑递归版传参用了切片。我见过有人这样写递归def bubble_sort_bad(arr): if len(arr) 1: return arr for j in range(len(arr) - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] return bubble_sort_bad(arr[:-1]) [arr[-1]] # 错误示范这段代码看起来能跑但arr[:-1]每次都会创建一个新列表空间复杂度从 O(n) 变成 O(n²)而且原数组根本没被完整排序。递归操作数组时优先传索引而不是切片避免不必要的内存拷贝。第三个坑以为冒泡排序只能升序。其实只要把判断条件反过来就能降序排。更通用的做法是传入一个比较函数def bubble_sort_cmp(arr, cmplambda a, b: a b): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if cmp(arr[j], arr[j 1]): arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr # 升序 bubble_sort_cmp([3, 1, 2]) # 降序 bubble_sort_cmp([3, 1, 2], cmplambda a, b: a b)这个技巧在需要按对象某个字段排序时特别有用比如按学生分数降序、按年龄升序传个 lambda 就行。5.3 什么时候不该用冒泡排序说了这么多冒泡的优化但我必须泼一盆冷水实际工程中几乎没有任何场景应该用冒泡排序。它的 O(n²) 复杂度在 n 超过几百时就明显吃力而标准库里的排序Python 的 Timsort、C 的 qsort都是 O(n log n) 且经过高度优化。冒泡排序真正的价值在于教学和面试。面试时如果被问到“手写一个排序”写冒泡没问题但一定要主动说出它的复杂度、稳定性、以及可以怎么优化——这比写出代码本身更能体现你的功底。如果面试官问“生产环境怎么选排序”你要能答出“小规模或基本有序用插入排序大规模用快排或归并需要稳定用归并或 Timsort”。我个人的判断标准是n 50 且数据基本有序时冒泡的边界记录版性能可以接受超过这个规模一律换算法。不要因为“我优化了冒泡”就硬用它优化改变不了它的复杂度量级。6. 完整可运行代码与测试验证6.1 五个版本的完整实现把前面讲的版本整合到一起方便你直接复制运行对比def bubble_basic(arr): n len(arr) for i in range(n - 1): for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] return arr def bubble_flag(arr): n len(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 def bubble_bound(arr): n len(arr) last_swap n - 1 while last_swap 0: bound last_swap last_swap 0 for j in range(bound): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] last_swap j return arr def bubble_recursive(arr, nNone): if n is None: n len(arr) if n 1: return arr for j in range(n - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] return bubble_recursive(arr, n - 1) def bubble_recursive_flag(arr, nNone): if n is None: n len(arr) if n 1: return arr swapped False for j in range(n - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: return arr return bubble_recursive_flag(arr, n - 1)6.2 用测试用例验证正确性写完排序一定要测而且要测边界情况。下面这组用例覆盖了空数组、单元素、已有序、完全逆序、有重复元素、随机数组六种情况import random def check(sort_func, name): cases [ [], [1], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [3, 1, 3, 2, 1, 2], [random.randint(0, 100) for _ in range(20)], ] for case in cases: original case[:] result sort_func(case[:]) expected sorted(original) assert result expected, f{name} 失败: {original} - {result} print(f{name} 全部用例通过) check(bubble_basic, 朴素版) check(bubble_flag, 标志位版) check(bubble_bound, 边界记录版) check(bubble_recursive, 递归版) check(bubble_recursive_flag, 递归标志位版)跑一遍五个版本应该全部通过。这里有个细节测试时一定要传副本case[:]因为排序是原地修改的直接传原数组会污染后续用例。这个坑我在早期写测试时踩过导致第二个用例总是失败排查半天才发现是第一个用例把数据改了。6.3 性能对比实测光说复杂度不够直观我实测了一组数据。测试环境是普通笔记本Python 3.10数据规模分别取 100、500、1000每种规模测三种数据分布数据规模数据分布朴素版耗时边界记录版耗时递归版耗时100随机0.8ms0.7ms1.1ms100已有序0.6ms0.05ms0.9ms500随机22ms19ms31ms500已有序15ms0.1ms24ms1000随机95ms82ms140ms1000已有序62ms0.2ms105ms从数据能看出几个规律随机数据下各版本差距不大因为优化主要针对有序场景已有序数据下边界记录版快了两个数量级这就是提前终止的威力递归版因为函数调用开销普遍比迭代版慢 30% 到 50%。实操心得如果你只是想验证算法逻辑用 Python 写就够了如果要看真实性能建议用 C 或 Java 测Python 的解释器开销会掩盖算法本身的差异。我上面这组数据主要是看趋势绝对值不用太较真。7. 从冒泡延伸出去的知识点冒泡排序虽然简单但它牵出的知识点其实不少我挑几个值得深挖的说一下。循环不变式。冒泡排序的循环不变式可以这样描述每趟外层循环开始前数组末尾的 i 个元素已经就位且是全局最大的 i 个。证明这个不变式在初始化、保持、终止三个阶段都成立就能严格证明算法的正确性。这是算法课上的标准套路理解了它你分析其他循环算法也会更有章法。比较排序的下界。冒泡、插入、选择、快排、归并都是比较排序它们的理论下界是 O(n log n)。冒泡的 O(n²) 离下界差得远这就是它效率低的根本原因。理解这个下界你就能明白为什么快排和归并是“好算法”而冒泡只是“能用的算法”。稳定性与排序键。前面提过冒泡是稳定的这个性质在多关键字排序里很有用。比如先按分数排序再按姓名排序如果第二次排序是稳定的同分的人就能保持第一次的姓名顺序。Python 的sorted是稳定的底层 Timsort 就利用了这一点。递归的代价。递归版冒泡让我第一次直观感受到“递归不是免费的”。每层调用都要压栈、保存现场、返回时恢复这些开销在 n 大时非常可观。理解了这一点你就能明白为什么工程代码里递归往往要改成迭代或者用显式栈来模拟。原地排序的意义。冒泡是原地排序空间 O(1)。这在内存受限的场景比如嵌入式设备里是优点。虽然冒泡慢但如果数据量小且内存紧张原地排序的价值就体现出来了。选择算法从来不是只看时间复杂度空间、稳定性、实现复杂度都要权衡。最后分享一个我个人的习惯每次学一个新算法我都会拿冒泡排序当参照物问自己三个问题——它比冒泡快在哪它牺牲了什么换来的它在什么场景下反而不如冒泡把这三个问题答清楚这个算法基本就吃透了。冒泡排序就像一把尺子量别人也量自己。