★ FEATURED ARTICLE 亲手写过链表排序的人都知道数组那套“按下标找数”的思路在单链表上经常碰壁偏偏很多教科书讲到选择排序就直接拿数组举例等到你自己想在链表上实现一遍才发现连“找最小的数”这种操作都要重新设计。这篇文章就把“基于链表的简单选择排序”从头到尾拆开讲清楚为什么选择排序和单链表其实是天然的搭档、怎么写代码不容易出bug以及最后一轮调试时那些让人头疼的指针问题都出在哪里。1. 算法思路拆解为什么选择排序适合链表1.1 选择排序的核心逻辑选择排序的原理说穿了就是一句话每一轮从待排序区间里挑出最小的元素把它放到当前区间的最前面然后待排序区间缩一格重复直到所有元素归位。拿扑克牌来想特别直观——你手里有一把乱序的牌每次从剩余的牌里抽出最小的一张放到最左边下一轮再从剩下的牌里抽最小的一张接着往右放等到所有牌抽完整把牌就排好了。这个逻辑有一个关键特点每轮只需要“找到最小元素”这一种操作而找最小只需要单向遍历一次不需要回头访问前驱也不需要频繁交换相邻元素。这个特点放到链表环境下非常契合因为单链表只有一个 next 指针想往回走基本做不到除非额外记录前驱。还有个容易忽略的点选择排序的比较次数是固定的 n(n-1)/2无论原始数据是有序还是完全逆序它都不会“偷懒”时间复杂度稳定在 O(n²)。对于几百上千节点的链表这个复杂度没问题一旦到几万、几十万节点肉眼可见地慢那时候就不该再用简单选择排序了。但作为理解数据结构与算法基础的教学题目它依然是必修课。1.2 数组版与链表版的根本差异数组版选择排序长得大概是这个逻辑for (i 0; i n - 1; i) { min i; for (j i 1; j n; j) if (a[j] a[min]) min j; swap(a[i], a[min]); }数组可以靠下标 a[j] 直接访问任意位置找最小值时只需记住最小值的下标。链表不一样你不能写 node[3] 这种语法只能通过指针 p p-next 一个节点一个节点往下爬。所以链表版找最小值时必须维护一个“指向最小节点的指针”而不是“最小值的下标”。除了访问方式不同数组交换元素只需 swap 两个下标指向的值链表交换数据域在指针层面完全不动只是把两个节点的 data 字段互相换一下。也就是说链表的选择排序在右手边只要交换数据不碰任何 next 指针这一点是很多只看数组教程的人没有意识到的优势。一旦你想通了“只交换数据不重组链表”这一层链表选择排序的代码复杂度立刻降下来因为整条链表的拓扑结构从头到尾根本没变过只是每个节点里存的值换了个位置。1.3 数据交换与指针交换两种策略的取舍实现链表选择排序大体上两条路交换节点数据域或者断开重连节点指针。我强烈建议在绝大多数学习场景下直接选数据交换。数据交换实现起来就是拿到两个节点后把它们的 data 字段互换。这样做的好处是整个链表的外形结构完全不变不需要担心“头节点丢失”“断链成环”这一类指针魔术调试也容易排序前后你数一数节点数逐个打印看一眼就知道有没有出问题。指针交换的思路是调整节点之间的 next让整个链表重新串成一个有序序列。这个方案面对“节点本身是个大结构体拷贝数据代价太高”的情况时更合适。比如每个节点里装着几百个字节的结构体甚至包含动态分配的缓冲描述信息你每交换一次就拷贝一整块数据代价很高此时调整 next 指针只改地址不搬数据。但指针交换的代码很容易在手写时出错要同时追踪待排序区间的边界指针、被删节点的前驱指针、被删节点的后继指针少记一个就断链。以我自己的经验刚开始学的时候非常容易在这种地方卡几个小时。因此我给出的建议很直接日常作业、考试、算法面试里写链表选择排序默认用数据交换法代码简单逻辑清晰正确率高。只有当节点数据体量真的特别大或者数据域包含不可拷贝的资源时才考虑指针交换。文章后面给的完整代码也是数据交换版指针交换会在第五节提到它的核心陷阱。2. 核心细节解析与实操要点2.1 节点结构设计与边界条件先定义节点。绝大多数课程和竞赛环境里都是不带头节点的单链表结构长这样typedef struct Node { int data; struct Node *next; } Node;写排序函数之前第一步永远是处理两个边界条件链表为空head NULL或者只有一个节点head-next NULL。这两种情况直接返回头指针即可不需要进入循环。别小看这两行检查很多新手代码崩溃就崩在这里——空链表直接取 head-next空指针解引用一步崩到结束。另一种常见做法是带一个不存数据的头节点哨兵节点把头节点传进排序函数。好处是头部操作可以统一但对于数据交换法而言哨兵节点的优势并不明显我建议初学者直接用不带头节点的版本专注理解排序本身。2.2 找最小节点只需要一个 minNode 指针在数据交换法的框架下内层循环的核心任务是找出未排序区间的最小节点。这块代码里最容易出错的点是“到底需要维护几个指针”我来明确回答只需要一个指向最小节点的指针不需要记录最小节点的前驱。为什么不需要前驱因为我们要做的是交换数据不是摘除节点。既然只是把两个节点的 data 对调那拿到正在考察的当前节点 cur 和找到的最小节点 minNode直接交换它们的 data 就行了根本不需要动 next自然也不需要知道 minNode 的前驱是谁。所以内层循环的逻辑就能压缩得很干净Node *p cur-next; Node *minNode cur; while (p ! NULL) { if (p-data minNode-data) { minNode p; } p p-next; }每一轮开始先把 minNode 初始化为 cur也就是默认当前未排序区间的第一个节点就是最小然后让 p 从 cur-next 出发往后扫。发现更小节点时只更新 minNode扫描完后手头就能确定谁是剩余区间里最小的。有个细节值得说为什么 p 从 cur-next 开始而不是从 cur 开始因为 cur 已经被当作初值放进 minNode 了从头再扫一遍没有任何意义。这个起点选对了循环体不仅少一次空转语义也更清楚。2.3 外层循环的终止条件外层循环驱动整轮选择从链表头部游走到尾部每轮把最小数据和当前节点交换然后 cur 向后挪一格。终止条件是 cur-next ! NULL而不是 cur ! NULL。原因是当 cur 已经指向最后一个节点时它已经是剩余区间里的唯一元素也是整个区间的最小值根本不需要再扫描一遍了。这个终止条件和数组版的差别也值得体会一下。数组版写的是 i n-1因为最后一个元素永远不可能再和谁交换。链表版写 cur-next ! NULL恰好对应“最后一个不需要处理”的语义。如果你把条件误写成 while (cur ! NULL)结果是什么会比较到最后一个节点为止多一轮空转。虽然最终排序结果大概率还是对的但多绕了一圈代码不干净。更重要的是这会让你习惯性地避开对终止条件的思考后面一旦改成指针交换法这种模糊的习惯就会变成实打实的 bug。2.4 完整参考代码把上面几块拼起来一个完整可运行的数据交换版选择排序函数如下Node *selectionSort(Node *head) { if (head NULL || head-next NULL) return head; Node *cur head; while (cur-next ! NULL) { Node *minNode cur; Node *p cur-next; while (p ! NULL) { if (p-data minNode-data) minNode p; p p-next; } if (minNode ! cur) { int tmp cur-data; cur-data minNode-data; minNode-data tmp; } cur cur-next; } return head; }排序完成后原来的链表头指针 head 依然有效因为整个排序过程没有改变任何节点的 next链表的外形和开始完全一致只是数据在节点之间发生了挪动。返回 head 直接可以继续遍历验证结果。如果要从小到大改成从大到小把内层 if (p-data minNode-data) 改成 if (p-data minNode-data) 就可以了。因为大于号意味着每轮找的是剩余区间最大的节点交换后最大的值不断被推到前面最终形成降序序列。3. 实操过程与核心环节实现单步推演与复杂度建模3.1 手推一遍 5 - 3 - 4 - 1 - 2光看代码不一定能建立起“这一轮到底干了什么”的直观印象我把一个标准例子完整推演一遍。初始链表5 - 3 - 4 - 1 - 2。第 1 轮cur 指向 5minNode 初始化为 5。p 从 3 开始扫描3 比 5 小minNode 记为 34 比 3 大跳过1 比 3 小minNode 记为 12 比 1 大跳过。扫描结束minNode 指向 1。交换 5 和 1 的 data链表变成 1 - 3 - 4 - 5 - 2。cur 移到 3。第 2 轮cur 指向 3minNode 初始化为 3。p 从 4 开始扫描4 比 3 大5 比 4 大2 比 3 小minNode 记为 2。交换 3 和 2链表变成 1 - 2 - 4 - 5 - 3。cur 移到 4。第 3 轮cur 指向 4minNode 初始化为 4。p 从 5 开始5 比 4 大接着看 33 比 4 小minNode 记为 3。交换 4 和 3链表变成 1 - 2 - 3 - 5 - 4。cur 移到 5。第 4 轮cur 指向 5minNode 初始化为 5。p 从 4 开始4 比 5 小minNode 记为 4。交换 5 和 4链表变成 1 - 2 - 3 - 4 - 5。cur 移到最后的 4触发 while (cur-next ! NULL) 的终止条件循环结束。这个 5 个元素的例子一共做了 4 轮每轮扫描长度分别为 4、3、2、1总比较次数 432110恰好等于 5*4/2。每次演示完我习惯把中间状态打印出来观察能非常直观地看到最小值如何一步步被“搬运”到头部后面这段无序区间如何不断收缩。建议读者自己动手在纸上画一遍比背代码有效得多。3.2 时间复杂度和空间复杂度先看比较次数外层跑 n-1 轮第 i 轮内层扫描剩余 n-i 个节点实际比较 n-i-1 次总比较次数是前 n-1 个自然数的和也就是 n(n-1)/2。无论输入数据是正序、逆序还是乱序这个数字都不会变所以最好情况、最坏情况、平均情况的时间复杂度全部是 O(n²)这是选择排序最突出的特点之一。再看交换次数数据交换法下每轮最多交换一次最少交换零次总共最多 n-1 次。交换操作本身是 O(1)。所以整体时间复杂度是 O(n²)。空间复杂度方面整个算法只用到了 cur、minNode、p、tmp 等固定数量变量没有额外申请与 n 相关的存储空间因此是 O(1) 原地排序。这一点比归并排序的 O(log n) 或 O(n) 辅助空间都要省。这里有个容易被忽略的推论既然不用额外空间那选择排序对内存受限的嵌入式环境挺友好哪怕时间复杂度高一点只要数据规模可控用起来完全没有压力。这也是为什么很多单片机OJ里简单排序首选选择排序或冒泡排序而不是快速排序。不过节点本身已经是链式存储本身就不像数组那样连续占用一大块内存空间上分布式存储所以“省空间”这点在链表场景里价值没有那么突出读者心里有数就好。3.3 稳定性分析为什么它不稳定排序算法的稳定性指的是排序前后相等关键字的相对顺序能不能保持不变。选择排序不稳定原因很容易解释它每轮会把远端的最小值直接交换到当前头部位置这个过程可能跨越多个相同关键字节点直接改变它们的相对顺序。举一个经典的例子链表 5a - 3 - 5b - 1其中 5a 和 5b 都代表关键字 5用后缀区分它们原本的相对位置。第 1 轮找出最小节点 1把它和当前头部 5a 交换链表变成 1 - 3 - 5b - 5a。此时两个 5 的相对顺序变成了 5b 在前、5a 在后和原来相反。排序完成后这个顺序不会恢复因此选择排序是不稳定排序。如果你业务上要求相等的元素必须保持原有先后顺序那选择排序从一开始就不该出现在候选名单里。链表场景下想要稳定排序可以考虑归并排序或者插入排序。但注意数组版插入排序是稳定的链表版插入排序只要严格按顺序查找插入位置也能做到稳定这点在下一节对比时会提到。4. 复杂度对比与优化空间分析4.1 常见链表排序算法横向对比这一节不用代码直接看一张我一直保留的对比表是我在不同链表排序方案间反复比较后整理的排序算法平均时间最坏时间空间稳定性在单链表上的实现难度简单选择排序O(n²)O(n²)O(1)不稳定低适合入门冒泡排序O(n²)O(n²)O(1)稳定中需要反复访问相邻前驱插入排序O(n²)O(n²)O(1)稳定中需维护已排序区末尾希尔排序视增量序列而定O(n²)O(1)不稳定高链表跳访问代价大归并排序O(n log n)O(n log n)O(log n)或O(n)稳定中高但常用递归快速排序O(n log n)O(n²)O(log n)不稳定高链表分割不如数组自然冒泡排序在链表上实现其实别扭。数组版冒泡靠相邻下标交换链表版想要交换相邻节点必须知道前驱节点的指针单链表又只能从头摸过去一次交换要 O(n) 找前驱整体直接退化成 O(n³) 的风险。好的写法是记录相邻节点的前驱指针但代码啰嗦程度远超选择排序。所以我跟新手讲链表排序第一步永远是“别先写冒泡”先写选择排序。插入排序在链表上的表现比很多人想象中好实现每轮把当前节点从无序区取下按顺序插入到前面已排序区因为链表天然支持在任意位置插入节点不需要搬移元素。最坏情况 O(n²)但对基本有序的链表表现很好且是稳定排序。实现时需要一个指针维护已排序区的尾部插入操作要小心处理头插和尾插两种边界。复杂度上和选择排序同为 O(n²)但插入排序的平均表现通常略好。如果你只是想排序一个无序链表且没有稳定性和额外内存限制归并排序才是最优解。4.2 提前终止与有序检测到底靠不靠谱数组版选择排序有个流行“优化”如果某一轮内层没有发生交换就说明序列已经有序可以提前结束。这个说法我仔细验证过在链表版里不能简单照搬。反例很简单链表 1 - 2 - 4 - 3。第 1 轮 cur 指向 1内层扫描 2、4、3发现最小节点就是 1一交换都没有发生。如果在这一轮就 break结果链表还是 1 - 2 - 4 - 3根本没有排好。原因在于某一轮的 cur 恰好已经是剩余区间最小值只能说明这个节点本身不需要挪动并不意味着后续区间已经有序。想在链表版里做“有序检测”必须在每一轮扫描时额外记录一个交换标记然后要等到一轮结束后发现完全没有任何交换并且这个情况发生在已经检查过所有节点位置之后才可信。但选择排序每一轮只把头部最小值换来你只检查头部最小值并不足以推断全链表有序。稳妥做法是在排序开始之前单独做一次 O(n) 扫描判断整个链表是否已经单调如果有序直接返回。这个优化只对“输入本来就基本有序”的场景有效正常情况下收益不大。换句话说不要花太多时间在给选择排序找优化上。它的固定比较次数是算法结构决定的再怎么优化也只是微调。如果数据规模大或者要求稳定海量数据直接换归并排序。4.3 哨兵节点的引入场景数据交换法不需要哨兵节点每次操作都只依赖现有节点的 next头部指针 head 从头到尾不会被改变。真正需要哨兵的是指针交换法。指针交换时如果要移动头节点你得知道“上一轮的上一轮”的那个前驱是谁专门去处理头节点会多出很多if判断创建一个哨兵节点把链表的真实头部挂到哨兵后面所有插入和删改都统一用“拿到前驱才能动手”的模式头节点情况下前驱就是哨兵代码可以少写一半分支。这个技巧我在做链表类题目时经常用尤其是涉及删除节点的场景。但如果你只是完成本文讨论的数据交换版选择排序哨兵节点属于可加可不加的糖不加反而更贴近“最简单实现”的初衷。4.4 结构体节点与大块数据场景的应对如果你要排序的链表节点长这样typedef struct BigNode { char name[256]; int score; double feature[64]; struct BigNode *next; } BigNode;swap 整个结构体一次就要拷贝几百上千字节。n 一到大光拷贝数据的开销非常可观。此时数据交换法的优势变成了劣势你应该使用指针交换。指针交换的核心思路每一轮找出最小值节点 minNode 以及它的前驱 minPrev同时也知道当前节点 cur 的前驱 curPrev然后把 minNode 从原位置摘下来插入到 cur 的前面cur 变成未排序区间的新头部。这里需要同时维护 minPrev 和 curPrev 两个前驱少一个都做不了。实现时最容易翻车的地方就是顺序先把 minNode 的 next 保存下来更新 minPrev-next 指向 minNode-next再把 minNode-next 指向 cur最后让 curPrev-next 指向 minNode。这三步顺序乱一步链表就成环了。我在文末的“常见问题”部分还会继续讲这个场景下的排查思路。5. 常见问题与排查技巧实录5.1 空指针崩溃最大的坑只有一个来源链表排序里遇到段错误十有八九是空指针解引用。常见高发点有三个忘记处理空链表和单节点、内层循环的 p 推进时对 p-next 直接访问、交换数据后 cur 误写成被交换过去的节点而不是下一个节点。排查空指针我习惯先给排序函数加一段开头日志printf(sort head%p, head-next%p\n, (void*)head, head ? (void*)head-next : NULL);定位到是空指针再一层层确认:到底是入口就空还是跑了几轮后空。链表这种结构最常见的空指针就是“最后一个节点后的 NULL 被当成了有效节点访问”。每一段循环都要问一遍自己代码能不能访问到 p-next 时 p 一定不等于 NULL。5.2 minNode 初始化的错误与表现有些新手会把 minNode 初始化为 NULL然后在内层循环里遇到第一个节点就赋值。这样写也能跑但逻辑上凭空多出一个判断分支还容易漏掉“如果整个区间只有一个节点”的情况。更简洁也更能体现选择排序语义的做法是把 minNode 初始化为 cur也就是“默认当前第一个就是最小”后续只更新比它更小的。另一种低级错误是内层循环把 minNode 和 p 搞混。发现更小节点时写成 p minNode直接打乱了遍历指针链表就开始原地打转。判别方法很简单出现死循环后把中间链表打印出来如果看到某个节点被重复打印或者打印的节点顺序发生跳变多半就是遍历指针被错误赋值了。5.3 数据交换前后 cur 的移动时机正确写法是先判断 minNode 是否就是 cur如果不是才交换最后统一执行 cur cur-next。顺序很重要交换放在 cur 后移之前因为交换用到的就是 cur 当前指向的节点一旦后移cur 就指向下一个节点了交换就变味了。有些写法会把 cur 指向 minNode这是完全错误的。盯着逻辑看cur 代表的是未排序区间的边界每一轮结束后边界就要向右收紧一格这个移动是固定的和 minNode 是谁没有任何关系。总是朝下一个原始位置走才能保证每个位置都作为当前边界被处理一次。5.4 指针交换法的经典成环场景虽然推荐数据交换法但肯定有人会去尝试指针交换。指针交换版比较容易写出成环 bug典型错误如下// 错误示范 minPrev-next minNode-next; minNode-next cur; curPrev-next minNode; // curPrev 可能还没正确维护如果 curPrev 始终没有更新那么当 cur 需要后移时整个链表可能已经成一个环printf 打印链表会一直输出不结束因为箭头永远绕不出去。排查方法是我到处推荐的“断链法”在一轮操作后手动从 head 开始数节点个数如果数出来比元素总数多要么成环要么指针跳错位。可以用一个有界计数循环帮助判断死循环int count 0; Node *t head; while (t count 200) { t t-next; count; } if (count 200) printf(suspected cycle\n);调试链表问题本来就是一步步走、一步步打印的过程。我见过太多人盯着屏幕想半天不如直接把中间状态全部打印出来看几轮就明白了。5.5 “数据域太值钱”时的最终方案我前面说过指针交换是应对大结构体节点的方案但还有一种务实做法如果排序对象的数据体量真的非常大与其交换数据不如给链表重新建一个索引数组用数组下标排序然后按排序后的下标重建链表。等于用 O(n) 的辅助空间换取 O(n²) 开销里那部分交换数据的成本降低。当然这已经不是“简单选择排序”的范畴了。对一个合格的工程师来说任务的第一优先级不是让算法听起来高级而是判断当前数据结构、数据规模和稳定性需求下该选哪种排序。链表上真正规模化排序归并排序永远是首选时间复杂度 O(n log n)、稳定、空间 O(n)如果迭代法可以做到 O(1) 额外空间保存缓冲。选择排序适合的是节点数小、代码必须短、空间必须省的场景。最后分享一点我的个人体会最初自己学链表排序时我一股脑想的是怎么“优雅地”交换指针、把头节点换来换去结果每次调试都是两小时起。后来想明白一件事链表的很多复杂问题都是因为我们默认必须动 next 才能完成排序。实际上只要数据域可以被赋值交换数据才是最直接的思维路径。现在碰到规模不大的链表排序我基本都是几行数据交换法写完收工心里踏实。一个小习惯让我少走了很多弯路每写完一个链表操作先跑一遍“数节点 打印全链”的验证脚本而不是直接看排序结果对不对。因为链表 bug 往往会让结构损坏但排序结果可能碰巧正确误导你找不到问题。先把结构合法性验证了再看数据对不对定位速度快得多。希望这篇文章能让你少踩几个我曾经踩进去的坑。
阅读完成 · 觉得有帮助？
