★ FEATURED ARTICLE 1. 先聊清楚为什么我们还在讨论冒泡排序每次数据结构课讲到排序总有人第一反应是“冒泡排序不是最没用那个吗”。说实话这种看法有一定道理——它的平均时间复杂度是O(n²)在十万级数据面前会跑得让人怀疑人生。但作为一个写了多年C语言的开发老手我得说一句公道话冒泡排序在被无数人嫌弃的同时恰恰是理解排序思想最好的入门教材而且它在链表场景下有独特的用武之地。这个标题其实拆开来看是三个递进的需求第一用最简单的思路实现“能跑”的冒泡排序第二在这个基础上做优化让效率从“完全不能看”提升到“小数据量还可以接受”第三把它移植到链表结构上解决数组无法动态增删的痛点。这篇文章想覆盖的读者大概是两类人一类是刚学C语言、正在和指针与数组搏斗的初学者另一类是已经会写链表、但总感觉“数组排序我会链表排序就懵”的进阶学习者。顺便说一句我在实际教学和代码评审里见过很多次这样的情况一个同学能把数组版冒泡排序倒背如流但一让他对链表排序立刻卡壳。问题往往不在排序本身而在于他没有意识到“数组版排序的本质是对下标的操作而链表版排序的本质是对节点关系的操作”。一句话点破后面所有代码都会顺起来。2. 经典版冒泡排序先把“能跑”做到位2.1 冒泡排序到底在做什么一趟一趟地把大数“顶”到末尾冒泡排序的核心思想用大白话说就是从头开始两两比较相邻元素如果前一个比后一个大就交换位置。这样每一趟下来最大的那个数就像气泡一样浮到了当前范围的最后面。下一趟再从头开始但不需要再碰那个已经归位的最大值。为了让你彻底明白这个过程我拿一个只有5个元素的数组举个例子{5, 1, 4, 2, 8}。第一趟开始比较5和15更大交换数组变成{1, 5, 4, 2, 8}接着比较5和4交换变成{1, 4, 5, 2, 8}比较5和2交换变成{1, 4, 2, 5, 8}比较5和8不用交换。第一趟结束最大值8已经在最后一位这一趟总共比较了4次。第二趟只需要处理前4个元素。比较1和4不交换比较4和2交换数组变成{1, 2, 4, 5, 8}比较4和5不交换。第二趟结束5归位。第三趟处理前3个元素1和2比一次2和4比一次没有任何交换。发现整个数组已经有序了。从这里你也能隐约看到优化的方向如果某一趟完全没发生交换说明已经有序可以直接结束。2.2 经典版代码双层循环的完整实现代码永远是第一位的。下面是最标准的数组版经典冒泡排序我加了详细的注释尤其是边界条件那一块建议初学者放慢速度一行一行读#include stdio.h // 经典冒泡排序对数组 arr 中的 n 个元素升序排列 void bubble_sort(int arr[], int n) { int i, j; int temp; // 外层循环控制“趟数”一共最多需要 n-1 趟 // 为什么是 n-1因为每趟最多归位一个元素 // 前 n-1 个元素都归位了最后一个自然就位了。 for (i 0; i n - 1; i) { // 内层循环负责比较相邻元素 // 注意上界是 n - 1 - i // 每一趟结束后末尾的 i 个元素已经有序 // 所以不需要再去碰它们。 for (j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { // 交换 temp arr[j]; arr[j] arr[j 1]; temp arr[j 1]; // 这一行是错的下面有解释 } } } }停一下我刚故意在交换那里埋了一个初学者经常写错的地方第三行赋值写成了temp arr[j 1]。如果真这么写数组会被两个相同的值覆盖排序直接失效。正确的交换是if (arr[j] arr[j 1]) { temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; }很多人第一次写交换都会栽在这种地方这不是智力问题而是敲代码的时候手速远快于脑速。我的建议是交换三行永远用同样的顺序写形成肌肉记忆——“temp存前一个前一个被后一个覆盖后一个拿temp的值”。再看整个双层循环的执行过程。外层跑第0趟时内层会从j0一直比较到jn-2把最大的数送到arr[n-1]外层跑第1趟时内层上界变成n-2把次大的数送到arr[n-2]。整个过程像不像每次捞起一桶水里最大的石子放到岸边这就是“冒泡”这个名字的来历。2.3 用main函数验证一遍看你真的跑对了没有只有排序函数还不够代码能不能跑得用一个完整程序验证。我建议你直接复制下面这段编译运行看看结果#include stdio.h void bubble_sort(int arr[], int n) { int i, j; int temp; for (i 0; i n - 1; i) { for (j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } } int main(void) { int arr[] {5, 1, 4, 2, 8}; int n sizeof(arr) / sizeof(arr[0]); int i; printf(排序前); for (i 0; i n; i) printf(%d , arr[i]); printf(\n); bubble_sort(arr, n); printf(排序后); for (i 0; i n; i) printf(%d , arr[i]); printf(\n); return 0; }运行结果应该是排序前5 1 4 2 8 排序后1 2 4 5 8如果你得到的是这个结果说明经典版已经通关了。sizeof(arr) / sizeof(arr[0])这个写法要记住它是C语言里获取数组长度的惯用方式等于数组总字节数除以单个元素字节数。不过它只能在数组定义所在的函数里用一旦数组作为参数传进函数退化成指针后这个写法就失效了——这也是初学者经常踩的第二个坑。经典版到这里算是讲完了。它的代码足够简单逻辑也足够清晰但效率的确不高哪怕数组已经有序它也会傻乎乎地跑完所有趟数。接下来要聊的优化核心思路就是“别做无用功”。3. 优化版冒泡排序把“白做的比较”剪掉3.1 第一刀加一个标志位这一趟没交换就直接收工经典版最招人恨的地方就是它不管数据状态如何永远老老实实比较n-1趟。假设给你一个已经排好序的数组{1, 2, 3, 4, 5}经典版依然会跑完4趟每趟做4次、3次、2次、1次比较一共10次白做的比较。优化思路非常直观如果在某一趟完整的内层循环里一次交换都没有发生那就说明数组已经是全局有序的后面几趟全是浪费直接跳出即可。实现这个逻辑只需要一个flag变量#include stdio.h // 第一版优化加标志位有序时提前终止 void bubble_sort_opt1(int arr[], int n) { int i, j; int temp; int flag; // 记录本趟是否发生了交换 for (i 0; i n - 1; i) { flag 0; // 每趟开始前重置为0 for (j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; flag 1; // 只要发生交换就置为1 } } // 如果整个一趟都没有交换说明已经有序 if (flag 0) break; } }这段代码的性能变化在哪里对于一个已经有序的数组{1, 2, 3, 4, 5}第一趟4次比较全都不触发交换flag为0直接跳出总共只做了4次比较。从10次降到4次其实就是把最佳情况的时间复杂度从O(n²)降到了O(n)。但要注意这个优化对“乱序但没完全乱”的数据帮助有限。比如数组{2, 1, 3, 4, 5}第一趟把2和1交换然后后面几组有序flag为1不能提前退出第二趟比较时数据已经有序才会退出。你依然要跑完约两趟。真正的好处是当数据接近有序时它能节省大量比较次数。3.2 第二刀记录最后一次交换的位置缩紧无序区的边界标志位优化解决的是“整体有序”的问题但现实中更常见的是“前半段无序、后半段已经有序”的情况。比如数组{5, 1, 2, 3, 4}第一趟结束后的状态是{1, 2, 3, 4, 5}后面全部有序flag优化能在第二趟刚开始就退出。这没问题。可如果是{3, 2, 1, 4, 5, 6, 7}这种后面一大截早就序的数组情况就没那么美好了。经典版的内层循环上界是n-1-i它的假设是“每趟结束一定会在末尾新增一个有序元素”。但如果后半段本来就有序这些比较全都白做了。优化思路是用变量last_swap记录本趟最后一次交换发生的下标下一趟的内层循环只需要跑到这个位置即可因为这个位置之后的元素已经不需要再动了。这个优化在算法领域有一个正经名字叫“有序边界收缩”实现如下#include stdio.h // 第二版优化记录最后一次交换位置收缩比较边界 void bubble_sort_opt2(int arr[], int n) { int i, j; int temp; int flag; int last_swap; // 记录本趟最后一次交换发生的下标 int border n - 1; // 下一趟需要比较到的最大下标 for (i 0; i n - 1; i) { flag 0; last_swap 0; // 内层只需要跑到 border for (j 0; j border; j) { if (arr[j] arr[j 1]) { temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; flag 1; last_swap j; // 记录交换位置 } } // 更新边界下次只跑到最后一次交换的位置 border last_swap; if (flag 0) break; } }注意两个细节第一last_swap记录的是j而不是j1因为下一趟还需要比较到last_swap1这个元素如果把边界设成last_swap1效果其实也可以但直接在代码里记录j更直觉化第二如果某一趟完全没有交换border会变成0外层循环跑完当前趟后flag0退出安全收场。这个优化在处理“大部分已经有序但开头乱了一下”的数据时效果极其明显。举个例子{7, 1, 2, 3, 4, 5, 6}这种数据第一趟会把7一路交换到末尾last_swap记录到5下一趟只需跑到5很快就会发现没交换然后退出。整体比较次数比经典版少很多。3.3 第三刀双向冒泡也就是“鸡尾酒排序”还有一种在冒泡优化里经常被提到的方案叫“鸡尾酒排序”也叫双向冒泡。它的思路是普通冒泡每趟只从前往后最大值沉底鸡尾酒排序在此基础上再从后往前跑一趟让最小值也浮到开头。相当于一趟“来回”。为什么要这么做你想想一个极端场景数组{2, 3, 4, 5, 6, 7, 1}最小值1在最后面。普通冒泡第一趟把7送到最后第二趟把6送到倒数第二直到第6趟才把1送到开头。明明只有1一个数位置不对却几乎跑满所有趟数。鸡尾酒排序则会在第一轮从后往前的过程中就把1送到最前面效率立竿见影。#include stdio.h // 鸡尾酒排序双向冒泡适合“小数在末尾、大数在开头”的数据 void cocktail_sort(int arr[], int n) { int left 0, right n - 1; int i, temp; int flag; while (left right) { flag 0; // 从左向右把大数送到 right 位置 for (i left; i right; i) { if (arr[i] arr[i 1]) { temp arr[i]; arr[i] arr[i 1]; arr[i 1] temp; flag 1; } } right--; // 右侧最大值已经归位 // 从右向左把小数送到 left 位置 for (i right; i left; i--) { if (arr[i - 1] arr[i]) { temp arr[i - 1]; arr[i - 1] arr[i]; arr[i] temp; flag 1; } } left; // 左侧最小值已经归位 if (flag 0) break; } }鸡尾酒排序并不是银弹它的代码复杂度比前面的优化版高在数据随机分布时优势也不明显。它最值钱的场景就是“大多数元素已经有序但少量小值/大值分布在错误的一端”。所以我的建议是日常练习一定要把鸡尾酒排序写一遍因为它是理解“双向扫描”思想的好素材但工程选择上不必迷信它。3.4 优化版实测到底快在哪、慢在哪光说不练假把式。我用一个长度为10的数组做了个简单的对比实验数据用伪随机生成结果大致如下表排序版本10个随机整数比较次数100个接近有序数据的比较次数代码复杂度经典版454950低标志位优化35~40数据相关约1000低边界收缩优化35~40数据相关约300中鸡尾酒排序30~40数据相关约500中注意这张表不是精确基准而是用来展示一个趋势数据越接近有序优化版的优势越明显数据完全随机时几种优化版提升有限因为每一趟基本都会发生交换无法提前止损。这也说明了一个重要的选型原则——优化要针对数据的实际特征来选而不是盲目堆代码。4. 链表上的冒泡排序让指针也学会冒泡4.1 为什么链表排序不能照抄数组版好消息是冒泡排序的核心思想——两两比较相邻元素并交换——在链表上完全适用。坏消息是如果你直接把数组版的写法搬过来会发现根本没法写因为链表的“相邻元素”不靠下标访问而是靠指针next链接。并且链表不能像数组那样用arr[j]和arr[j1]直接取值你必须在每一次比较前先遍历到目标节点。链表排序有两种常见策略一种是交换节点的数据另一种是交换节点本身也就是调整指针指向。两者的取舍很关键交换数据代码简单只动data字段不需要动指针代价是如果节点里存的不是int而是结构体大对象反复复制数据开销会很大。交换节点代码复杂需要处理prev、cur、next之间的指针关系优势是只改指针不复制数据适合节点携带大数据或资源句柄的场景。我个人的建议学习阶段先用“交换数据”把算法跑通理解冒泡规律后再挑战“交换节点”。直接一上来就写指针交换版很容易被指针绕晕然后连排序逻辑都忘光了。4.2 交换节点数据的链表冒泡排序最容易上手的写法先定义单链表节点结构#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node;交换数据的链表冒泡排序思路是外层循环控制趟数每趟从头节点开始用两个指针p和q指向相邻节点比较p-data和q-data如果顺序不对就只交换data字段。为了保证每趟能“少走一段路”我用一个指针end来标记已经归位的链表尾节点每趟结束后让end前移一个节点。void bubble_sort_list_data(Node *head) { if (head NULL) return; Node *end NULL; // 已排序部分的边界初始为NULL表示还没元素归位 Node *p; int temp; int swapped; // 当 end 还没到第二个节点时继续 // 注意条件判断end 一开始是NULL循环内要让 p 跑到 end 前一个位置停 while (end ! head-next) { swapped 0; p head; // 每趟从头部开始比较相邻两个节点 // 终止条件是 p-next 到达 end while (p-next ! end) { // p 和 p-next 就是相邻的两个节点 if (p-data p-next-data) { temp p-data; p-data p-next-data; p-next-data temp; swapped 1; } p p-next; } // end 前移最后那个节点已经归位下次不用再碰它 end p; if (!swapped) break; } }这段代码里最需要理解的是end指针的移动逻辑。数组版靠i来实现“每趟少比较一个元素”链表版就靠end。一开始end NULL内层循环会一直跑到链表的NULL结尾第一趟结束后p停在原链表的最后一个节点上然后end p于是下一趟内层循环跑到这个节点就停相当于把最后一个元素锁死。这里有一个经典的边界坑while (end ! head-next)这个条件。为什么不是end ! NULL因为当链表只有1个节点的时候head-next NULL如果写成while (end ! NULL)循环条件成立内层while (p-next ! end)判断p-next ! NULL只有一个节点时p-next为NULL内层一次都不执行然后end p变成head外层下一次发现end ! NULL不成立退出去。所以两种写法都能跑但end ! head-next的逻辑更规范它表达的是“已排序边界还没撞上第二个节点就继续”。4.3 交换链表节点的冒泡排序指针重接的关键细节如果你觉得交换数据太“取巧”想真正练指针操作那就得写交换节点版。难点在于交换两个相邻节点时必须让前一个节点的next、被交换节点的next都正确重接。尤其要注意如果被交换的两个节点靠近链表头部可能还需要动态调整head指针本身。我先给一个稳妥的写法使用“三指针遍历法”每次记录prev、a、b三个节点其中a和b是待比较的相邻节点prev是a前面的节点。如果a-data b-data就把b从a后面挪到prev后面再让a-next指向b-next。这套操作本质是把相邻节点b插入到a前面。void bubble_sort_list_swap(Node **head_ref) { Node *head *head_ref; if (head NULL || head-next NULL) return; Node *end NULL; Node *prev, *a, *b; int swapped; while (end ! head-next) { swapped 0; prev NULL; a head; b head-next; while (b ! end) // b 不越过已排序边界 { if (a-data b-data) { // 情况1a 就在链表头部要更新 head if (prev NULL) { head b; } else { prev-next b; } // 交换相邻节点 // 原来prev - a - b - b-next // 现在prev - b - a - b-next a-next b-next; b-next a; // 交换后a 和 b 的角色互换但下一轮仍然从 b 的前一个开始 // 不这里直接移动指针 // prev 在交换后应该指向 b已经就位 // a 变成被挪到后面的那个节点需要继续和下一个节点比较。 prev b; a b-next; // 注意这个时候 a 已经在 b 的后面 b a-next; swapped 1; } else { // 不交换三个指针整体后移 prev a; a b; b b-next; } } end a; // 一趟结束后a 是最后一个被比较到的节点 if (!swapped) break; } *head_ref head; }读到这里你会发现指针交换版比数据交换版难在“交换后指针怎么移”这一步。我刚开始写这版代码时也栽过好几次跟头最典型的问题是交换后b指针指向了错误的位置导致下一轮循环跳过了某个节点或者死循环。我的调试经验是先在纸上画出prev - a - b的前后变化图再对着图写代码每一步都问自己“这个节点的next现在指向谁”。比对着代码猜来猜去高效得多。还有一点非常重要这个函数接收的是Node **head_ref而不是Node *head因为交换可能改变链表头节点如果你传Node *head进去即使函数内部把头节点换了外面的指针还是旧的链表就“丢了”。这就是C语言里“要修改指针本身就要传指针的指针”的典型应用。4.4 链表版冒泡排序的完整测试程序代码写完了还是那句话得跑起来才算数。下面是一个完整的测试程序包含链表创建、打印、调用两种排序算法的逻辑#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 尾插法建立链表 Node *create_list(int arr[], int n) { Node *head NULL; Node *tail NULL; int i; for (i 0; i n; i) { Node *new_node (Node *)malloc(sizeof(Node)); new_node-data arr[i]; new_node-next NULL; if (head NULL) { head new_node; tail new_node; } else { tail-next new_node; tail new_node; } } return head; } void print_list(Node *head) { while (head ! NULL) { printf(%d , head-data); head head-next; } printf(\n); } // 这里放冒泡排序函数数据交换版或节点交换版 void bubble_sort_list_data(Node *head) { // 见前文实现省略具体内容 } void free_list(Node *head) { Node *tmp; while (head ! NULL) { tmp head; head head-next; free(tmp); } } int main(void) { int arr[] {9, 2, 5, 1, 8, 3, 7, 4, 6, 0}; int n sizeof(arr) / sizeof(arr[0]); Node *head create_list(arr, n); printf(排序前); print_list(head); bubble_sort_list_data(head); printf(排序后); print_list(head); free_list(head); return 0; }如果你用的是节点交换版记得在main里调用时写成bubble_sort_list_swap(head);否则头指针一旦被换后面打印就会出错。这个“传地址”的细节是链表操作中非常高频的失误点。5. 复杂度、稳定性与真实工程里的取舍5.1 看透时间复杂度的本质比较次数和交换次数很多人背过“冒泡排序时间复杂度O(n²)”但问一句“为什么是O(n²)”就答不上来。这里用最直白的方式拆一下。经典版本外层i从0跑到n-2内层j从0跑到n-2-i。所有趟数加起来比较总次数是第0趟n-1次 第1趟n-2次 第2趟n-3次 …… 最后一趟1次总和 (n-1) (n-2) ... 1 n(n-1)/2。当n很大时n(n-1)/2约等于n²/2所以时间复杂度是O(n²)。要注意这个复杂度与数据是否有序无关因为经典版不管什么数据都要跑满所有趟数。而加了标志位后最好情况下天然有序第一趟跑完n-1次比较就能退出复杂度降为O(n)最坏情况依然是O(n²)因为每趟都有交换无法提前退出。平均复杂度也是O(n²)数学上可以通过逆序数来证明每次交换都会消除一个逆序对而随机数组的逆序对期望数量是n(n-1)/4左右所以平均情况下的交换次数大约是O(n²)量级。5.2 稳定性冒泡排序的“传家宝”排序算法的稳定性说的是如果两个元素的值相同排序后它们的相对顺序是否保持不变。冒泡排序是稳定排序因为它的交换条件是严格大于不是大于等于。当两个相邻元素相等时它们不会发生交换因此相同值的先后顺序不会被破坏。这一点在工程上特别重要。假设你有一个学生名单先按学号排序再按成绩排序你希望第二次排序后成绩相同的学生仍然保持学号顺序——那你就必须用稳定排序。冒泡排序的“不出名”不等于“没用”它的稳定性在某些场景里就是比快速排序这种不稳定排序更合适。5.3 现实世界里该怎么选冒泡不是万能但也不是一无是处我经常被学生问老师既然有更快的排序算法我们为什么还要花时间学冒泡这个问题问得很好答案有三个层面。第一冒泡排序是理解“交换类排序”的最佳起点。它的代码逻辑几乎是线性的比较相邻、交换、重复。学会了它你再看选择排序、插入排序、快速排序都能找到共同点和差异点学习曲线会平滑很多。第二冒泡排序在小规模数据和近乎有序的数据上并非毫无竞争力。比如一个文件里只有几十条记录需要排序O(n²)和O(n log n)的差别可能连1毫秒都不到但代码的简单性和可维护性却是实打实的优势。没必要杀鸡用牛刀。第三链表排序时冒泡的实现难度远低于快速排序或归并排序。链表快速排序对随机访问有要求归并排序虽然理论上很适合链表但实现细节多、边界条件复杂。相比之下冒泡排序能让你用最少的代码把“链表排序”这个任务啃下来。用一张表总结一下三种场景的排序选择场景推荐排序原因数据量小少于几十冒泡/插入排序代码简单性能差异可忽略数据几乎有序插入排序或优化版冒泡接近线性时间数据量大且随机快速排序/归并排序O(n log n)更适合大规模数据链表结构且只求能跑链表冒泡排序容易实现降低调试成本链表且要求高性能链表归并排序稳定且平均O(n log n)6. 写在最后一些调试心得和给新手的额外嘱咐分享几个我在教学和实际开发中总结出来的经验希望能帮你在动手实现时少走弯路。如果你是在学数组版冒泡建议先用一个超小数组比如5个元素手动模拟一遍排序过程拿笔在纸上画出每一趟的状态。我教过的很多学生代码反复改不对最后发现根本原因是对“每一趟到底比较到哪一位”没想清楚。纸上画三轮比debug一小时都管用。如果你在做链表版冒泡强烈建议在主函数里先造一个只有两三个节点的链表来测试。链表排序最常见的bug有两个一是指针错位导致死循环解决办法是在每个循环末尾打印当前链表内容用printf做“过程可视化”二是忘记处理头节点的改变解决办法是确认函数签名用不用Node **。这两个问题只要提前注意基本不会耗太长时间。最后说一个容易被忽略的点内存管理。链表创建时用了malloc程序结束前一定要free否则在跑较大规模测试时会出现内存泄漏。很多初学者在练习时觉得无所谓但养成随手释放内存的习惯对后续学习其他数据结构非常有帮助。冒泡排序并不复杂但它是很多算法思想的载体相邻比较、交换、稳定性、边界收缩、有序区收缩、指针操作这些概念全都能在“用C语言实现冒泡排序”这个小项目里得到训练。把它当作一个“练手容器”去做你会收获比排序本身多得多的东西。
阅读完成 · 觉得有帮助？
