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[j+1]，所以 j 最大只能到n-2-i，写成range(n-1-i)正好覆盖0到n-2-i。

注意：内层循环的上界如果写成n - i，当 i=0 时 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[j+1]而不是>=，相等时不交换，所以相同元素的相对顺序不会改变，冒泡排序是稳定排序。这一点在需要保持原始顺序的场景里很重要，比如先按姓名排、再按分数排，稳定排序能保证同分的人维持姓名的相对顺序。

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]（局部小逆序）：

数据规模小的时候差距不明显，但当 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, n=None): 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 左右，超过就抛RecursionError；C 语言虽然默认栈空间大一些，但几十万层递归同样会崩。所以递归冒泡只适合教学和理解递归思想，不适合处理大规模数据。

注意：如果你非要用递归处理较大数组，可以考虑把递归改成尾递归形式，但 Python 和 C 都不做尾调用优化，改了也没用。真要处理大数据，老老实实用迭代版。

4.3 带提前终止的递归版

朴素递归版有个缺陷：即使数组已经有序，它还是要递归 n 层。我们可以把标志位优化搬进递归版：

def bubble_sort_recursive_flag(arr, n=None): 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：

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, cmp=lambda 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], cmp=lambda 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, n=None): 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, n=None): 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，每种规模测三种数据分布：

从数据能看出几个规律：随机数据下各版本差距不大，因为优化主要针对有序场景；已有序数据下边界记录版快了两个数量级，这就是提前终止的威力；递归版因为函数调用开销，普遍比迭代版慢 30% 到 50%。

实操心得：如果你只是想验证算法逻辑，用 Python 写就够了；如果要看真实性能，建议用 C 或 Java 测，Python 的解释器开销会掩盖算法本身的差异。我上面这组数据主要是看趋势，绝对值不用太较真。

7. 从冒泡延伸出去的知识点

冒泡排序虽然简单，但它牵出的知识点其实不少，我挑几个值得深挖的说一下。

循环不变式。冒泡排序的循环不变式可以这样描述：每趟外层循环开始前，数组末尾的 i 个元素已经就位，且是全局最大的 i 个。证明这个不变式在初始化、保持、终止三个阶段都成立，就能严格证明算法的正确性。这是算法课上的标准套路，理解了它，你分析其他循环算法也会更有章法。

比较排序的下界。冒泡、插入、选择、快排、归并都是比较排序，它们的理论下界是 O(n log n)。冒泡的 O(n²) 离下界差得远，这就是它效率低的根本原因。理解这个下界，你就能明白为什么快排和归并是“好算法”，而冒泡只是“能用的算法”。

稳定性与排序键。前面提过冒泡是稳定的，这个性质在多关键字排序里很有用。比如先按分数排序，再按姓名排序，如果第二次排序是稳定的，同分的人就能保持第一次的姓名顺序。Python 的sorted是稳定的，底层 Timsort 就利用了这一点。

递归的代价。递归版冒泡让我第一次直观感受到“递归不是免费的”。每层调用都要压栈、保存现场、返回时恢复，这些开销在 n 大时非常可观。理解了这一点，你就能明白为什么工程代码里递归往往要改成迭代，或者用显式栈来模拟。

原地排序的意义。冒泡是原地排序，空间 O(1)。这在内存受限的场景（比如嵌入式设备）里是优点。虽然冒泡慢，但如果数据量小且内存紧张，原地排序的价值就体现出来了。选择算法从来不是只看时间复杂度，空间、稳定性、实现复杂度都要权衡。

最后分享一个我个人的习惯：每次学一个新算法，我都会拿冒泡排序当参照物，问自己三个问题——它比冒泡快在哪？它牺牲了什么换来的？它在什么场景下反而不如冒泡？把这三个问题答清楚，这个算法基本就吃透了。冒泡排序就像一把尺子，量别人，也量自己。