说起排序算法，冒泡排序大概是很多人编程生涯里接触的第一个算法。它出现在每一本教材里，却几乎不会出现在正式的生产代码中。这种"人人认识、没人细看"的状态，让冒泡排序成了一个很特别的存在：简单到可以背诵，复杂到值得琢磨。

接下来我把冒泡排序从实现到分析彻底拆开讲一遍：先看每一趟比较到底在做什么，再从零写出一个正确的版本，然后把复杂度、稳定性这些结论的推导补齐，最后用实测数据看它在不同输入下的表现，顺便聊聊鸡尾酒排序和梳排序这两个变体。刚学算法的读者可以把它当入门复习，有经验的开发者也能在边界细节和优化里找到一些平时容易忽略的点。

1. 冒泡排序每一趟到底在做什么：从"气泡上浮"说起

1.1 一趟比较的全过程

用一个具体例子最容易说清楚。假设数组是[5, 1, 4, 2, 8]，第一趟从索引0开始，逐个比较相邻元素：

• 比较arr[0]=5和arr[1]=1，5 > 1，交换，得到[1, 5, 4, 2, 8]
• 比较arr[1]=5和arr[2]=4，5 > 4，交换，得到[1, 4, 5, 2, 8]
• 比较arr[2]=5和arr[3]=2，5 > 2，交换，得到[1, 4, 2, 5, 8]
• 比较arr[3]=5和arr[4]=8，5 < 8，不交换

一趟结束，最大的5被"冒泡"到了倒数第二位，而8本身就在最后一位。这里有个细节：即使最大值本来就在末尾，前面那些相对较大的数也会通过交换链逐渐向尾部靠拢，所以"大的往后走"是每趟必然发生的。

第二趟只需要比较到索引2为止，因为最后一位8已经确定是最大值，没必要再碰它。继续比较：

• 1 < 4，不交换
• 4 > 2，交换，得到[1, 2, 4, 5, 8]
• 比较4和5，不交换

第二趟结束，5也到了确定位置。第三趟比较两个元素时，发现1 < 2、2 < 4，整趟都没有发生任何交换，这时就能判定数组已经完全有序。

1.2 每趟结束后的"不变式"：最后一位是确定的

理解冒泡排序的关键，不是记住"它会把大的往右移"，而是记住每一趟结束后数组尾部会多出一个已经确定位置的元素。

这背后是一条循环不变式：第 k 趟结束后，数组末尾的 k 个元素已经处于最终位置。为什么？因为最大值经过相邻交换，一定会一路向右移动，直到遇到比它更大的元素或者到达数组末尾。就算最大值一开始就在中间，它也会被交换到最后一个位置；而第二大值在第一趟结束后一定会在倒数第二个位置之前，第二趟结束时就会到达倒数第二个位置。依此类推。

所以排序 n 个数，外层只需要跑 n-1 趟。因为每一趟确定一个元素，确定完 n-1 个元素之后，剩下的那个元素自然就落在正确位置了。这个结论看似简单，但它正是后面设计循环边界的基础。

1.3 "冒泡"与"沉底"：同一个过程的两套描述

名字叫"冒泡"，是因为大家习惯看大的元素像气泡一样往数组尾部浮。但如果你换个角度，把目光放在小的元素上，会发现它们其实是在往头部"沉"。

这两种描述完全等价。当一个比较大的元素向右交换时，同时意味着一个比较小的元素被挤到了左边。冒泡排序慢的根源，也恰恰在这里：小元素每趟只能向左移动一格，如果有一个很小的数在数组最右端，它要被"沉"到最前面，就必须经历 n-1 趟交换。这个现象在算法领域有个形象的说法叫"乌龟问题"，后面讲鸡尾酒排序时会专门提到。

2. 从零写一个正确的冒泡排序：四个边界细节

2.1 第一版代码：先保证正确

网上能搜到的冒泡排序版本非常多，有的写两层循环，有的写三层，有的收藏排序标志混乱。我建议先写一个不含任何优化的基础版本，跑对了再谈优化：

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

这段代码的骨架就是两层循环加一个交换。外层循环管"趟数"，内层循环管"这一趟要比较哪些相邻位置"。很多人在初学时能背出来，但一旦要求解释为什么边界是n - 1和n - 1 - i，就开始含糊了。这几个边界恰恰是冒泡排序最容易写错的地方。

2.2 外层循环为什么只跑 n-1 趟

有些人会把外层写成range(n)，也有人说应该写range(len(arr))。如果内层边界配套调整，这两种写法在某些情况下也能跑出正确结果，但用n - 1是最清晰的。

理由很简单：一趟内层循环结束，必然有一个最大值归位到数组尾部。需要归位的元素一共 n 个，但对最后一个元素来说，前面的 n-1 个位置都确定之后，它就没有其他位置可去了。所以最多只需要 n-1 趟。拿[2, 1]来说，一趟比较交换后就是[1, 2]，如果还要跑第二趟，那只能是重复劳动。

如果外层写成range(n)，代码不会直接报错，但会把最后一趟白白跑一遍。数据规模小的时候无所谓，对性能有要求或者做代码审查时，这种多余循环很容易被挑出来。

2.3 内层循环的上界为什么要减去 i

内层循环for j in range(n - 1 - i)，核心目的只有一个：保证j + 1不越界，同时不碰已经归位的尾部元素。

当i = 0时，需要比较的范围是0到n - 2，也就是n - 1对相邻元素，正好覆盖整个数组。第一趟结束后，最后一个元素确定，下一趟就不需要再参与比较，所以上界减 1。第二趟结束，倒数第二个元素也确定，上界再减 1。这就是n - 1 - i的来源。

最常见的错误是把内层写成range(n)或range(n - i)。如果是range(n - i)，当j = n - i - 1时，访问arr[j + 1]就可能直接索引越界。Python 会立刻抛IndexError: list index out of range。真正诡异的是，如果你写成range(n - 1)而不是range(n - 1 - i)，代码不会报错，结果也是对的，因为每一次都在比较靠近尾部的已确定元素，白白做很多无用功。这种隐藏性能浪费比显式报错更难发现。

2.4 提前终止优化：把最佳情况从 O(n²) 拉到 O(n)

基础版本无论数据是否有序，都会跑完所有趟数。如果一个数组是[1, 2, 3, 4, 5]，内层循环依然执行约n²/2次比较，这显然是浪费。

解决办法是加一个交换标志：如果整整一趟都没有发生任何交换，说明从当前范围看数组已经有序，后面的循环全部可以跳过。

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

这个版本的威力体现在最佳情况：数组本来就有序，第一趟扫描 n-1 次后没有任何交换，直接跳出，时间复杂度是 O(n)。最坏情况仍然是 O(n²)，因为完全逆序时每一趟都有交换，优化逻辑根本触发不了。很多人误以为加了这个标志后冒泡排序"变快了"，严格说只是让它在接近有序的输入下快起来。

3. 复杂度与稳定性：把结论背后的推导补齐

3.1 比较次数总和：n(n-1)/2 是怎么来的

冒泡排序最被人熟知的结论是"平均和最坏时间复杂度都是 O(n²)"，但 O(n²) 只是一个量级描述，具体比较次数是多少，值得自己推一遍。

未优化版本中，内层循环的执行次数是固定不变的。第一趟比较 n-1 对，第二趟比较 n-2 对，直到最后一趟比较 1 对。总和是：

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

当 n 足够大时，这个值约等于 n²/2。所以复杂度记为 O(n²)。这里的系数 1/2 在日常讨论中通常被忽略，但在性能敏感的场景里，知道冒泡排序的常数开销其实不小，这比只知道"O(n²)"有用得多。

3.2 交换次数：最坏、平均与最好

比较次数只代表循环走了多少遍，真正影响冒泡排序实际代价的，还有交换次数。

• 最坏情况（完全逆序）：每次比较都满足交换条件，交换次数同样是 n(n-1)/2。
• 平均情况（随机排列）：随机数组的逆序对期望数量是 n(n-1)/4，冒泡排序的每次交换恰好消除一个逆序对，所以期望交换次数约为 n(n-1)/4。
• 最好情况（完全有序）：交换次数为 0。

这里的"逆序对"是理解排序算法的好抓手。一次冒泡交换的本质，就是把一对相邻的逆序元素变成顺序，排序过程就是不断消除逆序对的过程。看到这一点，再回头看"冒泡排序慢"这个问题就更有体感：它在随机数据上要消除几百万个逆序对，每一个都要走一次 Python 循环和交换，性能自然上不去。

3.3 空间复杂度与"原地排序"的含义

冒泡排序是原地排序算法，额外空间复杂度 O(1)。因为它只借助常数级别的临时变量完成交换，没有创建新数组。在 Python 中写arr[j], arr[j+1] = arr[j+1], arr[j]看起来不像在用临时变量，实际上 Python 会在底层用元组打包解包，但额外空间依然是常数级。

这个特性在内存受限的嵌入式场景中很重要。同样是排序，归并排序需要一个等长辅助数组，空间复杂度 O(n)，而冒泡排序几乎不占额外内存。当然，现代开发中很少因为省这点内存去选冒泡排序，但在讨论算法性质时，"原地"是一个必须说清楚的关键属性。

3.4 稳定性证明，以及和选择排序的对比

稳定排序指的是：对于值相同的两个元素，排序后它们的相对顺序保持不变。冒泡排序只在arr[j] > arr[j+1]时交换，等于时不交换，因此相等元素的相对位置不可能被改变，它是稳定的。

这一点看着不起眼，实际工程中却很关键。比如先按时间排序，再对同一天内的记录按其他关键字排序，第二次排序如果算法不稳定，就可能打乱第一次的成果。

对比一下选择排序：它每一趟找到最小值，然后和当前位置交换。如果最小值在待排序区间里有重复元素，交换时可能把更早出现的相同值换到后面，导致稳定性丢失。虽然通过特殊写法也能保持稳定，但默认实现下选择排序通常不稳定。所以同样是 O(n²) 级别的简单排序，冒泡排序的稳定性是它区别于选择排序的一个重要优点。

4. 实测数据：n=4000时三种输入下的真实耗时

4.1 测试方法：数据生成与计时

纸上推演再多，不如跑一次数据来得直观。我用 Python 分别测试了基础版和提前终止版，数组规模取 n=4000，输入分为三种：完全逆序、随机排列、已经有序。

测试思路很简单，用time.perf_counter()计时：

import random import time n = 4000 reversed_data = list(range(n, 0, -1)) random_data = [random.randint(0, 10000) for _ in range(n)] sorted_data = list(range(n)) for data in [reversed_data, random_data, sorted_data]: arr = data.copy() start = time.perf_counter() bubble_sort_basic(arr) print(time.perf_counter() - start)

需要提醒的是：不同机器、不同 Python 版本跑出来的绝对时间相差很大，重点看同一数据下不同版本之间的相对差距，而不是把某个数字当成标准答案。

4.2 结果解读：优化在哪些情况下才真正有意义

我机器上的结果大致如下：

前三行数据可以分成两组来看。

完全逆序和随机排列下，提前终止版并没有比基础版更快，因为这两类输入在扫描过程中几乎一直有交换发生，swapped一直都是 True，循环只能跑满。真正体现优化价值的是"已经有序"这一行：基础版仍然老老实实跑了约 800 万次比较，耗时 1.5 秒；优化版第一趟扫描完就 break，耗时可以忽略不计。

从中能得出一个实用结论：提前终止优化不是让冒泡排序"从 O(n²) 变成 O(n)"，而是让它在特定输入下表现出 O(n) 的行为。如果把同样的逻辑用在待排序数组大部分有序、只有少数位置错乱的场景，收益会非常明显。

4.3 一个容易被忽略的参照：内置排序为什么是降维打击

测试时我还顺手对比了一下 Python 内置的list.sort()。同样的 n=4000 随机数据，内置排序耗时在毫秒级别，和冒泡排序的 1.5 秒差了三个数量级以上。

原因有两层：一是复杂度差异，Timsort 平均 O(n log n)，比 O(n²) 快得多；二是实现层面的差距，直接调用内置排序走的是 C 级别的循环和比较，而自己写的 Python 双层循环每一步都要经过解释器。两层差距叠加，结果就是直观的"降维打击"。

这不是说写冒泡排序没有意义。算法课上的复杂度分析和代码实现能力，考察的是对排序本质的理解，工程上该用sorted()的时候就用。真正的高手从来不会在 Python 里手写一个冒泡给几万条数据排序。

5. 两个值得动手实现的变体：鸡尾酒排序与梳排序

5.1 鸡尾酒排序：从"单向冒泡"到"双向冒泡"

前面提到过"乌龟问题"：小元素在单向冒泡中每次只能向左移动一格，非常慢。鸡尾酒排序的想法很直接——既然单向只能往一个方向扫，那就双向交替扫，一趟从左到右把最大值沉到尾部，下一趟从右到左把最小值浮到头部。

def cocktail_sort(arr): n = len(arr) start, end = 0, n - 1 swapped = True while swapped: swapped = False for i in range(start, end): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True if not swapped: break end -= 1 swapped = False for i in range(end - 1, start - 1, -1): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True start += 1 return arr

对[2, 3, 4, 5, 1]这种输入，鸡尾酒排序的优势看得非常清楚。单向冒泡要把 1 从末尾一步步移到开头，需要跑完整整 4 趟；鸡尾酒排序先正向扫完，把最大值 5 放到末尾，紧接着反向扫描，第一趟反向就能把 1 送到最前面。这种"两端同时收紧"的思路，让它对边界错位型数据更友好。

但注意，鸡尾酒排序并没有改变冒泡排序的复杂度，最坏仍然是 O(n²)。它只是在某些特定分布的输入下，减少了无效扫描的次数。

5.2 梳排序：把冒泡的间隔从 1 拉大

如果你理解了"乌龟问题"，自然会想到另一个优化方向：既然小元素一次只能挪一格太慢，那如果能一次挪好几格就好了。梳排序就是从这个思路出发的。

它不再只比较相邻元素，而是先用一个较大的间隔 gap 比较相距 gap 的元素，之后把 gap 按 1.3 倍缩小，直到 gap 变成 1，再做最后的普通冒泡。这个 1.3 是经过大量实验得到的常用收缩因子，能保证排序正确的同时，明显提升性能。

def comb_sort(arr): n = len(arr) gap = n shrink = 1.3 swapped = True while gap > 1 or swapped: gap = int(gap / shrink) if gap < 1: gap = 1 swapped = False for i in range(n - gap): if arr[i] > arr[i + gap]: arr[i], arr[i + gap] = arr[i + gap], arr[i] swapped = True return arr

梳排序的平均表现远好于冒泡排序，有资料把它和一些高级排序算法放在同一量级讨论，但它的理论复杂度分析比较复杂，工程中也很少有人手写。这里列出它，不是为了让你在项目里替换冒泡，而是帮助你理解"间隔比较"为什么能打破冒泡排序每次只能移动一格的限制。

5.3 变体什么时候值得用

这两种变体在实际开发中的出场率都不高。它们的价值更多体现在算法思维层面：鸡尾酒排序教会你"扫描方向也可以双向利用"；梳排序教会你"排序间隔不一定非得是 1"。

如果真要在受限环境下手写排序，比如写一段不依赖标准库的 C 代码给几百万个小数据排序，梳排序可能是冒泡系里唯一值得考虑的增强版。鸡尾酒排序则更适合数据规模很小、且已经知道数组接近有序但两端有乱序元素的场景。

6. 常见实现误区与一次真实的排查过程

6.1 越界问题：arr[j+1] 是怎么爆掉的

冒泡排序最经典的报错就是索引越界。常见写法是：

for i in range(n): for j in range(n): if arr[j] > arr[j + 1]: ...

当j = n - 1时，arr[j + 1]访问的是arr[n]，已经超出列表范围，Python 立刻抛IndexError。这个错误在第一趟内层循环就会触发，所以反而比较好定位。

难定位的反而是另一种情况：写成for j in range(n - 1)。它不会抛异常，因为j + 1最大值是n - 1，始终合法。但如果外层循环还在用range(n - 1)，每一趟都会反复比较已经确定的尾部区域，正确性没问题，性能却在白白浪费。如果你发现冒泡排序在你的机器上比别人的实现慢不少，先检查内层循环是否忘了减去i。

6.2 交换的两种写法：看似等价，坑不一样

Python 里最推荐的交换写法是多重赋值：

arr[j], arr[j + 1] = arr[j + 1], arr[j]

它安全、直观、不需要临时变量。如果用传统方式：

tmp = arr[j] arr[j] = arr[j + 1] arr[j + 1] = tmp

也可以，只是多一行。我不建议在 Python 里为了"炫技"使用异或交换：

arr[j] ^= arr[j + 1] arr[j + 1] ^= arr[j] arr[j] ^= arr[j + 1]

这个技巧在某些 C 语言教材里出现过，但可读性差，而且当两个索引指向同一个元素时，会直接把值清零。在高级语言里没有任何性能收益，纯粹是给自己找坑。

6.3 提前终止标志放错位置带来的死循环或失效

很多人知道要加swapped标志，但位置放错。看下面这段：

swapped = False 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] swapped = True if not swapped: break

问题在于swapped只初始化了一次。第一趟发生交换后，它就一直为 True，后面即使某一趟完全没有交换，not swapped也不会成立，优化彻底失效。正确做法是让swapped在每趟循环开始时重新置为 False，保证它只记录"当前这一趟"的信息。

for i in range(n - 1): swapped = False ...

这个细节几乎每次面试都能筛掉一批人。能讲清楚它为什么在循环内初始化，说明你真正理解了"某趟无交换则整体有序"的前提。

6.4 一次按索引改写的实践记录

某位同学在做练习时，把冒泡排序改成按索引取值，写出了下面这段代码：

for i in range(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=10000 后，程序运行时间突然到了几十秒，整个人懵住了。排查时我们先打印每趟结束后的数组，发现一个很明显的问题：数组末尾已经确定的部分，在后续每一趟里仍然被反复比较；正确版本中内层上界应该随着i增大而减小。

改回来之后，同样数据量从几十秒降到十几秒。这个例子说明，写排序算法不能只追求"结果对"，循环边界是否真的和循环变量挂钩，才是区分"背代码"和"写算法"的分水岭。

7. 我的选型建议：冒泡排序到底该用在哪儿

7.1 数据量小且追求代码最简

如果只是给几十个数排序，而且代码里不希望引入额外的排序思路，冒泡排序完全够用。它的实现量最小，逻辑直白，出 bug 的概率也低。比如写一个快速验证脚本，需要把某个小型配置列表按规则排一下，直接用冒泡没有任何问题。

7.2 在面试和教学中的价值

面试时我经常让候选人手写冒泡排序，重点不是他能不能在两分钟内写出来，而是写完之后能不能回答三个问题：每一趟结束后的不变式是什么？swapped优化适用的前提是什么？为什么说冒泡排序是稳定的？这三个问题能反映一个人是真的理解排序，还是仅仅背过代码。

教学中冒泡排序的作用同样不可替代。它是最容易用"模拟数组状态"来演示的排序算法，适合建立循环不变式、稳定性和复杂度分析的直觉。很多更高级的排序算法理解起来困难，恰恰是因为缺乏这种基础直觉。

7.3 什么时候坚决不用

数据量超过几千、排序发生在性能敏感路径、或者需求方明确要求接近最优排序性能时，都不要用冒泡排序。就算需要稳定排序，也可以优先考虑插入排序，它在接近有序数据上的表现通常比冒泡更好，交换次数更少。大数据量下的排序，直接使用标准库内置排序就是最合理的工程决策。

我个人的体会是：冒泡排序的真正价值不在于"能排序"，而在于它是理解排序算法的起点。每趟确定一个元素的不变式思想，在后续学习选择排序、插入排序、快速排序时会反复出现；稳定性这个概念，更是所有排序算法都绕不开的评价维度。能把一个"入门算法"讲到实现正确、分析透彻、优化合理，本身就说明你对排序这件事有了扎实的理解。