冒泡排序

2026 大纲 七（四）起泡排序（即冒泡排序，两个名字指同一个算法，本篇统一用"冒泡"）。

只看相邻对，就能判断整体有序

冒泡排序只做一件事：从头到尾扫一遍，逐对比较相邻元素，逆序就交换。

一趟扫完之后，序列满足一个不变量：

末尾 $i$ 个是全局最大的 $i$ 个，已升序且位置永不再变；前 $n-i$ 个只经历过相邻交换。

它有一个别的算法都没有的便利：

🔴 "所有相邻对都不逆序" $\Rightarrow$ "整体有序"。 因为 $\le$ 具有传递性——若 $a_0\le a_1\le \cdots \le a_m$，则任意 $a_i\le a_j(i<j)$。

这条性质给了它一个极简单的提前终止判据：本趟一次交换都没发生，就说明已经有序，可以直接收工。快排、堆排都没有这么便宜的终止判据。

先动手看一眼

加载可视化中...

代码与三处要点

void BubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {          // 最多 n-1 趟
        bool swapped = false;                  // 本趟是否发生过交换
        for (int j = 0; j < n - 1 - i; j++) {  // 已就位的末尾 i 个不再参与比较
            if (a[j] > a[j + 1]) {             // 严格大于才交换 —— 稳定性靠这里
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;                // 一次交换 = 3 条赋值
                swapped = true;
            }
        }
        if (!swapped) break;                   // 本趟无交换 ⇒ 已有序，直接结束
    }
}

第一，内层上界 n - 1 - i 是关键。 第 $i$ 趟（$i$ 从 0 计）时末尾已有 $i$ 个元素就位，比较到 a[n-2-i] 与 a[n-1-i] 为止即可，再往后比就是白做。边界上 n <= 1 时外层条件 0 < n - 1 不成立，直接返回，空表与单元素表安全。

第二，swapped 这个判断不是可有可无的。

🔴 最好 $O(n)$ 完全由它提供。不带这个标志的版本，最好情况也是 $O(n^2)$。 没有它时，即使输入已经有序，外层也会跑满 $n-1$ 趟、做 $n(n-1)/2$ 次比较。凡是说"冒泡最好 $O(n)$"，都以带标志的版本为准。

它还带来一条与插入、选择的分界：冒泡的趟数与初始序列有关（$1\sim n-1$ 趟，已有序时 1 趟即止），而直接插入和简单选择都固定 $n-1$ 趟。

第三，稳定性靠"严格大于"。 唯一会改变相对次序的动作是相邻交换，条件是 a[j] > a[j+1]：两个相等元素若成为相邻对，条件为假、不交换。把 > 写成 >=，{2a, 2b} 第 1 趟就被交换成 2b, 2a。

交换次数恒等于逆序对数

这是本篇全部计数结论的来源：

🔴 冒泡的一次交换恰好消除一个逆序对。

因为交换的是相邻两个元素，它们的先后关系翻转，而与其他任何元素的相对次序都没变。排序结束时逆序对数为 0，所以交换次数 = 原序列的逆序对数。

输入	逆序对数	交换次数	移动次数（$\times 3$）	比较次数
正序	0	0	0	$n-1$（1 趟即止）
随机（期望）	${\displaystyle \frac{n(n-1)}{4}}$	${\displaystyle \frac{n(n-1)}{4}}$	${\displaystyle \frac{3n(n-1)}{4}}$	约 $n^2/2$
逆序	${\displaystyle \frac{n(n-1)}{2}}$	${\displaystyle \frac{n(n-1)}{2}}$	${\displaystyle \frac{3n(n-1)}{2}}$	${\displaystyle \frac{n(n-1)}{2}}$

于是时间是最好 $O(n)$、平均与最坏 $O(n^2)$，空间 $O(1)$。

"一次交换 = 3 条赋值"是它最重要的常数因子。 直接插入排序的一次后移只写一条 A[j+1] = A[j]，而它的后移次数同样等于逆序对数，于是

$$\frac{\text{冒泡的赋值次数}}{\text{直接插入的赋值次数}}\approx \frac{3\times \text{逆序对数}}{1\times \text{逆序对数}}=3$$

🔴 同为 $O(n^2)$ 且同样稳定，冒泡却比直接插入慢约 3 倍——差的不是量级，是常数。 这就是"$n$ 稍大就不该用冒泡"的定量依据。

记录很大时更不该用它：每次交换要搬 3 次整条记录，此时应改选简单选择排序（最多 $3(n-1)$ 次移动）。

存储结构上它很宽容：只比较和交换相邻元素，链表上就是"当前结点与它的后继"，所以顺序表、链表都能用。

逐趟推演与执行流程图（第一次学、或想手动模拟就展开）

例一：{5, 3, 4, 1, 2}

趟	本趟的比较与交换	本趟结果	已就位
1	(5,3)换 (5,4)换 (5,1)换 (5,2)换	3 4 1 2 5	5
2	(3,4)不换 (4,1)换 (4,2)换	3 1 2 4 5	4,5
3	(3,1)换 (3,2)换	1 2 3 4 5	3,4,5
4	(1,2)不换 → 本趟无交换，提前终止	1 2 3 4 5	全部

合计比较 $4+3+2+1=10$ 次，交换 8 次（= 24 条赋值）。

例二（含相等关键字，用于观察稳定性）：{49, 38, 65, 97, 76, 13, 27, 49*}

趟	结果
1	38 49 65 76 13 27 49* 97
2	38 49 65 13 27 49* 76 97
3	38 49 13 27 49* 65 76 97
4	38 13 27 49 49* 65 76 97
5	13 27 38 49 49* 65 76 97
6	本趟无交换 → 提前终止

注意第 4 趟：49 与 49* 在某一时刻成为相邻对，比较条件 49 > 49 为假，不交换，两者的先后关系被保住。本例共 6 趟（比 $n-1=7$ 少一趟），这正是提前终止起作用的表现。

不变量的证明与更强的提前终止写法（想弄懂末尾为什么一定就位、或题目给了 last 版本的代码就展开）

证明第 1 趟。 内层循环从 $j=0$ 走到 $j=n-2$，每一步都把 $a[j]$ 与 $a[j+1]$ 中较大者留在右边。设当前区间的最大值初始在下标 $p$：当 $j$ 走到 $p$ 时，比较 $a[p]$（最大值）与 $a[p+1]$，因为它最大必然发生交换，最大值移到 $p+1$；接下来 $j=p+1$，同样的道理它又移到 $p+2$……最大值一旦被扫描指针"接住"，就会被一路推到末尾。所以第 1 趟结束时 $a[n-1]$ 一定是全局最大值。

归纳。 第 $i$ 趟只在 $a[0..n-1-i]$ 上工作，把这个子区间的最大值推到 $a[n-1-i]$。由归纳假设 $a[n-i..n-1]$ 已经是最大的 $i$ 个且有序，而子区间的最大值不大于它们，所以放在 $a[n-1-i]$ 处正合适。$◻$

更强的提前终止：记录最后一次交换的位置。 swapped 只回答"有没有交换"，而更多信息就在手边。设本趟最后一次交换发生在 $j=last$，那么 $a[last+1..]$ 这一段本趟再没发生过交换，说明它们两两之间已不逆序；又因为 $a[last+1]$ 是被从左边推过来的、不小于它左边扫过的所有元素，所以 $a[last+1..n-1]$ 整段都已就位。

void BubbleSort2(int a[], int n) {
    int m = n - 1;                             // 本趟内层循环的右边界
    while (m > 0) {
        int last = 0;                          // 本趟最后一次交换的位置
        for (int j = 0; j < m; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
                last = j;
            }
        }
        m = last;                              // 下一趟只需处理 a[0..last]
    }
}

m = last 一句同时完成两件事：本趟无交换则 last 仍为 0，m 变 0，循环自然结束；有交换则一次可能跳过好几趟。例如 {2, 1, 3, 4, 5, 6, 7, 8}：

版本	过程	趟数
标志位版	第 1 趟交换 (2,1) 后有序，但 swapped 为真；第 2 趟扫完无交换才终止	2
最后交换位置版	第 1 趟唯一一次交换发生在 $j=0$，故 m = 0，直接结束	1

这一段的价值不在于多背一段代码，而在于示范一件事：不变量越强，能省的工作就越多。

链式存储上的冒泡排序与随机情况下逆序对数的期望

链表实现："相邻"在链表上就是"当前结点与它的后继"，所以它是少数几个能直接用于链表的排序之一：用一个指针从头结点开始逐对比较 p->data 与 p->next->data，逆序时交换两个结点的数据域即可（若记录很大也可改成摘链重接，但要多维护前驱指针）；每趟结束把已就位的尾部缩短一个。复杂度不变，仍是 $O(n^2)$——链表并没有省掉比较，只是省掉了下标运算。

随机情况下逆序对数的期望为 $n(n-1)/4$：任取一对下标 $(i,j)$（$i<j$），两元素构成逆序的概率是 $1/2$，而这样的下标对共 $(\genfrac{}{}{0ex}{}{n}{2})=n(n-1)/2$ 个。

比较次数的精确式：第 $i$ 趟（$i$ 从 1 计）做 $n-i$ 次比较，跑满 $n-1$ 趟则

$${\text{KCN}}_{max}=\sum _{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}$$

考点速记

三条结论：

1. 交换次数恒等于逆序对数，一次交换 3 条赋值——所以同为 $O(n^2)$ 却比直接插入慢约 3 倍。
2. 最好 $O(n)$ 是"提前终止判断"的产物；趟数因此与初始序列有关（$1\sim n-1$）。
3. 每趟至少 1 个元素就位，且是当前未排序区的全局最值，位置永不再变。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 由前几趟结果反推排序方法：给出一个序列的前三趟结果，问采用的可能是哪种排序。冒泡的指纹是每趟末尾（或开头）多出一个全局最值且不再动，且前部只发生过相邻交换（元素位置的变动幅度都是 1 格）。⚠️ 与堆排序的尾部长得一模一样，只能靠前部区分——堆排的前部必须满足堆序，冒泡一般不满足。

它还会作为对照项出现在几处判断题里：稳定性判断（冒泡稳定）、"每趟至少确定一个元素最终位置的有哪些"（冒泡符合，但那道题的选项里没放它）、"最坏情况下移动最少的是哪个"（答案是简单选择排序，冒泡是被排除的那个）。

易错："冒泡最好 $O(n)$"以带提前终止判断的版本为准。 题目给的代码里没有 swapped 标志时，最好也是 $O(n^2)$。

易错：冒泡与堆排的中间状态尾部一致。 判断时要看前部有没有堆序。

易错：移动次数是交换次数的 3 倍。 问"移动次数"时别把交换次数直接报上去。

教材出处

• 起泡排序的算法步骤、算法描述（算法 8.4，其中用 flag 标记某趟是否发生交换、无交换则不再执行下一趟）、以 $\{49,38,65,97,76,13,27,49\}$ 为例的逐趟过程（图 8.3，第六趟无交换即完成排序）：严蔚敏《数据结构（C 语言版）》（第 2 版），p242–p243
• 最好情况（正序）只需一趟、$n-1$ 次比较且不移动记录；最坏情况（逆序）$\text{KCN}=n(n-1)/2$、$\text{RMN}=3n(n-1)/2$（每次交换要移动 3 次记录）；空间复杂度 $O(1)$：同书 p243
• 算法特点（稳定排序；可用于链式存储结构；移动记录次数较多，平均时间性能比直接插入排序差）：同书 p243

相关知识

排序的基本概念｜ 快速排序（冒泡的改进：一次交换消除多个逆序对）｜ 直接插入排序（同为 $O(n^2)$ 且稳定，但每次只写 1 条赋值）｜ 简单选择排序（比较次数固定、交换极少、不稳定）｜ 堆排序（尾部一致，靠前部堆序区分）｜ 由中间状态反推排序算法｜ 排序算法对比

相关文章

• 排序基本概念
• 直接插入排序
• 折半插入排序
• 希尔排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序
• 计数排序
• 外部排序
• 由中间状态反推排序算法
• 排序算法对比与性能实测

交互体验

前往完整可视化页面 →

真题练习

相关真题（1题）

2010Q112分