C++冒泡排序及其优化算法

前言冒泡排序bubble sort是最早接触的排序算法之一反复比较相邻的两个元素逆序就交换每一轮把一个极值「冒」到区间末尾。它的最坏和平均时间复杂度都是 O(n²)实际项目里几乎不会用它但它非常适合用来说明「有序区间的扩张」「循环不变式」「提前退出」这些概念也经常作为优化题出现。常见的误解有两个。一是以为加了标志位之后算法就「变快了一个数量级」——标志位只改善了最好情况原本就有序时从 O(n²) 降到 O(n)最坏和平均仍是 O(n²)。二是以为「优化过的冒泡」能和插入排序、快速排序相提并论——在随机数据上冒泡的交换次数远多于插入排序常数也更大优化改变不了这个量级。本文从最基本的双层循环讲起依次加入三种常见优化提前退出标志、记录最后一次交换位置、双向冒泡鸡尾酒排序并说明每种优化改善的是哪一类输入。最后给出复杂度对照表和实现时最容易写错的边界。一、基本冒泡排序算法维护一个不变式第 i 轮结束时区间末尾的 i 个元素已经是全局最大的 i 个且有序。每一轮从下标 0 开始比较相邻元素逆序则交换直到本轮区间的末尾。// 适用于 C17#include cstddef#include utility#include vectorvoid bubbleSort(std::vectorint a) {const std::size_t n a.size();for (std::size_t i 0; i 1 n; i) {for (std::size_t j 0; j 1 n - i; j) {if (a[j] a[j 1]) {std::swap(a[j], a[j 1]);}}}}外层循环执行 n-1 轮就够了每轮至少把一个元素放到最终位置n-1 轮之后剩下的那个自然也在正确位置。内层上界是n - i因为末尾 i 个元素已经有序不需要再比较。关于下标类型这里用std::size_t循环条件写成j 1 n - i而不是j n - i - 1。后者在n - i为 0 时会发生无符号下溢变成一个极大的数循环失控。写成j 1 n - i时j 1最多等于n - i不会溢出j本身远小于SIZE_MAX条件自然为假。这是无符号下标倒序/边界循环最常见的防御写法。正确性可以用不变式说明内层循环每比较一次较大者向右移动一位因此一轮结束后本轮区间的最大值一定停在区间末尾。下一轮把它排除在外重复下去整个数组有序。基本版本的比较次数固定为 n(n-1)/2与输入无关。即使数组已经有序它仍然会把所有比较做完这是后面优化的出发点。二、优化一提前退出标志如果某一轮里一次交换都没有发生说明任意相邻元素都满足顺序整个数组已经有序可以立即结束。用一个布尔标志记录本轮是否交换过// 适用于 C17void bubbleSortFlag(std::vectorint a) {const std::size_t n a.size();for (std::size_t i 0; i 1 n; i) {bool 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;}}if (!swapped) {break;}}}这个优化让最好情况输入已经升序只做一轮 n-1 次比较复杂度 O(n)。对「几乎有序、只有少量逆序对」的数据也有帮助因为一旦某一轮没有交换就提前结束。但要注意最坏情况完全逆序仍然要做满 n-1 轮比较次数不变交换次数是 n(n-1)/2。标志位必须每轮重新置为false不能放在外层循环外面只初始化一次否则第一轮之后永远为真提前退出失效或者反过来永远为假第一轮就退出。这是实现时最常见的错误之一。三、优化二记录最后一次交换的位置观察内层循环如果某一轮中从某个位置之后再也没有发生交换说明那段后缀已经有序下一轮不必再比较到末尾。记录本轮最后一次交换发生的下标lastSwap下一轮的内层上界就收缩到那里。// 适用于 C17void bubbleSortLastSwap(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; // 最后一次交换的右端点}}n lastSwap; // 之后的元素已经有序}}这里用n表示「还需要处理的区间长度」每轮结束后把它更新为lastSwap。如果整轮没有交换lastSwap保持 0n变成 0循环自然结束所以这个版本连标志位都不需要。正确性在于最后一次交换发生在lastSwap - 1与lastSwap之间说明从lastSwap到本轮末尾的相邻元素都满足顺序而本轮末尾又是当前最大值因此这段后缀整体有序可以永久排除。这个优化对「尾部已经有序、头部还有少量乱序」的数据效果明显但它不改变最坏复杂度完全逆序时每轮最后一次交换都在末尾n只减少 1比较次数仍是 O(n²)。四、优化三双向冒泡基本冒泡有一个弱点如果一个很小的元素位于数组末尾它每轮只能向左移动一位需要很多轮才能到位常被称为「乌龟」问题。双向冒泡鸡尾酒排序cocktail shaker sort在一轮里先从左到右把最大值送到右端再从右到左把最小值送到左端两个方向交替进行。// 适用于 C17void cocktailSort(std::vectorint a) {std::size_t begin 0;std::size_t end a.size();bool swapped true;while (swapped begin 1 end) {swapped false;for (std::size_t i begin; i 1 end; i) {if (a[i] a[i 1]) {std::swap(a[i], a[i 1]);swapped true;}}--end; // 右端已就位if (!swapped) {break;}swapped false;for (std::size_t i end - 1; i begin; --i) {if (a[i - 1] a[i]) {std::swap(a[i - 1], a[i]);swapped true;}}begin; // 左端已就位}}边界要仔细核对。初始end a.size()正向循环i从begin到end - 2把最大值送到end - 1随后--end把它排除。反向循环i从end - 1开始比较i - 1与i一直做到begin 1把最小值送到begin随后begin。外层条件begin 1 end保证区间里至少还有两个元素空数组和单元素数组直接不进循环。双向冒泡对「小元素在末尾」的输入改善明显最好情况仍是 O(n)最坏和平均仍是 O(n²)。它并没有改变量级只是把某些输入形态下的轮数减少了一半左右。实现时容易把--end和begin的位置放错导致跳过元素或重复处理建议先用小数组手工推演边界。五、复杂度与稳定性版本最好平均最坏额外空间稳定基本冒泡O(n²)O(n²)O(n²)O(1)是加提前退出O(n)O(n²)O(n²)O(1)是加最后交换位置O(n)O(n²)O(n²)O(1)是双向冒泡O(n)O(n²)O(n²)O(1)是稳定性来自交换条件a[j] a[j 1]只有严格逆序才交换相等元素不会被交换相对次序保持不变。如果把条件写成相等元素也会交换排序结果仍然正确但不再稳定。这一点在只关心数值时无所谓在按某个键排序、要求保持原有次序时就必须注意。交换次数方面冒泡排序的交换次数等于数组的逆序对数量这一点和插入排序相同但冒泡的比较次数固定为 O(n²)除非提前退出而插入排序在部分有序时比较次数接近 O(n)。所以即使都做了优化插入排序通常也更适合「基本有序」的数据。实际工程中应当直接用std::sort它的最坏复杂度是 O(N log N)手写冒泡主要用于教学或面试题。如果确实要在小数组上用手写排序插入排序的常数更小、代码同样简单是更现实的选择。冒泡排序的价值在于它清晰地展示了「每轮确定一个极值」和「提前终止」的思想。常见坑点1. 内层上界写错❌for (std::size_t j 0; j n - i - 1; j)当i n - 1时n - i - 1下溢。 ✅for (std::size_t j 0; j 1 n - i; j)避免无符号减法。2. 标志位不重置❌bool swapped false;写在外层循环之外第一轮之后状态残留。 ✅ 每轮进入内层前重新置false。3. 提前退出条件写反❌if (swapped) break;—— 只要发生过交换就退出排序不完整。 ✅if (!swapped) break;。4. 用比较破坏稳定性❌if (a[j] a[j 1]) std::swap(...)相等元素被交换。 ✅if (a[j] a[j 1])只在严格逆序时交换。5. 最后交换位置更新错❌ 记录lastSwap j左端点下一轮上界少算一位。 ✅ 记录lastSwap j 1它是「已有序后缀的起点」。6. 双向冒泡边界偏移❌ 正向结束后忘记--end或反向循环从end开始访问a[end]越界。 ✅ 正向把最大值送到end - 1后--end反向从end - 1开始比较i - 1与i。7. 认为优化后最坏也是 O(n)❌ 宣称「加了标志位冒泡排序平均 O(n)」。 ✅ 最好情况 O(n)平均与最坏仍是 O(n²)。8. 对空数组或单元素数组没验证❌ 外层直接写for (i 0; i n - 1; i)n 0时下溢。 ✅ 用i 1 n或先判断n 2直接返回。总结优化改善的输入不改善的部分提前退出标志已有序、几乎有序完全逆序仍 O(n²)记录最后交换位置尾部已有序最坏仍 O(n²)双向冒泡小元素集中在末尾最坏仍 O(n²)稳定比较严格大于保持相等元素次序不改变复杂度三种优化针对的是不同的输入形态共同点是都不改变 O(n²) 的最坏复杂度。理解它们的价值在于看清「哪一段已经有序」「什么时候可以停」这两个判断如何减少无用比较而不是指望手写冒泡在实际项目里替代标准库排序。真正需要排序时用std::sort需要稳定时用std::stable_sort手写冒泡留在教学和面试场景即可。