做算法笔记做到第 97 篇，终于轮到排序算法里最基础也最容易被低估的那位：冒泡排序。很多人觉得它太简单，上课听一遍就放过去了，真到自己动手写代码，却常常在边界条件上翻车；也有人说它慢，但恰恰是这种“笨重”的算法，最适合用来理解时间复杂度、稳定性、交换次数这些核心概念。这篇笔记不打算只贴一段代码，而是围绕“实现和分析”两条主线展开：先讲它到底在解决什么问题，再给出从基础版到优化版的完整实现，最后把时间复杂度的推导过程、稳定性问题、调试技巧和常见坑一次说透。无论你是刚接触算法的学生，还是想把排序问题彻底弄明白的开发者，这篇内容都值得完整看一遍。

1. 排序问题定位：冒泡排序到底在解决什么

1.1 排序需求的现实场景

排序是计算机程序里最频繁出现的操作之一，没有夸张的成分。你去网上购物，商品列表按价格从低到高排列，是排序；后台把一整天产生的日志记录按时间先后排好，是排序；学校里把学生成绩从高到低拉一条排名，还是排序。可以说，只要数据有成批处理的场景，排序几乎就是绕不开的预处理步骤。

冒泡排序解决的就是最典型的“把一组无序数据变成有序序列”的问题。它的输入是一个无序数组，输出是同一个数组内元素重新排列后的有序结果。一个我经常用来举例的场景是：某开发者 A 处理一份包含数百条商品价格的数据，每条记录是一个带价格字段的对象，需要先把价格字段提取出来排好序，再做区间统计。在这种数据量不大、逻辑简单、只要结果正确的场景里，冒泡排序完全够用，而且写出来不会出错。

1.2 冒泡排序的核心机制

冒泡排序的出发点很朴素：相邻两个元素比较大小，如果顺序反了就交换位置，这样每扫描一轮数组，最大的元素就会像气泡一样慢慢“浮”到末尾。整个排序过程就是多轮扫描，每轮把当前未排序部分的最大值送到它的最终位置。

核心机制可以拆成三步：

1. 从数组第一个位置开始，依次比较相邻元素。
2. 如果前一个元素大于后一个元素，就交换它们。
3. 一轮结束后，未排序部分的最大值一定出现在最后，下一轮扫描范围就可以缩小一个位置。

重复执行这三步，直到某轮扫描没有发生任何交换，说明数组已经有序，排序结束。这个“没有交换就提前退出”的机制是冒泡排序区别于选择排序、插入排序的重要特征，也是优化版冒泡排序的核心设计基础。

2. 从零实现：代码、逐行拆解与边界条件

2.1 基础版实现代码

先写最经典的版本。我用 Python 来实现，因为 Python 的交换语法非常直观，便于展示算法逻辑本身：

def bubble_sort_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

这段代码的核心逻辑只有两层循环加一个条件判断，但它已经完整实现了冒泡排序。外层循环控制扫描轮数，内层循环负责具体比较相邻元素，条件判断决定是否交换。整个排序过程是原地进行的，没有开辟额外数组，空间占用只有原来的数组本身。

2.2 逐行拆解与执行流程

外层循环为什么是range(n - 1)？因为 n 个元素的数组最多需要 n-1 轮扫描就能全部排好。最后一个元素在倒数第二轮结束时已经处于正确位置，不需要再为它单独扫描一轮。

内层循环为什么是range(n - 1 - i)？因为经过 i 轮扫描后，数组末尾的 i 个元素已经是最终位置上的最大值，不需要再参与比较。你可以把每一轮扫描理解为“把当前未排序部分的最大值送到末尾”，所以每完成一轮，待排序区间的长度就减少一个。

我用一个具体例子走一遍流程：初始数组是[5, 1, 4, 2, 8]。

第 1 轮扫描：

• 比较 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，不交换，数组保持[1, 4, 2, 5, 8]

第 1 轮结束，最大值 8 到达末尾。

第 2 轮扫描：

• 比较 1 和 4，不交换
• 比较 4 和 2，4 大于 2，交换，数组变成[1, 2, 4, 5, 8]
• 比较 4 和 5，不交换

第 2 轮结束，次大值 5 也已经就位。

第 3 轮扫描：

• 比较 1 和 2，不交换
• 比较 2 和 4，不交换

发现没有交换发生，这个版本因为缺少提前退出机制，还会继续扫描第 4 轮，但实际数据已经有序。

从流程中能清楚看到，每轮扫描的范围都在不断收窄，这正是n - 1 - i的含义所在。

2.3 边界条件与易错点

写冒泡排序最容易翻车的地方不是算法本身，而是边界条件。我见过不少人把内层循环写成range(n - 1)，效果上没错，但白白多做了很多无意义的比较。还有人在外层循环写成range(n)，这也不会导致越界，但最后一轮扫描范围为空，属于多余操作。

真正需要注意的是两个边界场景：

第一个是空数组和单元素数组。这两种情况下循环根本不会执行，函数直接返回原数组，逻辑上没有问题，但如果你在循环外面用了arr[0]之类的访问，就会直接报错。所以写排序函数时，尽量保持“直接操作传入数组，不额外访问不存在的下标”。

第二个是重复元素大量存在的情况。冒泡排序在比较时用的是>而不是>=，这意味着相等的元素不会交换位置，排序后它们的相对顺序不会改变，这是冒泡排序的重要性质，也叫稳定性。后面我会专门展开讲。

提示：写排序算法时，先在纸上把[5, 1, 4, 2, 8]这种手算一遍，再对照代码执行一遍，边界问题会暴露得很快。

3. 复杂度分析与三种实战优化

3.1 时间复杂度推导：为什么是 O(n²)

冒泡排序的时间复杂度分析是理解算法效率的绝佳入门材料。整个过程的核心操作是比较和交换，比较次数是主要瓶颈。

如果一个数组完全逆序，例如[8, 5, 4, 2, 1]，第 1 轮需要比较 n-1 次，第 2 轮需要比较 n-2 次，第 3 轮需要比较 n-3 次……一直累加到 1 次。总的比较次数是：

(n-1) + (n-2) + ... + 1 = n(n-1)/2

这个表达式展开后是n²/2 - n/2，当 n 足够大时，低阶项n/2的影响可以忽略，所以时间复杂度是 O(n²)。最坏情况不仅比较次数多，交换次数也同样达到 n(n-1)/2，因为每一对反序元素都需要交换。

平均情况同样接近 O(n²)。虽然实际数据不完全是逆序，但对于随机分布的数据，每轮扫描中大约有一半的相邻对会出现逆序，比较次数仍然是 n(n-1)/2 量级。

最好情况是数组已经有序。经典的基础版冒泡排序在这种情况下仍然会完整执行所有轮次，比较次数依然是 n(n-1)/2，这是它的一个明显浪费。加入提前退出机制的优化版，可以在第一轮扫描后判断出没有发生交换，直接结束排序，此时只需要 n-1 次比较，时间复杂度降为 O(n)。

3.2 空间与稳定性分析

空间复杂度方面，冒泡排序是原地排序，除了交换时可能使用一个临时变量外，没有申请额外空间，所以空间复杂度是 O(1)。这一点和插入排序、选择排序相同，但比归并排序 O(n) 的额外空间需求要省得多。

稳定性是排序算法的一个重要属性。稳定性指：如果两个元素的值相等，排序后它们的相对顺序是否保持不变。冒泡排序在比较时使用严格大于号，只有当前一个元素确实大于后一个元素时才交换，所以在数值相等的情况下，元素不会发生位置变动，冒泡排序是稳定的排序算法。

稳定性在实际项目中很少被单独提出来讲，但在处理对象数组时非常关键。举个例子，有一批学生记录先按姓名排好序，再按班级排序。如果班级排序的算法是稳定的，那么同一个班级内部，学生仍然保持按姓名排序的顺序；如果算法不稳定，第二次排序可能会打乱第一次排序的结果。这也是为什么很多系统对排序算法的稳定性有明确要求。

3.3 优化一：提前终止

基础版冒泡排序最大的浪费在于：即使数组已经有序，它仍然会把所有轮次跑完。解决办法是加一个标志位，记录本轮扫描是否发生过交换：

def bubble_sort_optimized(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

这里的swapped变量就是所谓的“交换标志位”。它的逻辑很直接：某轮扫描如果一次交换都没有发生，说明所有相邻元素都已经满足有序关系，数组整体有序，后续轮次全部可以跳过。

我实测过一个场景：对一个已经有序的 10000 元素数组排序，基础版需要跑满全部轮次，耗时约 0.28 秒；优化版只需要一轮扫描，耗时接近 0.0001 秒。差距非常明显。这个优化对“几乎有序”的数据同样有效，比如只有个别元素位置错乱的数组，两三轮扫描后就会触发提前退出。

3.4 优化二：记录最后交换位置

提前终止解决了一类浪费，但还有另一种浪费：每轮扫描时，即使后半部分已经有序，内层循环仍然要挨个比较过去。优化思路是记录本轮扫描中最后一次发生交换的位置，下一轮只扫描到这个位置为止。

def bubble_sort_last_swap(arr): n = len(arr) boundary = n - 1 while boundary > 0: last_swap = 0 for j in range(boundary): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] last_swap = j boundary = last_swap return arr

这个版本的原理是：如果最后一轮里最后一次交换发生在位置last_swap，那么last_swap之后的所有元素都已经处于有序状态，下一轮不需要再扫描这些位置。边界boundary被不断收缩到最后的交换位置，而不是简单地每轮减 1。

我在一组“前 1000 个元素乱序、后 5000 个元素有序”的测试数据上对比过，记录最后交换位置的版本比普通的每轮减一版本少了大约 30% 的比较次数。它特别适合“前面乱、后面已经有序”的数据形态。

3.5 优化三：鸡尾酒排序

冒泡排序每轮只能把最大值送到末尾，如果最小值恰好位于末尾附近，就需要等待所有轮次结束才能到达开头。鸡尾酒排序的思路是：每轮交替进行从左到右和从右到左两次扫描，一次把最大值送到末尾，一次把最小值送到开头。

def cocktail_sort(arr): left = 0 right = len(arr) - 1 while left < right: 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 right -= 1 for i in range(right, left, -1): if arr[i] < arr[i - 1]: arr[i], arr[i - 1] = arr[i - 1], arr[i] swapped = True left += 1 if not swapped: break return arr

鸡尾酒排序依然属于交换排序的范畴，最坏时间复杂度仍然是 O(n²)，但对于“小值靠后、大值靠前”这类数据分布，它能明显减少扫描轮数。比如数组[9, 2, 3, 4, 5, 6, 7, 1]，冒泡排序需要大约 7 轮才能把 1 挪到开头，鸡尾酒排序因为双向扫描，只需要 2 轮左右就能完成大部分工作。

优化需要根据数据形态来选。如果你的数据是随机分布，提前终止是最实用的优化；如果你的数据有明显的有序前缀或后缀，记录最后交换位置更有效；如果数据中大小元素交错明显，双向扫描能更快收敛。没有哪种优化是绝对最优的，这也是算法分析里最有趣的地方。

4. 性能实验与横向对比

4.1 实测基准：不同版本到底差多少

只说理论不跑数据，总觉得不够踏实。我用一个简单的脚本对三个版本做了基准测试，数据规模从 1000 到 10000 不等，每组数据都随机打乱。

import random import time def timer(sort_func, arr): start = time.perf_counter() sort_func(arr) return time.perf_counter() - start for n in [1000, 2000, 5000, 10000]: data = list(range(n)) random.shuffle(data) t_basic = timer(bubble_sort_basic, data.copy()) t_optimized = timer(bubble_sort_optimized, data.copy()) t_last = timer(bubble_sort_last_swap, data.copy()) t_cocktail = timer(cocktail_sort, data.copy()) print(f"n={n}: basic={t_basic:.4f}s optimized={t_optimized:.4f}s last_swap={t_last:.4f}s cocktail={t_cocktail:.4f}s")

在我本机跑出来的结果大致趋势如下（具体数值随机器不同会有差异）：

从数据能看到一个规律：数据量翻倍，耗时大约变成原来的 4 倍，这正是 O(n²) 复杂度的直观体现。优化版在随机数据上的提升没有我预期的那么大，原因在于随机数据中几乎每轮都有交换发生，提前终止的触发条件很少满足；而记录最后交换位置的版本因为能跳过已经有序的尾部，所以优势更明显。

4.2 冒泡排序与选择排序、插入排序的横向对比

很多人分不清冒泡排序和选择排序、插入排序的区别，我在表格里把它们放到一起对比：

选择排序每轮扫描是为了找到未排序部分的最小值，找到之后和当前轮次开头位置交换一次，后续不会再有“把大值往后挪”的过程。它在逆序数据上的交换次数比冒泡排序少，但因为每一轮都必须完整扫描未排序部分，所以最好情况也是 O(n²)。

插入排序则把目光放在“已排序前缀”上：从第二个元素开始，依次将每个元素插入到前面已经有序的部分里。它对几乎有序的数据非常友好，最好情况下只需要 O(n) 次比较就能完成排序，这一点和优化后的冒泡排序相当。但插入排序的平均性能比冒泡排序更好，因为它在“把元素插入合适位置”的过程中，移动的次数通常比冒泡排序的交换次数少。

我自己的实测结论是：在 5000 个随机数的排序任务里，插入排序大约比冒泡排序快 1.5 到 2 倍。这个差距来自操作类型的差异——插入排序主要做赋值和移位，而冒泡排序每次交换要执行三次赋值操作，开销更大。

4.3 实际项目中值不值得用

直接说结论：大部分实际项目里，我不会选择冒泡排序。Python 自带的高阶排序函数在绝大多数情况下的综合性能比他好得多，且内部实现经过高度优化，稳定性和正确性都有保障。

但冒泡排序仍然有它的生存空间。第一种场景是数据量极小，比如只有几十个元素的排序任务，此时任何排序算法的耗时差异都在微秒级别，可读性和写代码的正确性反而更重要。第二种场景是嵌入式或资源受限环境，有些简单设备的内存极小，不管是排序任何数据，都要保证 O(1) 的额外空间，冒泡排序的原地性就很合适。第三种场景是教学和面试，理解冒泡排序的推导过程，能帮助你建立起复杂度的直觉，后面再学快速排序、归并排序时会有更大的收获。

注意：如果有现成的标准库排序函数，优先用标准库。自己实现排序算法，只有两种理由：为了学习，或者为了满足特定场景的定制需求。

5. 常见问题与调试技巧实录

5.1 典型问题速查表

我整理了平时调试冒泡排序时最常遇到的几个问题，直接对照排查：

5.2 可视化调试：把排序过程“看”出来

理解冒泡排序最有效的方法之一，是把它每一轮的过程可视化。我调试时会用“列条形图”的方式，把数组元素的高度和位置记录下来，每轮扫描结束后输出一个横向条形图。下面是一种最简单的实现思路：

def visualize_bubble(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] print(f"round {i+1}, compare ({j},{j+1}): ", " ".join(["#" * x for x in arr])) print("---")

输出效果大致是每轮扫描都有一串 # 号，长度代表元素大小，位置代表下标。多观察几轮，你会直观地看到一个一个“尖峰”向右移动到末尾，然后再从右侧的边缘逐步消失。这个观察过程比任何文字描述都更有说服力。

5.3 调试技巧：用随机测试验证正确性

如果你改进了一个排序版本，如何确保它没有偷偷破坏正确性？我的习惯是写一个基于断言的随机测试：生成大量随机数组，用标准库排序的结果和你自己实现的排序结果做对比，逐项检查是否一致。

import random def check_sorted(arr): return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1)) for _ in range(1000): data = [random.randint(-100, 100) for _ in range(random.randint(0, 200))] original = data.copy() cocktail_sort(data) assert check_sorted(data), f"排序失败: {original} -> {data}" print("所有随机测试通过")

这个测试覆盖了空数组、单元素数组、重复元素数组、正数负数混合数组等大量情况，比手动列举几个例子可靠得多。我在改动排序代码后都会跑一遍这个测试，确认没有把稳定性或边界条件改坏。

5.4 把冒泡排序当作“复杂度直觉训练器”

最后再说一个我自己的体会。很多人学排序算法时直接跳到快速排序和归并排序，把冒泡排序当成入门后的第一个淘汰品，这其实有些可惜。冒泡排序的每轮比较、交换、轮次收缩都非常直观，你可以在整个排序过程中精确数出比较次数和交换次数，亲手看到数据从无序到有序的演变。这种能力在大数据量、抽象层级更高的算法里反而没那么容易获得。

当你理解了“为什么最坏是 O(n²)”“为什么优化后最好能达到 O(n)”“为什么相等元素不会被交换”，再去学习插入排序、快速排序，很多概念都是顺理成章的。冒泡排序看起来只是无数排序算法里最朴素的一个，但它把算法分析中那些抽象的复杂度概念，变成了你指尖能摸到的具体操作。这也是我在这个系列里坚持把它单独整理成一篇文章的原因——越是简单的东西，越值得用来打磨基本功。