Wong Kosheng排序算法是C语言学习中绕不开的第一道门槛，而冒泡排序法又几乎是所有教材默认开篇的第一个算法。我刚开始学C语言的时候，第一次看到冒泡排序的代码只有十来行，心里想“就这？”，可真到自己动手写、动手调试、再讲给别人听的时候，才发现里面藏着的细节远比想象得多。这篇内容，我想把对冒泡排序的理解、踩过的坑、以及在面试和教学里常被追问的点，一次性整理清楚。
这篇内容适合刚接触C语言、想彻底弄懂排序原理的初学者，也适合准备笔试面试前快速过一遍排序基础的同学。我会从算法直觉讲起，再拆代码实现，然后聊复杂度和稳定性，最后把新手最容易翻车的几个地方单独拎出来说。所有代码统一用C语言写，环境不起眼，能编译能运行就行，完全不需要依赖任何花哨的东西。
先给出一个最简单的结论：冒泡排序的思路就是重复地扫描待排序序列，依次比较相邻两个元素的大小，顺序不对就交换，直到整趟下来没有发生任何交换为止。不过这句话背后还藏着“相邻交换凭什么能让全局有序”“标志位优化为什么重要”“稳定排序到底意味着什么”这些问题，这篇就把它们逐个拆开。
1. 冒泡排序到底在做什么：先建立直觉再动手写
1.1 气泡模型的直觉：为什么叫“冒泡”
冒泡排序这个名字非常形象，你可以把数组里的每个元素想象成水底的一个气泡，气泡的“浮力”大小就是元素的数值。相邻两个气泡比一比，数值更大的那个往水面方向浮一格，如此反复，最大的气泡就会一路浮到顶端。
这个类比真正有价值的地方在于，它解释了为什么要做“相邻比较”，而不是随便挑两个元素交换。只有通过相邻元素的两两交换，才能保证每一趟结束时，当前未排序区间里的最大值“恰好”到达最终应该在的位置。这是一种局部操作不断积累，最终形成全局有序的过程。
我在带人入门时，往往会建议先在纸上画一个竖直方向的水面，然后手动推演一趟过程。看着最大值一步一步“浮”到末尾，后续代码里内外层循环的边界为什么那样写，就非常容易理解了。
1.2 一趟冒泡的完整推演
假设数组是 5, 3, 8, 1, 2，目标是从小到大排序。第一趟的过程是这样：
- 比较第1个元素5和第2个元素3，5 > 3，交换，数组变成 3, 5, 8, 1, 2；
- 比较当前第2个元素5和第3个元素8，5 < 8，不需要交换，数组不变；
- 比较第3个元素8和第4个元素1，8 > 1，交换，数组变成 3, 5, 1, 8, 2；
- 比较第4个元素8和第5个元素2，8 > 2，交换，数组变成 3, 5, 1, 2, 8。
第一趟结束，8 这个最大值已经从原来的第3个位置被一路交换到最后一个位置。注意一个细节：第一趟只需要比较4次，也就是 n - 1 次，因为最大值到达末尾后，下一趟完全不需要再碰它。
更值得留意的是，每一趟需要比较的次数都在减少。第二趟只需要在前4个元素里处理，比较3次；第三趟比较2次；第四趟比较1次。于是总比较次数就是 4 + 3 + 2 + 1 = 10，恰好等于 n × (n - 1) / 2。这正是等差数列求和的结果，也是后面推导时间复杂度的重要依据。
1.3 为什么多趟之后序列一定有序
很多人会有疑问：为什么要执行 n - 1 趟？少一趟行不行？答案藏在“最大值归位”这个性质里。
第一趟结束后，整个数组的最大值一定在最后一位，无论它初始在哪个位置，只要它参与相邻比较，就会一路被交换到末尾。第二趟结束后，剩余元素中的最大值，也就是全局次大值，一定会出现在倒数第二位。依此类推，每多执行一趟，就有一个元素固定到它最终应该在的位置。
从数学归纳法的角度理解：每一趟都让无序区间的最大值归位，相当于每一趟都把待排序规模缩小1。当规模从 n 缩小到 1 时，最后一个元素自动处于正确位置，不需要再比较。所以外层循环只需要跑 n - 1 趟，这是由这个“归位”性质直接决定的，不是硬记出来的边界。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 三版代码：从标准写法到更快的优化
2.1 第一版：教科书标准双层循环
最经典的冒泡排序实现如下：
c复制#include <stdio.h>
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 3, 8, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
这段代码的核心就是两个循环加一次三行交换。外层循环控制“一共要执行多少趟”，i 从0取到 n - 2，也就是执行 n - 1 趟。内层循环控制“这一趟比较到哪个位置为止”，j 从0取到 n - 2 - i，因为每一趟都要把已经归位的末尾部分让出来。
新手最容易出现的边界错误，是内层循环写成了 j < n - 1。这样每一趟都会重新比较已经排好的末尾元素，虽然结果可能还是对的，但白白多了很多次比较。哪怕只是学习阶段的代码，也建议从一开始就养成写正确边界的习惯，后面学其他排序算法时会省下很多排查时间。
2.2 第二版：加一个标志位，最好情况直接变成O(n)
标准写法有一个明显的冗余：如果数组本来就有序，比如 1, 2, 3, 4, 5，第一趟跑完你会发现一次交换都没有发生。既然整趟下来没有任何元素需要换位置，说明所有元素都已经处在正确位置，后面几趟完全是在浪费时间。
优化思路是加一个标志位，每一趟开始时置为0，只要发生交换就置为1。这一趟结束后检查这个标志位，如果还是0，就说明本轮没有交换发生，可以直接跳出整个循环：
c复制void bubble_sort_optimized(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (swapped == 0) {
break;
}
}
}
这个优化在面试里几乎必被问到。加了标志位后，最好情况下的时间复杂度从 O(n²) 降到了 O(n)，因为数组已经有序时只需要跑一趟，比较 n - 1 次就可以结束。很多教材讲完标准写法就停了，但面试官更希望听到你能主动说出“可以用标志位提前退出”这一层理解。
2.3 第三版：记录最后一次交换位置，进一步收窄比较区间
标志位版本已经够用，但还藏着一处可以继续优化的空间。看这个例子：数组是 5, 1, 2, 3, 4。第一趟结束后，数组变成 1, 2, 3, 4, 5，最后一次交换发生在第1个元素和第2个元素之间。后面的 2 和 3、3 和 4、4 和 5 其实都没有发生交换，那下一趟内层循环完全没必要从开头比较到末尾，只需要比较到“最后一次发生交换的位置”就够了。
实现方式是用一个变量记录本轮最后一次交换的下标，下一轮的内层循环上限直接取这个值：
c复制void bubble_sort_boundary(int arr[], int n) {
int last_swap_index = n - 1;
while (last_swap_index > 0) {
int current_last = 0;
for (int j = 0; j < last_swap_index; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
current_last = j;
}
}
last_swap_index = current_last;
}
}
每一轮结束后，last_swap_index 记录的就是最后一次交换发生的位置，这个位置之后的元素已经是全局有序的，下一轮完全不需要再碰它们。这个版本在部分有序的数组上能明显减少比较次数，最坏情况仍然是 O(n²)，但实际表现会比经典写法好一些，可以作为面试时的加分项提出来。
2.4 逐行精读：每行代码背后的设计意图
三行交换里的临时变量 temp 是整个算法最关键也最容易出错的地方。很多人问为什么不直接写成 arr[j] = arr[j + 1]; arr[j + 1] = arr[j]，这是典型的错误写法，因为第二行执行时，arr[j] 已经被前面赋值覆盖掉了。三行交换的本质是用临时变量保护旧值，这个思路在后续几乎所有需要交换的场景里都会用到。
外层循环的 i，含义可以理解为“已经归位的元素个数”，也可以理解为“已经完成的趟数”。每完成一趟，末尾就多一个有序元素，所以内层循环的次数是 n - 1 - i。有人喜欢把外层循环写成 for (int i = 1; i < n; i++)，结论一样，但从0开始计数更贴合C语言的数组下标习惯，也不容易把自己绕晕。
还要注意循环里的所有 n - 1 都是从数组下标0开始推导出来的。数组最后一个元素的下标是 n - 1，而相邻比较需要访问 j 和 j + 1，所以 j 的最大值只能是 n - 2，这也就是 j < n - 1 - i 的真正来源。理解这一层，比死记边界条件可靠得多。
3. 复杂度与稳定性：把“为什么”一次搞清楚
3.1 一组数字看懂最好、最坏、平均时间复杂度
直接说结论：冒泡排序的时间复杂度，最好情况是 O(n)，最坏情况是 O(n²)，平均情况也是 O(n²)。
最坏情况对应数组完全逆序，比如 5, 4, 3, 2, 1。每一趟都要把当前最大值交换到末尾，几乎每次比较都伴随交换。比较次数固定为 n(n-1)/2，交换次数也是 n(n-1)/2，两者都是平方级别，所以整体是 O(n²)。
最好情况对应数组已经有序。标准写法依然会傻傻地跑完 n(n-1)/2 次比较，所以标准写法的“最好情况”依然是 O(n²)。但加上标志位优化后，第一趟发现没有交换就退出，比较次数只有 n-1 次，复杂度降到 O(n)。这也是我在前文强调第二版代码不只是“小优化”的原因，它从量级上改变了最好情况的复杂度。
平均情况的分析比较复杂，但结论同样是 O(n²)。一个直观的理解方式是：对一个随机排列的数组，期望的交换次数大约是比较次数的一半，而比较次数本身是平方级别，所以平均复杂度也逃不出平方级。这决定了冒泡排序的应用边界——只适合处理数据量很小的场景，几百个元素以内没有问题，再往上就会明显吃力。
3.2 空间复杂度为什么是O(1)
冒泡排序只需要一个临时变量，加上几个循环变量，这些都是常数级别的额外空间，不随数据规模增长而变化。所以空间复杂度是 O(1)，也被叫做原地排序算法。
这个结论在横向对比其他排序算法时很有用。比如归并排序需要一个与原数组等长的辅助数组来完成合并，空间复杂度是 O(n)。而冒泡排序、选择排序、插入排序这些基础排序都是原地操作，几乎不消耗额外内存。如果你需要在一个内存受限的嵌入式环境里做小规模排序，冒泡排序这种空间优势就非常实在。
3.3 稳定性：相等元素相对顺序为什么不会乱
稳定排序的定义是：如果两个元素值相等，排序之后它们的相对顺序保持与原来的顺序一致。冒泡排序是稳定排序，原因在于比较条件用的是严格大于号 arr[j] > arr[j + 1]，相等时不触发交换，原本在前的那个元素就会继续保持在前面。
这个特性在排序对象不只是简单数字时格外重要。举例来说，一个结构体数组里存了学号和成绩，你想先按成绩排序，同时希望成绩相同的记录仍然按学号顺序排列，这时候就一定要用稳定排序。常见稳定排序除了冒泡，还有插入排序和归并排序，而选择排序和快速排序默认情况下是不稳定的。在真实项目里处理多关键字排序时，我通常会优先选择稳定排序完成第一层排序，避免后面二次排序把前面排好的相对顺序彻底打乱。
4. 实操手记：从编译到调试的完整流程
4.1 环境准备与代码组织建议
学习冒泡排序不需要复杂的工程环境。在 Linux 或 macOS 下直接用系统自带编译器，Windows 下装好开发环境即可，只要能编译运行 C 语言代码，不依赖任何第三方库，这段代码跑起来毫无压力。
实操阶段我有一个习惯：不要一上来就铺一个完整项目结构，先写一个单文件，把排序函数和 main 函数放在一起，跑通了再去考虑模块化拆分。之后可以把排序函数单独放到一个文件里，头文件里声明原型，main 函数只负责调用和打印结果。这样既锻炼函数封装能力，也方便在后续多个小程序里直接复用同一个排序函数。
4.2 打印每一趟状态的调试技巧
理解冒泡排序最笨但最有效的方式，是在每一趟结束后打印当前数组状态。我在学习阶段就是这么干的，看着每一趟“最大值上浮”的过程被完整输出，对算法的理解比任何干巴巴的讲解都深刻。
c复制void bubble_sort_debug(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
printf("第 %d 趟: ", i + 1);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
if (swapped == 0) {
break;
}
}
}
运行这段代码，你能直观看到第一趟后最大数到达末尾，第二趟后次大数停在前一个位置。如果某一个数据下排序结果不对，不用急着怀疑算法，先打印每趟状态，再和手算结果对照，往往一眼就能看出是哪一趟的交换逻辑出了问题。
我在讲解时会建议学生准备纸笔，先把数组抄下来，每做一次比较就用箭头标出交换结果，再和程序输出逐行比照。这招虽然原始，但在学习阶段比盯着屏幕空想高效太多。
4.3 把冒泡排序封装成通用函数
如果想让冒泡排序支持任意类型的数组，在 C 语言里可以用 void 指针加函数指针参数来实现比较逻辑，但这涉及比较深的指针用法，初学者可以暂时往后放。绝大多数场景下，先封装成针对 int 数组的函数已经完全够用。
函数签名上建议写成 bubble_sort(int arr[], int n)，带上数组长度参数。很多人奇怪为什么不在函数内部用 sizeof 算长度，这是因为数组作为函数参数传递时退化成指针，sizeof 拿到的是指针大小，不是数组元素个数。这是 C 语言里非常经典的“坑”，没踩过的人往往只是还没写过自定义数组处理函数。
我在练习阶段还会额外做一个小练习：把冒泡排序改成只排数组的前 k 个元素，或者只排某个区间。做完这个练习，你对数组参数的理解会明显上一个台阶，因为你会发现如果长度和区间不通过参数显式传入，根本没法控制排序范围。
5. 新手高频翻车现场与排查实录
5.1 越界问题：内层循环边界为什么会写错
越界是最常见的崩溃原因。比如有人把内层循环写成 for (int j = 1; j < n - i; j++)，想用 arr[j - 1] 和 arr[j] 比较，但写着写着漏掉 -1，直接比较 arr[j] 和 arr[j + 1]，j 一旦取到 n - 1，就会访问 arr[n]，直接越界。
C 语言不会像高级语言那样给出友好的报错信息，它只会读到数组后面一段垃圾内存。运气好得到错误结果，运气不好程序直接崩溃。我见过最经典的问题是内层循环写成 j < n - 1，外层循环也写成 i < n - 1，结果不崩溃，但内层循环不停比较到 n - 2，把已经排好的区域反复比较，性能很差。排查这类边界问题，最直接的办法还是打印每趟数组状态，看到重复比较的模式，基本就能锁定是边界写错了。
5.2 交换逻辑写错：三种典型错误
交换只有三行代码，出错方式却千奇百怪。第一种是赋值方向写反，把 arr[j] = arr[j + 1] 写成 arr[j + 1] = arr[j]，导致两个相邻位置被覆盖成同一个值，数组中一个元素直接“消失”。第二种是忘记使用临时变量，试图用两行赋值完成交换，旧值被新值覆盖，数据永久丢失。第三种是在 if 外面做交换，导致即使不需要交换也执行交换，排序结果自然一片混乱。
这三种情况我都遇到过，也都帮人排查过。强烈建议把三行交换当成固定模板来记：int temp = a; a = b; b = temp;。排序算法里交换频率很高，一旦写错，很难靠运行结果反向推理出具体是哪个位置出错，所以从一开始就用标准写法最省心。
5.3 边界条件记不住？一个核心原则就够了
很多初学者反复记不住内外层循环边界，我分享一个经验：只需要记住“每趟冒泡让当前最大值归位，已经归位的元素下一趟不再参与比较”这个原则。
在这个原则下，外层循环执行 n - 1 趟，因为前 n - 1 个数归位后，最后一个数自然有序；内层循环的上限是 n - 1 - i，因为前 i 个数已经处于最终位置。每次写代码时问自己一句“这一趟还剩多少未排序元素”，边界就不容易错。如果还是不放心，拿 1, 2, 3 这种很小且有序的数据跑一遍，结果对不对立刻见分晓。
5.4 数据量一大就慢：冒泡排序的适用边界在哪里
O(n²) 的复杂度决定了冒泡排序不适合大规模数据。直观体验一下：排序 10 万个随机整数，快排这类 O(n log n) 算法只需要几十毫秒，冒泡排序可能要几十秒，差距可以达到几百上千倍。真实开发里数据量一大，直接调用库函数或者使用快速排序、堆排序这类高效算法才是正路。
但冒泡排序并非一无是处。它的位置集中在教学入门、小规模数据排序、以及那些对代码可读性要求很高的场景里。面试场合如果被要求手写排序，你能写出带标志位优化的版本，并清楚解释时间复杂度和稳定性，就已经比只会背标准代码的候选人强不少。
从更大的视角看，先吃透冒泡排序，后面学选择排序、插入排序、快速排序时，你会发现它们的基本框架都是“遍历 + 比较 + 交换”，差别只在策略。冒泡排序打下的基础，会在理解更复杂排序算法的路上持续发挥作用。
我个人在学习和带人过程中的体会是，冒泡排序是最值得花时间弄懂的“第一课”。它代码短、逻辑直白、结果容易验证，用来建立对排序问题的整体直觉再合适不过。学的时候多问几个为什么，后面接触任何排序算法都不会慌。
最后再分享一个小技巧：手写冒泡排序时，可以顺手用字符串数组再实现一遍，把数字比较换成字符串比较函数。这个练习能一次性锻炼数组、字符串、函数参数多个知识点的综合运用，比单纯背排序模板有意思得多。