前言冒泡排序bubble sort大概是每个人学编程时写下的第一个排序算法也是最容易写错边界的算法之一。它出现的语境通常是教学但不少人会顺手把它用进真实代码里于是带来两个问题一是性能在 n 稍大时就很糟二是它的优化版本和基础版本常被混为一谈。围绕冒泡排序有三个流传很广的说法都需要纠正一下冒泡排序的时间复杂度是 O(n²)。 严格说基础版本最好、最坏、平均都是 O(n²)加了本轮无交换即提前结束标志的版本最好情况是 O(n)。把两者混着说会让面试对答失分。冒泡排序和选择排序差不多。 两者看着都是两重循环但数据移动的代价差别很大——冒泡每次比较都可能触发元素交换选择排序每一趟只交换一次。冒泡排序因为是 O(n²) 所以一无是处。 换一个角度冒泡排序的交换次数恰好等于序列的逆序对inversion个数这个性质在某些统计场景里是有用的。本文讲清冒泡排序的机制、给出能直接编译的两个版本基础版与优化版、一个泛型版本并用表格把它和选择、插入排序放在一起对照最后列出真会踩的坑。一、原理相邻交换与逆序对冒泡排序的机制只有一句话反复比较相邻的两个元素如果顺序不对就交换位置。每一趟扫描从头走到尾最大的元素会被一路挤到当前未排序区间的末尾——这就是冒泡这个名字的来源。下一趟就不用再管末尾那个已经就位的元素了扫描范围减一。如此重复直到整个序列有序。这里有个值得记住的性质冒泡排序的交换次数等于序列中的逆序对个数。逆序对是指下标i j但a[i] a[j]的一对数。因为每次相邻交换恰好消除一个逆序对且不会引入新的逆序对。所以对于一个几乎有序的数组冒泡排序的实际交换次数非常少而它最慢的情况——完全逆序——需要交换 n(n-1)/2 次。稳定性方面只要交换条件写成严格大于a[j] a[j1]相等元素不会被交换排序就是稳定的stable。如果写成大于等于相等元素也会被换位稳定性就被破坏了。二、基础实现#include algorithm #include cstddef #include iostream #include vector // 基础版冒泡排序任何输入都是 O(n^2) void bubbleSort(std::vectorint a) { const std::size_t n a.size(); for (std::size_t i 0; i 1 n; i) { // 共 n-1 趟 for (std::size_t j 0; j 1 n - i; j) { if (a[j] a[j 1]) { std::swap(a[j], a[j 1]); } } } } int main() { std::vectorint v{5, 1, 4, 2, 8, 0, 2}; bubbleSort(v); for (int x : v) std::cout x ; std::cout \n; // 0 1 2 2 4 5 8 return 0; }几点说明内层上界是n - i因为末尾i个元素已经就位。写成j 1 n - i而不是j n - i - 1是为了避免n 0时n - 1在std::size_t上回绕成极大值。这是无符号类型最容易踩的一个坑。比较和交换用的是严格大于所以排序稳定。下标类型统一用std::size_t避免-Wsign-compare警告也避免有符号与无符号混用时的隐式转换陷阱。三、两个教科书级优化优化一本轮没有发生交换就提前结束。如果某一趟从头到尾一次交换都没有说明序列已经有序后面几趟纯属浪费。优化二记住最后一次交换的位置。该位置之后的元素在本趟中已经确认有序下一趟的扫描范围可以收缩到那里而不只是简单地减一。把两个优化合在一起#include algorithm #include cstddef #include iostream #include vector // 优化版最好情况 O(n)且能动态收缩扫描范围 void bubbleSortOptimized(std::vectorint a) { std::size_t n a.size(); while (n 1) { std::size_t lastSwap 0; // 本趟最后一次交换后的位置 for (std::size_t j 0; j 1 n; j) { if (a[j] a[j 1]) { std::swap(a[j], a[j 1]); lastSwap j 1; } } if (lastSwap 0) break; // 本趟无交换已有序 n lastSwap; // 只扫到上次交换处 } } int main() { // 最好情况已经有序一趟就结束只做 n-1 次比较 std::vectorint sorted{1, 2, 3, 4, 5, 6, 7}; bubbleSortOptimized(sorted); for (int x : sorted) std::cout x ; std::cout \n; // 最坏情况完全逆序 std::vectorint reversed{7, 6, 5, 4, 3, 2, 1}; bubbleSortOptimized(reversed); for (int x : reversed) std::cout x ; std::cout \n; return 0; }关于复杂度可以精确地说基础版比较次数恒为 n(n-1)/2与输入无关。优化版在已有序输入上只做一趟比较 n-1 次即最好情况 O(n)完全逆序时仍是 n(n-1)/2 次比较与同样次数的交换。这些结论是算法分析的结果跟具体机器无关。如果你想在真机上感受差异可以自己写计时用std::chrono::steady_clock分别测已有序数组和随机数组注意把随机数组准备成同一份、并提高优化级别如-O2再比否则测到的主要是调试构建的开销。四、泛型版本与其它排序的对照冒泡排序很容易写成对迭代器友好的泛型形式。注意这里需要双向迭代器bidirectional iterator而不是前向迭代器——因为要从尾部往回退用到--end#include algorithm // std::iter_swap 在 algorithm 中声明 #include functional #include iostream #include iterator #include vector template typename BidirIt, typename Compare void bubbleSort(BidirIt first, BidirIt last, Compare comp) { if (first last) return; for (BidirIt end last; end ! first; ) { --end; // 每趟少看一个已就位元素 bool swapped false; for (BidirIt it first; it ! end; it) { BidirIt next it; next; if (comp(*next, *it)) { // 逆序则交换 std::iter_swap(it, next); swapped true; } } if (!swapped) break; // 提前结束 } } int main() { std::vectorint v{5, 1, 4, 2, 8}; bubbleSort(v.begin(), v.end(), std::lessint()); for (int x : v) std::cout x ; std::cout \n; // 1 2 4 5 8 bubbleSort(v.begin(), v.end(), std::greaterint()); // 降序 for (int x : v) std::cout x ; std::cout \n; // 8 5 4 2 1 return 0; }注意这里的比较器是逆序则交换所以传std::less得到升序传std::greater得到降序——和std::sort的约定一致。下面是三种 O(n²) 排序的对照。交换/移动次数一列是算法分析结论不是某台机器的实测值。维度冒泡排序选择排序插入排序最好时间复杂度O(n)优化版/ O(n²)基础版O(n²)O(n)平均时间复杂度O(n²)O(n²)O(n²)最坏时间复杂度O(n²)O(n²)O(n²)是否稳定稳定用严格大于时不稳定稳定交换/移动次数交换次数 逆序对数交换至多 n-1 次移动约 逆序对数 n额外空间O(1)O(1)O(1)对近似有序数据交换少但比较仍可能多无优势表现好适配链表可以相邻交换代价高可以但需连续找最小最适合链表从表里能看出冒泡最致命的地方它把比较和数据移动绑在一起了。插入排序一次移动只需要一次赋值而冒泡一次交换是三次赋值借助临时变量。逆序对数量相同时冒泡的实际写入量是插入排序的数倍。这就是同样是 O(n²)冒泡通常比插入慢的实质原因。需要真正排序时直接使用标准库#include algorithm #include vector // std::sort通常实现为内省排序introsort不保证稳定 std::sort(v.begin(), v.end()); // std::stable_sort保证稳定代价通常是额外内存或更多时间 std::stable_sort(v.begin(), v.end());常见坑点1. 内层上界用无符号数做减法把 0 减成了极大值。// ❌ n 0 时 n - i - 1 在 size_t 上回绕条件恒真越界访问是 UB for (std::size_t j 0; j n - i - 1; j) { /* ... */ } // ✅ 用加法形式避免减法回绕 for (std::size_t j 0; j 1 n - i; j) { /* ... */ }2. 内层上界永远写a.size()忘了收缩范围。// ❌ 逻辑仍然正确但每趟都白扫尾部已就位元素 for (std::size_t j 0; j 1 a.size(); j) { /* ... */ }// ✅ 逐步收缩 for (std::size_t j 0; j 1 n - i; j) { /* ... */ }3. 用做比较破坏了稳定性。// ❌ 相等元素也被交换不再是稳定排序 if (a[j] a[j 1]) std::swap(a[j], a[j 1]); // ✅ 严格大于才交换 if (a[j] a[j 1]) std::swap(a[j], a[j 1]);4. 以为基础版也有 O(n) 最好情况。// ❌ 这是基础版即使输入已经有序也要跑满 n(n-1)/2 次比较 void bubble(std::vectorint a) { for (std::size_t i 0; i 1 a.size(); i) for (std::size_t j 0; j 1 a.size() - i; j) if (a[j] a[j 1]) std::swap(a[j], a[j 1]); }// ✅ 想让最好情况变成 O(n)必须加无交换即退出的判断 bool swapped true; for (std::size_t i 0; i 1 n swapped; i) { swapped false; for (std::size_t j 0; j 1 n - i; j) { if (a[j] a[j 1]) { std::swap(a[j], a[j 1]); swapped true; } } }5. 把冒泡写成了选择排序。// ❌ 这是选择排序每趟找最小值放到前面交换次数最多 n-1 for (std::size_t i 0; i 1 n; i) { std::size_t m i; for (std::size_t j i 1; j n; j) if (a[j] a[m]) m j; std::swap(a[i], a[m]); }// ✅ 这才是冒泡比较的对象必须相邻 for (std::size_t j 0; j 1 n - i; j) if (a[j] a[j 1]) std::swap(a[j], a[j 1]);6. 在需要稳定的场景里用了std::sort。std::sort不保证稳定排按分数排序、同分保持原顺序这类需求时结果会乱。// ❌ 同分元素的相对顺序可能被打乱 std::sort(students.begin(), students.end(), [](const S a, const S b) { return a.score b.score; }); // ✅ 需要稳定就用 stable_sort std::stable_sort(students.begin(), students.end(), [](const S a, const S b) { return a.score b.score; });7. 对链表用下标写法。std::list没有operator[]冒泡必须写成迭代器版本。// ❌ 编译错误std::list 没有 operator[] if (lst[j] lst[j 1]) { /* ... */ } // ✅ 用迭代器与 std::iter_swap if (*next *it) std::iter_swap(it, next);8. 排序过程中修改了参与比较的元素。如果在比较函数里带副作用比如更新计数器、写日志到同一数组会破坏排序的不变式得到未定义的结果。比较函数应该是纯函数。总结要点结论核心机制反复比较相邻元素逆序则交换交换次数恰好等于序列的逆序对数量稳定性用严格大于比较时稳定基础版复杂度任何输入都是 O(n²)比较 n(n-1)/2 次优化版复杂度最好 O(n)、最坏 O(n²)可动态收缩范围与插入排序相比移动代价更高每次交换 3 次赋值 vs 1 次移动生产环境选择用std::sort需稳定用std::stable_sort边界安全用j 1 n - i而非j n - i - 1避免无符号回绕冒泡排序的价值在于它把排序这件事拆到了最朴素的形式只依赖相邻比较与交换所以它天然稳定、天然 O(1) 额外空间也因此交换次数直接等于逆序对数。理解这一点比记住它的复杂度有用得多。但如果你要在真实项目里给数据排序请直接用std::sort——冒泡排序适合用来学算法不适合用来排数据。编译验证示例均为 C17 标准写法g -stdc17 -Wall -Wextra -Wsign-compare bubble_sort.cpp -o bubble_sort