10、链表的排序：冒泡排序在链表上的实现、插入排序在链表上的实现
排序，是数据结构里绕不开的话题。数组排序我们都很熟悉了，但链表排序呢？
说实话，我刚入行那会儿，也觉得链表排序不就是把数组那套搬过来吗？结果一上手就发现——没那么简单。链表没有随机访问能力，你不能直接 list[i] 去取值。这就逼着我们去思考：指针操作到底该怎么玩？
今天我们就来聊聊两种最基础的排序算法在链表上的实现：冒泡排序 和 插入排序。
核心观点：链表排序的本质不是交换数据，而是调整指针。谁把指针玩明白了，谁就掌握了链表的精髓。
10.1 冒泡排序在链表上的实现
冒泡排序的思路很简单：从头到尾，两两比较，把大的往后“冒”。
在数组里，我们靠下标来遍历。在链表里，我们靠指针来移动。我习惯用两个指针：一个指向当前节点，一个指向它的下一个节点。
10.1.1 基本思路
- 外层循环控制“趟数”，一共需要
n-1趟 - 内层循环负责两两比较，把大的节点往后移
- 每一趟结束后，最大的节点就“沉”到了链表尾部
你可能会问：链表怎么知道长度？嗯，要么提前遍历一遍算出来，要么用 while 循环判断是否到达尾部。我个人更倾向于后者——少一次遍历，少一点麻烦。
10.1.2 代码实现
// 链表节点定义
typedef struct Node {
int data;
struct Node* next;
} Node;
// 冒泡排序（只交换数据域）
void bubbleSort(Node* head) {
if (head == NULL || head->next == NULL) return;
int swapped;
Node* ptr;
Node* last = NULL; // 指向已排序的尾部
do {
swapped = 0;
ptr = head;
while (ptr->next != last) {
if (ptr->data > ptr->next->data) {
// 交换数据
int temp = ptr->data;
ptr->data = ptr->next->data;
ptr->next->data = temp;
swapped = 1;
}
ptr = ptr->next;
}
last = ptr; // 更新已排序尾部
} while (swapped);
}我的经验：这里我选择只交换数据域，而不是调整指针。为什么？因为简单、直观、不容易出错。如果你追求极致性能，可以尝试交换节点指针——但相信我，调试起来会让你怀疑人生。
10.1.3 冒泡排序的复杂度
| 指标 | 值 |
|---|---|
| 最好情况 | O(n) — 已经有序，只需一趟 |
| 最坏情况 | O(n²) — 完全逆序 |
| 平均情况 | O(n²) |
| 空间复杂度 | O(1) — 原地排序 |
说白了，冒泡排序在链表上并不高效。但我为什么还要讲？因为它简单、好理解，适合用来理解“指针遍历”的基本操作。
10.2 插入排序在链表上的实现
插入排序的思路是：把链表分成两部分——已排序区和未排序区。每次从未排序区取一个节点，插入到已排序区的正确位置。
这个思路在链表上其实比数组更自然。为什么？因为链表插入不需要移动元素，只需要改几个指针就行。
10.2.1 基本思路
- 维护一个“已排序链表”的头指针，初始为
NULL - 遍历原链表，每次取出一个节点
- 在已排序链表中找到合适的位置，插入进去
我曾经在项目中用这个思路处理一个实时数据流——数据不断进来，需要保持有序。插入排序在链表上简直就是为这种场景量身定做的。
10.2.2 代码实现
// 插入排序（调整指针）
Node* insertionSort(Node* head) {
if (head == NULL || head->next == NULL) return head;
Node* sorted = NULL; // 已排序链表头
Node* curr = head;
while (curr != NULL) {
Node* next = curr->next; // 保存下一个节点
// 在 sorted 中找到插入位置
if (sorted == NULL || sorted->data >= curr->data) {
// 插入到头部
curr->next = sorted;
sorted = curr;
} else {
// 在 sorted 中查找插入位置
Node* search = sorted;
while (search->next != NULL && search->next->data < curr->data) {
search = search->next;
}
curr->next = search->next;
search->next = curr;
}
curr = next; // 继续处理下一个节点
}
return sorted;
}避坑指南：我曾经在写这段代码时，忘记保存 curr->next，结果插入操作把 curr 的 next 改了，导致原链表断掉，后面的节点全丢了。记住：先保存，再操作。
10.2.3 插入排序的复杂度
| 指标 | 值 |
|---|---|
| 最好情况 | O(n) — 已经有序，每次插入到尾部 |
| 最坏情况 | O(n²) — 逆序，每次插入到头部 |
| 平均情况 | O(n²) |
| 空间复杂度 | O(1) — 原地排序 |
你想想看，插入排序在链表上的优势是什么？它不需要像数组那样频繁移动数据，只需要改指针。所以实际运行效率往往比冒泡排序好不少。
10.3 两种排序的对比
| 对比项 | 冒泡排序 | 插入排序 |
|---|---|---|
| 实现难度 | 简单 | 中等 |
| 指针操作 | 少（只交换数据） | 多（调整指针） |
| 稳定性 | 稳定 | 稳定 |
| 适用场景 | 教学、小规模数据 | 数据流、部分有序数据 |
| 实际效率 | 较低 | 较高 |
我的建议：如果你只是写个作业或练手，冒泡排序就够了。但如果你在写生产代码，尤其是数据量不确定时，插入排序是更靠谱的选择。
10.4 知识体系图
下面这张图帮你理清链表排序的核心逻辑：
嗯，这张图把两种排序的核心区别画得很清楚。冒泡排序重在“比较和交换”，插入排序重在“拆分和插入”。
10.5 避坑总结
最后，我把自己踩过的坑总结一下，希望能帮你少走弯路：
- 忘记保存 next 指针：插入排序时，一定要先保存
curr->next，否则链表会断 - 死循环：冒泡排序的
last指针更新不对，会导致内层循环永远跑不完 - 空链表和单节点：这两种情况一定要提前处理，否则代码会崩溃
- 稳定性问题：如果你交换的是节点指针而不是数据，稳定性可能会被破坏
一个小技巧：调试链表排序时，我习惯写一个 printList() 函数，每趟排序后都打印一次。这样能直观看到数据是怎么“冒泡”或“插入”的。
好了，链表排序就讲到这里。这两种排序虽然简单，但它们是理解更高级排序算法（比如归并排序、快速排序）的基础。把指针操作练熟了，后面学什么都快。
公众号:蓝海资料掘金营，微信deep3321