简介针对C语言链表排序的示例工程面向需要掌握链表结构与基础排序算法的初学者以完整可编译的方式组织适合课后练习、课程设计或面试复习。压缩包共四个文件包含一个C语言源文件、一个工程配置文件、一个用户选项文件和一个筛选器文件整体体积约三千字节轻量紧凑。已有一千八百七十五人学习。源码从链表的基本概念出发先讲解节点的数据域与指针域再逐步演示动态节点的创建、插入、删除和遍历显示排序环节分别给出冒泡排序与快速排序两种实现帮助初学者对比相邻交换与递归分治的过程。配合调试器观察每个节点的指针变化可直观理解内存地址衔接、动态分配与释放以及分治策略在链表上的实际应用。作者将功能划分为初始化、插入、删除、显示、排序等独立函数结构清晰非常适合本科生、职校生在课后实践与课程设计中作为参考。 我最早意识到“链表排序”和“数组排序”不是一回事是在一次笔试里明明把快排背得滚瓜烂熟结果面对一个单链表手里的代码愣是不知道怎么下手。后来工作了真正写嵌入式、写C服务才发现链表排序是个特别能暴露基本功的场景——你懂不懂指针、懂不懂内存、懂不懂边界条件写一次链表排序全照出来了。这篇文章就从我这几年写 C 语言链表排序的实战经验出发把单链表排序的几种主流玩法掰开揉碎地讲一遍。不搞花架子直接上代码、上对比、上踩坑记录。适合刚学完链表基础、准备刷数据结构题的人也适合工作里要手写内核链表排序、C 笔试题总在链表上栽跟头的人。1. 为什么数组排序那套不能直接照搬到链表——先理解两者的寻址差异很多人一开始会想我把数组里的冒泡、选择、快排、归并搬到链表上不就行了吗理论上是但你要是真动手会发现第一步就卡住了链表没有随机访问能力。1.1 数组能做到的链表做不到数组排序能随便写arr[i]、arr[j]因为数组在内存里是连续排布的CPU 可以直接通过“基地址 偏移量”跳到任意位置。链表靠的是一个个节点通过指针串起来你只能从头节点开始一路p p-next走到底。这意味着什么意味着两件事第一你没法直接取“中间元素”。哪怕你知道链表有 100 个节点你也得从头数 50 次才能摸到第 50 个节点。所以快排那种“选基准值然后两边同时扫”的玩法在单链表上写起来非常别扭因为你的两个游标没法同时从两头往中间走。第二交换两个“位置”上的元素代价完全不一样。数组里交换两个元素就是开个临时变量然后拷三下链表里如果交换的是两个节点的值倒也能这么干但如果交换的是两个节点本身也就是把节点在链表中的位置调换你得同时处理四个指针前驱节点的 next、当前节点的 next、后一个节点的前驱、后一个节点自己的 next。稍有疏忽就断链。1.2 冒泡、选择、快排搬到链表的“变形”空间虽说数组那套不能照搬但也不是完全不能移植只是每个算法都要针对链表结构做变形冒泡排序核心是相邻元素比较并交换。链表里“相邻元素”是现成的每个节点都带着next指针天然就是相邻关系。所以冒泡在链表上反而比较好写只是同样要区分“交换值”和“交换节点”。选择排序核心是每轮找最小值放到最前面。链表上也能做从头到尾遍历找最小节点找到后就把它跟当前位置的节点交换。但这里有个问题如果你交换的是节点本身那“当前位置”的前驱指针维护起来非常麻烦。快排核心是分治 基准值。链表上做快排不是不行常见做法是“只交换值、不动节点”把基准值放到某个位置然后根据值大小做分区但实际的移动逻辑比数组复杂不少而且快排在链表上对基准值的选择更敏感搞不好就退化。归并排序核心是“先拆分、再合并”天生适合链表——拆分靠的是遍历和断链合并靠的是改 next 指针都不需要随机访问。所以后来业界标准答案基本都是“链表排序用归并”不是没道理的。我自己实际项目里用得最多的也是归并但笔试场景下面试官有时候就让你写个“单链表冒泡”或“单链表选择排序”。所以下面我把三种路线都详细讲一遍各位可以根据场景选。2. 值交换法选择排序在单链表上的直接移植先把最简单、最不容易出错的一种讲清楚交换两个节点的数据域而不是交换节点本身。这种思路写起来最贴近写数组排序的手感特别适合思路还没完全打开的新手。2.1 选择排序实现不带头节点也要清爽假设链表节点定义为typedef struct Node { int data; struct Node *next; } Node;选择排序的思路是每一轮从当前位置p开始往后找出值最小的节点min然后把p-data和min-data交换。由于我们不移动节点只交换值不需要维护任何前驱指针断链风险基本为零。直接看代码void selectionSort(Node *head) { Node *p, *q, *min; int tmp; for (p head; p ! NULL; p p-next) { min p; for (q p-next; q ! NULL; q q-next) { if (q-data min-data) { min q; } } if (min ! p) { tmp p-data; p-data min-data; min-data tmp; } } }这段代码走两遍外层循环p指向当前要确定最终位置的节点。内层循环q从p-next开始往后扫一边扫一边记录当前遇到的最小节点min。一轮结束后把p的值和min的值一换这个位置就排好了。时间复杂度是 O(n²)因为每轮都要从当前位置往后全扫一遍。空间复杂度 O(1)只开了一个临时变量tmp。对于数据量不大的链表这个写法其实是够用的。2.2 为什么值交换被很多人诟病我却建议先写一遍业界不少老手一听“交换数据域”就摇头理由是如果节点存的不是简单的 int而是一个很大的结构体每次交换都要拷贝整个结构体性能非常难看。这个批评是对的但我觉得得分场景。我面试实习生、校招生的时候反而比较喜欢看对方能不能先写出“值交换”版。为什么因为排序的核心逻辑是独立的你先想清楚“链表怎么遍历、怎么找最小值、怎么比较”比一上来就纠结指针操作更重要。值交换版把排序主逻辑和指针操作解耦了是很好的思维训练。而且在很多场景下节点数据真就是一个 int 或者一个 float交换值一点问题都没有。比如你给一个整数链表排序根本犯不上去搞指针交换那套复杂的操作。注意值交换的适用前提是节点的数据域可以被安全拷贝。如果数据域里有指针、堆内存、互斥锁这类资源就不能简单赋值否则浅拷贝会把多个节点指向同一块内存释放的时候直接 double free。这种情况我后面第 4 部分会用实际案例展开。如果你只是为了快速写对一道题或者链表节点只存简单值类型值交换法就是你的最优解。如果你要面对的是结构体节点、链表很长、性能要求高那就看下面两种。3. 指针交换法把“搬数据”变成“改线”既然值交换有可能拷贝成本太高那自然就想到了另一种思路节点不动数据动 next 指针让节点在链表里的位置重新排列。这就是“指针交换法”或者说“节点交换法”。3.1 带头节点的双指针操作逻辑指针交换最麻烦的地方是你要交换两个节点必须先找到它们各自的前驱节点。因为链表的连接是单向的改 a 和 b 的位置实际上改的是“a 前驱的 next”和“b 前驱的 next”顺便还要处理 a、b 自身的 next。这里我强烈建议使用带头节点的链表。头节点是个哑节点不存有效数据只是为了让“第一个有效节点的前驱”永远存在这样你处理头部交换时不需要单独特判。这个经验是我在项目里写链表查了半天 bug 后总结出来的带头节点真的能省掉一大部分 if 分支。比如要把节点 x 和节点 y 交换假设 x 在 y 前面x_pre 是 x 的前驱y_pre 是 y 的前驱。交换逻辑是void swapNodes(Node *x_pre, Node *x, Node *y_pre, Node *y) { if (x-next y) { // 相邻节点直接换 x_pre-next y; x-next y-next; y-next x; } else { Node *tmp y-next; x_pre-next y; y-next x-next; y_pre-next x; x-next tmp; } }注意我在这里分了两类情况相邻节点交换和不相邻节点交换。为什么要分因为相邻交换时y 的前驱恰好就是 x你如果套用不相邻的逻辑y_pre 和 x 是同一个节点先改y_pre-next x会对同一个指针重复赋值结果就乱了。这是新手写指针交换最容易踩的坑以为通用逻辑能覆盖所有情况结果相邻节点一出链表直接变成环或者丢节点。3.2 边界条件与断链风险指针交换法看着不复杂但边界条件一个都不能漏。第一个边界待交换节点是头节点。如果你用的是不带头节点的链表要交换头节点和另一个节点你的参数列表就必须传入二级指针Node **head因为头节点本身可能被换走。很多笔试题里大家都写成void sort(Node *head)一出现头节点交换就直接丢链问题就出在这。带头节点之后头节点永远不会被换走哑节点永远是第一个节点问题自动消失。第二个边界空链表和单节点链表。这两种情况不需要排序直接返回。所以在排序函数开头一定要判断if (head NULL || head-next NULL) { return head; }这个判断写不写在一些在线判题系统里就是 100 分和 0 分的区别。空指针解引用是 C 语言崩得最快的一种死法。第三个边界链表的尾节点 next 必须置空。交换节点过程中尤其是非相邻交换很容易把某个节点的 next 指到不该指的地方。我调这种 bug 时一般的做法是每次 swap 操作后立刻打印整个链表确认没有环、没有尾节点还指着旧对象。虽然粗暴但排查效率特别高。指针交换版的冒泡排序、选择排序写起来代码量比值交换版大不少但它的优势也很明显不管节点数据多大交换操作都只动指针O(1) 拷贝量。如果你写的是嵌入式程序节点关联着外设缓冲区指针那你几乎只能选指针交换。4. 归并排序链表排序的工程最优解如果说值交换适合教学、指针交换适合中等规模链表那面对大规模、长链路排序我最推荐的还是归并排序。这也是我在嵌入式项目里给一个几千节点的状态链表排序时最后落地的方案。4.1 快慢指针找中点这一招归并排序的第一步是“把链表从中间拆成两半”。数组可以直接按下标取中点链表做不到所以要用“快慢指针”快指针一次走两步慢指针一次走一步当快指针走到尾时慢指针正好在中间附近。很多刚学的人问为什么快指针走两步、慢指针走一步最后慢指针就是中点因为你把链表想象成一条跑道快指针速度是慢指针的两倍同一个起点出发当快跑完全程时慢正好跑了一半。这个类比想明白代码就是一瞬间的事Node *getMiddle(Node *head) { Node *slow head; Node *fast head; while (fast-next ! NULL fast-next-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }注意上面返回的是前半段的最后一个节点而不是后半段的第一个节点。拿到mid之后做一次断链Node *right mid-next; mid-next NULL;这样原链表就被 split 成了两个独立链表从头到 mid 是左半段从 right 到末尾是右半段。断链这步很关键不断的话后面两个链表各自归并时会串在一起。4.2 不分配额外节点的合并方法归并的“合”是重头戏。数组归并通常要开一个临时数组来放合并结果链表的优势就来了你可以完全不申请新节点只靠改 next 指针把两个有序链表串起来。合并两个已有序的链表核心逻辑是双指针走起Node *merge(Node *a, Node *b) { Node dummy; Node *tail dummy; dummy.next NULL; while (a ! NULL b ! NULL) { if (a-data b-data) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next (a ! NULL) ? a : b; return dummy.next; }这里我用了一个栈上的哑节点dummy全程不 malloc 任何内存只把tail-next指向较小的那个节点。为什么用哑节点因为合并结果的头节点到底是a还是b一开始说不准用哑节点就不需要每次判断“当前结果链表是否为空”。归并排序的完整递归逻辑如下Node *mergeSort(Node *head) { if (head NULL || head-next NULL) { return head; } Node *mid getMiddle(head); Node *right mid-next; mid-next NULL; Node *leftSorted mergeSort(head); Node *rightSorted mergeSort(right); return merge(leftSorted, rightSorted); }这个写法非常干净找中点、断链、递归排序、合并。每一步的逻辑都独立不像指针交换的冒泡那样各种状态搅在一起。4.3 时间复杂度与稳定性归并排序的时间复杂度是 O(n log n)而且不管链表原本是什么顺序它都是这个复杂度不存在快排那种“遇到逆序就退化”的问题。空间复杂度是 O(log n) 的递归栈开销但注意这里没有申请堆内存所以对嵌入式、内存敏感环境非常友好。还有一个重要特性归并排序是稳定排序。两个值相等的节点排序后相对顺序不会变。这个特性在实际工程里很有用比如你先按时间排序再按优先级排序两次排序后同一个优先级内部仍然按时间有序就是因为使用了稳定排序。相比之下前面讲的选择排序不是稳定排序一轮里把最小值换到前面会打乱相等值的相对顺序指针交换版的冒泡排序如果只在时交换可以做成稳定的。所以在工程里只要不是链表特别短我基本无脑选归并。简单、稳定、性能上限高这些优点在面试和实际开发里都是实打实的。5. 三种节点交换方式之外的排序策略和实际选择前面已经讲完了值交换、指针交换、归并排序这三种主流方式。但链表排序的坑还不止“选哪种算法”这么简单。从我这几年写代码的经验来看下面的几个问题才是真正让项目里链表排序翻车的重灾区。5.1 交换 data 域时结构体里的指针怎么办一个很常见的场景链表节点里存的不只是 int而是一个包含指针的结构体比如typedef struct Student { char *name; int score; struct Student *next; } Student;如果你用值交换法对这个结构体整体赋值那么两个节点的 name 指针也会被交换。看起来没问题其实问题很大第一如果你之后需要按 name 释放堆内存交换后 name 的归属就乱了你没法确定某个指针到底该由谁来 free。第二如果你交换后有一方被删除、释放了 name另一方的 name 就成了悬空指针访问就是野指针未定义行为。这种情况下要么改用指针交换法要么在值交换时只交换你关心的业务字段不要把 name、id 这类资源句柄也一并 swap。我一般在项目里会定义一个类似swapData的函数只拷贝业务字段不碰指针资源。5.2 稳定性需求哪些场景要求不能乱序稳定排序在什么场景重要举我踩过的一个坑在事件驱动系统里事件节点按优先级排序但同一优先级的节点要按入队时间先后处理。我用选择排序写了一次结果同优先级的事件顺序全乱了测试立刻报了一个诡异的状态错乱。后来我把排序换成归并问题直接消失。所以规则很简单如果你对“相等元素的先后顺序”有要求优先考虑稳定的排序算法归并、稳定的冒泡不要选择排序。如果不要求稳定那选择排序、快排都可以代码写起来还可能更简单。5.3 场景速查表直接给结论方便你下次做选型场景推荐方案理由链表短100节点、节点数据是基础类型值交换选择排序/冒泡代码简单边界清晰节点数据是大型结构体、带资源句柄指针交换排序交换代价低不搬数据长链表、性能要求高、要求稳定归并排序O(n log n)稳定无需额外内存笔试/面试手写题归并排序代码简洁且思路清晰最容易讲明白嵌入式环境、内存紧张归并排序不 malloc只靠栈上局部变量6. 避坑日记我写链表排序时踩过的四个真实故障最后分享几个我在写链表排序时实际遇到过的故障。这些问题的表现有时候很隐蔽可能只是某一次运行偶尔出错但根因几乎都是同一个指针操作越界或未处理边界条件。6.1 野指针导致排序中途崩溃有段时间在排一个嵌入式模块的链表调用排序函数后只要链表长度超过 3程序必崩。后来查了整整一个下午发现是我在冒泡排序的交换逻辑里忘了把尾节点的 next 置空。两个节点交换后互相指向对方结果形成了一个局部环遍历到尾节点后tail-next还指向旧地址一访问就非法。反过来说这也是为什么我后来坚持“每轮排序结束后打印一遍整个链表”的原因而不是等程序崩了再回头看代码。排查这种事越早发现越省时间。6.2 删节点后 next 没置空导致死循环有一次我给链表的“删除指定节点后排序”功能加代码排序过程中总是出现重复打印。原因是删除节点时我只做了“前驱节点的 next 指向被删节点的 next”但被删节点自己还保存着对后继的指向。虽然逻辑上新链表已经串好了但被删节点还“挂在”旧链表里偶尔会让遍历走到旧节点上去。这个问题的教训是断开一个节点的关系时把它的 next 一并置空。虽然有时候不置空也能跑但置空是更稳的做法能避免很多诡异现象。6.3 递归深度过深导致栈溢出归并排序用了递归链表特别长时比如几百万节点递归深度会有几十层虽然不至于压爆栈但在一些栈空间受限的嵌入式平台上还是可能爆。我遇到过一例单片机默认栈只有 8KB归并排序就死在这里。解决办法有两种一是平台上把任务栈调大二是把归并排序改成迭代版自底向上归并不用递归逻辑同样清晰。如果只是笔试刷题一般递归版就好不需要考虑这种极端情况。6.4 在线判题平台上的隐藏条件很多 C 语言 OJ 平台对链表排序的测试用例非常刁钻空链表、只有一个节点、所有值相等、已经排好序的逆序链表、节点数上万。每种情况都会触发不同分支的边界条件。我总结出来的经验是排序函数开头三行一定是if (head NULL) return head; if (head-next NULL) return head;这两行无损任何性能但能把一大批边界用例直接拦下。不要觉得这是废话等你看到 OJ 报几十个测试用例错一半再来补这两个判断心态就崩了。再一个细节在线判题平台经常用判断结果所以合并两个有序链表时用和也要想清楚。会把相等的节点从 a 链取走会从 b 链取走两种取法对最终链表内容没有影响但如果你后面还有额外逻辑这个选择就会影响顺序。7. 我现在的固定组合带头节点 递归归并这几年折腾下来我现在写链表排序已经基本固定成一套组合拳带头节点 递归归并 必要的边界断言。带头节点解决的是头节点交换、头部删除这些边界麻烦递归归并解决的是时间复杂度和稳定性问题边界断言保证我在任何平台上跑都不会因为空链表、单节点链表直接崩掉。这套组合在嵌入式、OJ、日常项目里都验证过算是我个人非常推荐的“实战模板”。最后再补一个调试小技巧很多人写链表排序时最怕的就是“看不出链表现在长什么样”。我习惯写一个极简的打印函数void printList(Node *head) { while (head) { printf(%d - , head-data); head head-next; } printf(NULL\n); }每次排序前打一遍排序后打一遍中间每轮关键操作后再打一遍。虽然多几行输出但对于定位断链、成环、丢节点的问题这个笨方法比其他任何调试器都好使。链表这个东西眼睛看到的打印结果比脑子里推演三百遍都更直接。链表排序说到底就是“遍历 比较 调整指针”的组合游戏。把单个环节的边界想清楚再组合出完整流程就没有想象中那么难了。希望这篇基于我自己踩坑经历写的文章能帮你少走点弯路拿去直接照着写就行。本文还有配套的精品资源点击获取