冒泡排序从原理到优化：C语言实现与复杂度稳定性详解

如果你问一个刚学编程的人哪个排序算法他闭着眼都能写出来十有八九是冒泡排序。名字形象、代码短、思路直白它几乎是很多人人生中接触的第一个算法。但我在给某学弟补C语言的时候发现能把代码默写出来的人不少能答出“内层循环为什么是 n-1-i”“冒泡排序最好情况时间复杂度是多少”“相等的元素为什么不会乱序”的人并不多。这篇东西就是想把冒泡排序从“会背代码”拉到“理解透彻”我会从原理开始把C语言实现从基础版一步步优化到能实际用的版本再把复杂度、稳定性、调试经验挨个讲清楚。不管你是刚学C语言的大学生还是准备面试想巩固基础或者是准备教别人排序算法这篇应该都有参考价值。1. 冒泡排序到底在“冒”什么从一次完整遍历说起1.1 “气泡上浮”这个比喻到底准不准很多人第一次听“冒泡排序”脑子里浮现的画面是水底的气泡一路往上飘越接近水面越大。这个比喻和算法的对应关系其实是这样的在一个数组中我们把较大的元素看成“更重的东西”在每一轮相邻比较中它只要发现自己比右边邻居大就向右移动一步。经过一整轮最大的元素就像气泡一样“浮”到了数组末尾。但这里有一个容易误导的地方气泡在水里是一路畅通往上走的而数组里的“大数”向右移动的每一步都要靠相邻比较来驱动一次只挪一格。所以在最坏情况下一个元素从开头挪到末尾需要走完一整轮这也是冒泡排序被当成“慢排序”代表的原因之一。搞清楚了这一点你再看任何冒泡代码都会觉得每一行都非常自然。1.2 拿一组数据把第一轮走一遍我习惯用一组不长不短的数据来做演示{5, 1, 8, 4, 2}。下面把这一趟完整的相邻比较列出来箭头左边是交换前的数组状态。j05 1交换得到 {1, 5, 8, 4, 2}j15 8不交换数组还是 {1, 5, 8, 4, 2}j28 4交换得到 {1, 5, 4, 8, 2}j38 2交换得到 {1, 5, 4, 2, 8}你看最大的 8 一路从中间位置“冒”到了末尾。第二轮对前 4 个元素 {1, 5, 4, 2} 做同样的操作5 会被送到倒数第二位第三轮轮到 4第四轮轮到 2。整个过程就像水底的气泡一串一串浮上来只不过每次只完整浮现一个。如果你用动画演示软件跑一遍会发现一个很有意思的现象比较不是跳跃式的而是像“爬行”一样逐个向右推进。这种“相邻交换”的动作是冒泡排序区别于选择排序和插入排序最核心的特征。1.3 看懂“每轮确定末尾位置”就算入门了第一轮结束数组末尾的位置放好了全局最大值。第二轮结束倒数第二个位置放好了第二大的值。所以外层循环每走一次我们就“锁定”了数组从后往前的一个位置。我在教某学弟的时候经常让他回答一个问题做了 i 轮之后最后面 i 个数还需不需要再参与比较答案是已经不需要了。因为每一轮确定一个最大值放到末尾这些位置不会在接下来的轮次里被动摇。这就是内层循环写成 j n - 1 - i 的原因——末尾的 i 个位置已经是最终顺序比较区间越缩越短。很多人把冒泡排序的“循环不变量”说得特别玄乎其实就是一句大白话每完成一轮外层循环后缀 i 个元素已经有序。懂了这个后面看任何优化版本都不会发怵。2. C语言实现的四个台阶从教科书版到实用版2.1 教科书基础版双重循环的结构与边界先给出最标准的写法所有C语言教材上几乎都这么写void bubble_sort(int arr[], int n) { int i, j; for (i 0; i n - 1; i) { for (j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; } } } }外层循环为什么是 i n - 1因为 n 个元素只需要 n - 1 轮就能让最后一个元素自动归位。我见过有同学写 i n多跑一轮结果也没错但完全没必要。内层循环为什么是 j n - 1 - i前面已经说过末尾 i 个元素在之前几轮里已经确定位置再比较就是浪费。这段代码的交换部分用了临时变量 tmp这是交换两个整数的标准动作没什么好说的。唯一要注意的是别漏掉中间那行漏了就变成“复制”而不是“交换”数据会直接出错。2.2 第一次优化用swapped标记提前结束基础版有个很“笨”的地方哪怕数组已经是完全有序的它依然会跑完所有轮次。比如排序 {1, 2, 3, 4, 5}第一轮跑完一次交换都没发生按理说已经可以停了但基础版还是会继续做完全部比较。解决办法是加一个标记变量void bubble_sort(int arr[], int n) { int i, j; for (i 0; i n - 1; i) { int swapped 0; for (j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) { break; } } }每次进入新一轮先把 swapped 置为 0。一旦发生了至少一次交换就置为 1。这一轮走完如果 swapped 还是 0说明从开头到当前比较区间末尾都没有需要交换的相邻对整个数组已经有序直接跳出外层循环。这个优化让最好情况从 O(n²) 降到了 O(n)。对于已经有序或者接近有序的数据效果立竿见影。对于一个本来就有序的 10 万元素数组优化版只跑一轮就退出时间几乎是 0基础版则要跑完将近 5 亿次比较差距非常恐怖。2.3 第二次优化记录最后一次交换的位置加了 swapped 标记之后还能不能再省一点可以。观察一下某轮中最后一次交换发生在位置 j那意味着从 j 往后到当前边界之间的所有相邻元素都已经有序。下一轮我们根本不需要再比较到原来的边界只需要比较到 j 就够了。基于这个思路可以这样改写void bubble_sort(int arr[], int n) { int last n - 1; while (last 0) { int new_last 0; int j; for (j 0; j last; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; new_last j; } } last new_last; } }这里的 last 就是“本轮需要比较到的最大下标”。每轮结束后把 last 更新为最后一次交换位置 j。如果整轮没有交换new_last 保持为 0下一次循环条件 last 0 不成立循环自然退出。这段代码还顺带解决了 swapped 版的冗余假设某轮比较到中间某处之后就不再发生交换下一轮就真的只比较到那里后面的区域彻底不再碰。我之前测试过一组数据类似 {1, 2, 3, 4, 5, 6, 0}这种写法比单纯加 swapped 标记还要少跑不少比较。代价是代码稍微隐晦一点初学阶段可以先跳过但理解了之后会很有成就感。2.4 双端冒泡鸡尾酒排序真正的实用优化前两种优化都还只是在“比较区间”上做文章。有一个更直观的方向既然从前往后能把大的送到末尾那从后往前是不是也能把小的送到开头两边同时“冒泡”就是鸡尾酒排序也叫双向冒泡。void cocktail_sort(int arr[], int n) { int left 0, right n - 1; while (left right) { int swapped 0; int j; for (j left; j right; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } right--; for (j right; j left; j--) { if (arr[j] arr[j - 1]) { int tmp arr[j]; arr[j] arr[j - 1]; arr[j - 1] tmp; swapped 1; } } left; if (!swapped) { break; } } }向右走一轮确定右边界的最大值向左走一轮确定左边界的最小值。对于“大的集中在左边、小的集中在右边”这类数据比如 {10, 9, 8, 7, 1, 2, 3}鸡尾酒排序的速度大约是普通冒泡的两倍。因为普通冒泡一轮只能把最大的 10 送到末尾而 1、2、3 还要慢慢往左挪鸡尾酒排序却能在往回走的时候顺手把 1 送到开头效率提升非常明显。2.5 四个版本横向对比版本最坏时间复杂度最好时间复杂度额外空间特点教科书基础版O(n²)O(n²)O(1)最简单最容易理解swapped提前退出O(n²)O(n)O(1)对有序数据友好记录最后交换位置O(n²)O(n)O(1)省去冗余比较区间鸡尾酒排序O(n²)O(n)O(1)对特定分布数据更快四个版本空间复杂度都是 O(1)这是冒泡排序的一大优点——原地排序不需要额外数组。你只要记住如果哪天有人问“冒泡排序最好情况时间复杂度是多少”答案不是 O(n²)而是 O(n)因为加了提前退出机制之后有序数组只需要一轮 n-1 次比较。3. 把账算清楚复杂度、交换次数与稳定性3.1 比较次数怎么算n(n-1)/2的由来基础版的比较次数是固定值与数据分布无关。第一轮比较 n-1 次第二轮比较 n-2 次一直递减到最后一轮比较 1 次。把所有轮次相加(n-1) (n-2) ... 2 1 n(n-1)/2这个公式你应该很眼熟它就是等差数列求和。用 n5 代入得到 10 次比较前面演示的 {5, 1, 8, 4, 2} 走完基础版确实正好 10 次比较。这里要注意加了提前退出优化之后比较次数就不是固定值了。最好情况下是有序数组第一轮做完 4 次比较就退出最坏情况下是逆序数组依然要做满 10 次比较。所以聊复杂度的时候一定要把“哪个版本的冒泡”说清楚否则容易鸡同鸭讲。3.2 交换次数最好、最坏与平均比较次数只反映“看了多少次”交换次数才是冒泡排序真正“干活”的量。最坏情况比如输入 {5, 4, 3, 2, 1}每一轮比较都会触发交换交换次数等于比较次数同样是 n(n-1)/2。最好情况是输入完全有序交换次数为 0。平均情况下的交换次数严谨一点说取决于数组中“逆序对”的数量。随机排列的平均逆序对数量是 n(n-1)/4所以平均交换次数也在这个量级依然是 O(n²)。情况比较次数交换次数最好已有序n-1提前退出版0最坏完全逆序n(n-1)/2n(n-1)/2平均随机排列约 n(n-1)/2约 n(n-1)/4这也是冒泡排序一直被诟病的原因它不光比较次数高交换次数同样高。同样是 O(n²)选择排序的交换次数却能控制在 n-1 次这在交换操作比较贵的场景下就是天壤之别。3.3 稳定性一句代码的区别稳定性是排序算法一个容易被初学者忽略的属性。它的定义是如果数组里有两个相等的元素排序后它们的前后相对顺序保持不变这个排序算法就是稳定的。冒泡排序天然是稳定的因为代码里用的是 arr[j] arr[j1] 才交换。两个相等的数字比如两个 7 紧挨着arr[j] arr[j1] 不成立所以它们不会互相交换位置相对顺序自然不会变。但如果你手一抖把大于号改成大于等于写成 arr[j] arr[j1]那排序结果虽然还是有序的稳定性却被破坏了。两个相等的 7 会因为“大于等于”而交换位置相对顺序就变了。这一点在很多面试题里是考点实际开发里如果你要基于多个字段做排序稳定性的影响会更明显。3.4 逆序对冒泡排序行为的关键钥匙“逆序对”这个概念是真正理解冒泡排序效率的钥匙。逆序对指的就是数组中一对下标 i j 但 arr[i] arr[j] 的元素。例如 {3, 1, 2} 里(3,1) 和 (3,2) 是两个逆序对。冒泡排序每次相邻交换都恰好消除一个逆序对左边元素大于右边交换后两者顺序正确且不影响其他元素的相对位置。所以交换次数等于初始逆序对数量。这个结论看起来很普通但它帮你把“数组有多乱”量化了。最坏情况完全逆序的数组逆序对数量是 n(n-1)/2 个最好情况有序数组逆序对数量为 0。理解了逆序对你还会发现冒泡排序和插入排序在“消除逆序对”这件事上其实是完全不同的策略冒泡靠相邻交换一个一个消插入排序则是把元素往前“插”的时候一次跳过多个逆序对。这就是为什么数据量稍大时插入排序通常比冒泡快的原因。4. 调试冒泡排序的翻车现场与三条排查经验4.1 测试数组清单哪些边界一定要试写完了排序函数别急着说“跑通了”。我给自己定了一条规矩任何排序算法都要过一遍下面的测试清单。测试数据预期结果要发现的隐患空数组保持为空循环条件是否正确处理 n0单元素数组 {42}保持 {42}是否误判或越界所有元素相等 {7,7,7,7}保持原顺序比较条件是否会错误交换完全升序 {1,2,3,4,5}保持升序提前退出逻辑是否正确完全降序 {5,4,3,2,1}变成升序交换逻辑是否正确含重复值混合 {2,3,2,1,3}升序且稳定相等值是否保持相对顺序有一个细节值得单独说空数组。如果 n0外层 for (i 0; i n - 1; i) 会变成 i -1在编译器看来这是合理的循环体不会执行通常没问题。但如果你用的是有符号整数比较理论上是安全的反而要注意的是 n 为负数这种不合法输入那应该在最开头用 if (n 1) 直接返回。4.2 最常见的边界Bugarr[j1]越界在我看过的代码里冒泡排序的 bug 十有八九出在内层循环边界上。最常见的越界写法是for (j 0; j n; j) { if (arr[j] arr[j 1]) { // 交换 } }当 j n-1 时arr[j1] 就是 arr[n]而有效下标最大是 n-1。这一下就越界了。C语言不会像 Java 那样抛异常它可能读写到栈上的隔壁变量结果时好时坏属于最难查的那类 bug。另一种隐蔽写法是for (j 0; j n - i; j) { if (arr[j] arr[j 1]) { // 交换 } }当 i0 时j 可以取到 n-1arr[j1] 又是 arr[n]直接越界。正确的写法必须是 j n - 1 - i这样 j 最大取到 n-2-iarr[j1] 最大取到 n-1-i始终在有效范围内。建议你写代码的时候脑子里始终记着“arr[j1] 最大不能超过 arr[n-1]”不管循环条件怎么写都要对这做一次推导。4.3 升序写成降序以及保留等号的问题如果把 if (arr[j] arr[j1]) 改成 if (arr[j] arr[j1])那就从升序变成了降序这是很多人实现“反向排序”时顺手做的改动。逻辑本身没有错但要注意如果你的程序里同时存在升序和降序两种需求最好封装成两个函数或者加一个参数控制比较方向不要靠临时改符号来应付。另外要留意的是当你为了保持稳定性而坚持用严格大于时千万别在优化时把条件顺手改成 。前面说过这会让相同元素的相对顺序改变在某些要求稳定排序的业务场景里会直接导致数据错乱。我有一个朋友在某个数据处理流程里用了自己写的冒泡结果查了半天最后发现就是比较符号多了一个等号。4.4 排错三招打印、随机对照、手工模拟如果排序结果不对我的排查流程基本固定就三招。第一招每轮打印结果。写一个这样的辅助函数void print_array(int arr[], int n) { int i; for (i 0; i n; i) { printf(%d , arr[i]); } printf(\n); }然后在冒泡函数里每一轮结束调用一次。看着打印结果你能立刻看出是哪一轮开始乱掉的非常直观。第二招随机数据对照标准库。C标准库提供了 qsort可以直接拿它当作“标准答案”。写一段测试代码生成大量随机数组分别用自己写的冒泡和 qsort 排序逐一比较结果#include stdio.h #include stdlib.h #include time.h int cmp_int(const void *a, const void *b) { return (*(int *)a - *(int *)b); } void test_bubble() { srand((unsigned)time(NULL)); int arr[100], tmp[100]; int t, i, n; for (t 0; t 1000; t) { n rand() % 30; for (i 0; i n; i) { arr[i] rand() % 100; tmp[i] arr[i]; } bubble_sort(arr, n); qsort(tmp, n, sizeof(int), cmp_int); for (i 0; i n; i) { if (arr[i] ! tmp[i]) { printf(mismatch at test %d\n, t); return; } } } printf(all tests passed\n); }这招最大的价值是可以一次性覆盖大量随机场景专治诡异边界问题。只有测试用例足够多才能验证到你没有想过的角落。第三招手工模拟小数组。把数组长度缩到 3 或 4拿纸笔把每一轮比较和交换写出来和代码的执行路径对照。这个方法“最土”但往往最快定位问题因为小数组人能跟上大数组人脑根本跑不过来。5. 冒泡和它的竞争对手选择排序、插入排序的取舍5.1 同为O(n²)三个算法各打什么牌几乎所有初学者都会被问到“排序算法有哪些”而大家最熟悉的三个 O(n²) 算法就是冒泡、选择和插入。它们各有各的性格。算法最好时间最坏时间稳定性交换次数特点冒泡排序O(n)O(n²)稳定交换次数理论上等于逆序对数量选择排序O(n²)O(n²)不稳定常见实现交换次数最多 n-1极少插入排序O(n)O(n²)稳定移动次数等于逆序对数量但通过移动一批完成选择排序的核心思路是“每轮挑一个最小的放到前面”。它的比较次数固定为 n(n-1)/2但交换次数被压到了 n-1这一点在交换代价很高时非常香。插入排序的核心思路是“维护一个有序前缀新元素往前插”它对基本有序的数据极度友好最好情况 O(n)。冒泡排序呢它的特色是“相邻比较、相邻交换”代码最好讲稳定性天然成立并且加上提前退出后对有序数据也还行。但它的交换次数通常是三者中最高的数据一大就非常吃亏。5.2 小数据量场景下怎么选有一类场景我非常建议直接用冒泡数组长度很小比如不到 20 个元素数据规模对你的程序性能根本没有影响。这时候选择代码最简单、最不容易写错的版本反而是最优决策。为了那几微秒的差距去折腾复杂逻辑性价比太低。如果数组稍微大一点比如几百到几千同时交换操作比较贵——例如数组里存的是结构体交换一次要做大量拷贝——选择排序的优势就出来了因为它总共只需要 n-1 次交换。如果数据基本有序比如很多真实场景中的日志按时间追加后偶尔乱序插入排序会是更好的选择。它的最好情况 O(n)而且实现也不复杂。冒泡的位置就有点像“万金油的教学版”不算最优但理解成本最低。实际生产里用它的人并不多但学它的人很多。5.3 冒泡在教学中的不可替代性我始终觉得冒泡排序在算法教学里的地位是不可替代的。不是因为它在工程里有多强而是因为它把几个最重要的概念一次性呈现在一个简单例子里循环嵌套、边界控制、循环不变量、稳定性、时间复杂度。它能让我们直观看到“每轮确定一个位置”——这是很多复杂算法的共同思路。它能用“相邻交换”讲清楚逆序对和交换次数的关系。它还能通过加一个 swapped 标记直观展示“最好 O(n)、最坏 O(n²)”的时间复杂度差距。这些概念如果直接上快排、归并初学者往往会被递归和信息量淹没。所以我给某学弟的建议一直是冒泡不只是背代码而是把它当成分析算法的训练场。能在冒泡上把“排序算法由哪些部分组成”讲明白的人后面学任何排序都会更快。6. 由冒泡延伸出的两个变体鸡尾酒排序与梳排序6.1 鸡尾酒排序左右交替的冒泡前面在优化部分已经给过鸡尾酒排序的完整代码了这里再补充一点使用心得。它本质还是冒泡只是把“单向冒泡”变成了“双向冒泡”每一轮把最大值放到右边界同时把最小值放到左边界。我实际测试下来对于“一半大数在左、一半小数在右”的数据鸡尾酒排序能比普通冒泡快接近一半。但遇到完全随机的数据提升就没有那么明显因为随机分布没有明显的“方向性”双向走的收益有限。它的另一个好处是左右两个边界 left、right 让比较区间逐渐收窄写的好的话天然就带有“跳过已有序区间”的效果。缺点也很明显代码比普通冒泡长逻辑稍微绕一些不适合作为教学入门。通常我会把它当作“看完冒泡之后的进阶彩蛋”而不是一开始就教。6.2 梳排序拉大间隔的冒泡梳排序是冒泡的一个更激进的变体。冒泡每次只比较相邻元素交换一次只能消除一个逆序对太慢了。梳排序的思路是先用一个比较大的间隔 gap比较相距 gap 的两个元素让大数能快速跨越很多位置然后每轮把 gap 缩小通常是除以 1.3最后 gap 变成 1再做一轮标准冒泡。核心代码大概是这样的void comb_sort(int arr[], int n) { int gap n; int swapped 1; while (gap 1 || swapped) { gap (gap * 10) / 13; if (gap 1) gap 1; swapped 0; int i; for (i 0; i gap n; i) { if (arr[i] arr[i gap]) { int tmp arr[i]; arr[i] arr[i gap]; arr[i gap] tmp; swapped 1; } } } }这里的 (gap * 10) / 13 就是乘上 1/1.3 的近似操作。gap 从 n 起步逐步缩小到 1。当 gap 大的时候远距离元素能迅速“近似的”走上几步大幅减少逆序对数量最后一轮 gap1 时数据已经大体有序标准冒泡的提前退出机制可以很快收工。梳排序的时间复杂度平均大约 O(n²/2^p)其中 p 与缩小因子有关虽然理论上还是 O(n²)但实际表现比冒泡好得多是我自己常写的一个“冒泡家族”实用版本。6.3 学了冒泡之后最值得带走的东西我个人的体会是冒泡排序给我们留下的不是那几行代码而是一套“观察排序算法”的方法。你可以问自己每一轮循环后哪些位置被确定了比较次数和交换次数分别受什么影响它稳定吗为什么它最好和最坏的情况各是什么能把这几个问题在冒泡上答清楚你就已经具备分析任何排序算法的基本功了。接下来学插入排序、快排、归并都会像看同一棵树的枝杈一样清晰。最后再分享一个小技巧如果你写完了冒泡排序不确定效率是否正常可以在主函数里跑一个 10 万元素的随机数组分别用基础版和带 swapped 标记的版本计时。你会非常直观地感受到优化版对数据分布的敏感度这种体验比背任何复杂度分析都有说服力。冒泡排序虽然简单但把它彻底嚼碎了一点都不亏。