单向链表的排序

排序是数据结构的核心算法而链表排序更是面试高频考点 —— 因为链表无法随机访问需要用指针操作来实现排序逻辑。本文将从插入排序的核心思想讲起一步步拆解数组插入排序 → 单向链表插入排序 → 单向链表选择排序用图文 代码带你彻底掌握链表排序的精髓。一、插入排序核心思想与数组实现1.1 插入排序的核心思想插入排序的本质是 **「将无序区的数据逐个插入到有序区的合适位置」**最终让整个序列有序。可以类比军训排队一开始只有第一个人站好有序区后面的人无序区依次过来找到自己在队伍中的位置插入进去重复这个过程直到所有人都站成有序队列。1.2 数组实现插入排序数组的插入排序逻辑清晰是理解链表插入排序的基础// 数组插入排序升序 void insert_sort(int a[], int len) { int j, t; // step1: 划分有序区/无序区i从1开始默认a[0]是有序区 for (int i 1; i len; i) { // step2: 拿数取出无序区第一个元素a[i] t a[i]; j i; // step3: 找位置在有序区中找到t的插入位置 while (j 0 t a[j-1]) { a[j] a[j-1]; // 元素后移腾出位置 --j; } // step4: 插入将t放到正确位置 a[j] t; } }执行步骤拆解初始有序区[a[0]]无序区[a[1], a[2], ..., a[n-1]]取出无序区第一个元素t从后往前遍历有序区比t大的元素后移将t插入到腾出的位置有序区长度 1重复直到无序区为空。二、单向链表插入排序从数组到链表的思维转换链表无法随机访问也不能像数组那样「后移元素」所以插入排序的实现逻辑完全不同 ——核心是「拆分链表 逐个插入有序区」。2.1 链表插入排序的整体流程以链表4 → 2 → 3 → 5为例完整流程如下阶段操作链表状态初始原链表head → 4 → 2 → 3 → 5 → NULLstep1拆分有序区 / 无序区有序区head → 4 → NULL无序区2 → 3 → 5 → NULLstep2拿数取无序区第一个节点2有序区head → 4 → NULL待插入2无序区3 → 5 → NULLstep3找位置2 4插在4前面有序区head → 2 → 4 → NULLstep4拿数取无序区第一个节点3有序区head → 2 → 4 → NULL待插入3无序区5 → NULLstep5找位置2 3 4插在2和4之间有序区head → 2 → 3 → 4 → NULLstep6拿数取无序区第一个节点5有序区head → 2 → 3 → 4 → NULL待插入5无序区NULLstep7找位置5 4插在末尾有序区head → 2 → 3 → 4 → 5 → NULL排序完成2.2 关键概念与指针设计p_list指向有序区的头节点p_temp指向无序区的第一个节点用于遍历无序区p_insert当前要插入到有序区的节点p在有序区中遍历的指针最终停在待插入位置的前一个节点链表插入必须知道前驱节点。2.3 链表插入排序代码实现#include stdio.h #include stdlib.h // 定义链表节点 typedef struct node { int data; struct node *next; } node_t; // 创建头节点 node_t *create_list() { node_t *head (node_t *)malloc(sizeof(node_t)); head-data 0; // 头节点不存有效数据 head-next NULL; return head; } // 尾插法添加节点 void append(node_t *head, int data) { node_t *new_node (node_t *)malloc(sizeof(node_t)); new_node-data data; new_node-next NULL; node_t *p head; while (p-next ! NULL) { p p-next; } p-next new_node; } // 打印链表 void print_list(node_t *head) { node_t *p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 单向链表插入排序升序 void insert_sort_list(node_t *p_list) { if (p_list-next NULL || p_list-next-next NULL) { return; // 空链表或只有一个节点无需排序 } // step1: 拆分有序区和无序区 node_t *p_temp p_list-next-next; // 无序区第一个节点 p_list-next-next NULL; // 断链有序区只剩第一个节点 // step2: 遍历无序区逐个插入有序区 while (p_temp ! NULL) { node_t *p_insert p_temp; // 待插入节点 p_temp p_temp-next; // 无序区指针后移 // step3: 在有序区中找插入位置p最终停在待插入位置的前驱 node_t *p p_list; while (p-next ! NULL p-next-data p_insert-data) { p p-next; } // step4: 插入节点 p_insert-next p-next; p-next p_insert; } } int main() { node_t *head create_list(); // 构造测试链表4 → 2 → 3 → 5 append(head, 4); append(head, 2); append(head, 3); append(head, 5); printf(排序前); print_list(head); insert_sort_list(head); printf(排序后); print_list(head); // 输出2 3 4 5 return 0; }代码核心逻辑拆分链表将原链表拆为「有序区仅首节点」和「无序区剩余节点」遍历无序区逐个取出待插入节点寻找位置用指针p遍历有序区找到待插入节点的前驱插入节点修改指针将待插入节点链入有序区。三、单向链表选择排序另一种经典排序思路选择排序的核心是 **「为每个位置选择合适的数」**—— 在无序区中找到最小或最大的节点将其交换到当前位置逐步让链表有序。3.1 选择排序的核心思想类比军训排队从第一个位置开始在后面所有人中找到最矮的人交换到第一个位置再从第二个位置开始在后面所有人中找到最矮的人交换到第二个位置重复直到所有位置都处理完毕。3.2 链表选择排序代码实现// 单向链表选择排序升序 void select_sort_list(node_t *p_list) { if (p_list-next NULL || p_list-next-next NULL) { return; } node_t *curr p_list-next; // 当前要确定的位置 while (curr ! NULL) { node_t *p curr-next; // 遍历指针 node_t *min_node curr; // 记录当前最小节点 // 在无序区中找到最小节点 while (p ! NULL) { if (p-data min_node-data) { min_node p; // 更新最小节点 } p p-next; } // 交换当前节点和最小节点的数据简化实现无需修改指针 if (min_node ! curr) { int temp curr-data; curr-data min_node-data; min_node-data temp; } curr curr-next; // 处理下一个位置 } }代码核心逻辑定位当前位置curr指向当前要确定的位置寻找最小值遍历curr之后的节点找到数据最小的节点交换数据将curr节点和最小节点的数据交换简化实现避免复杂指针操作后移指针curr后移处理下一个位置。四、链表排序对比插入排序 vs 选择排序特性插入排序选择排序核心思想逐个插入有序区为每个位置选最小数时间复杂度最好O (n)已排序最坏 / 平均O (n²)最坏 / 平均O (n²)空间复杂度O (1)原地排序O (1)原地排序稳定性稳定相同元素相对位置不变不稳定交换可能破坏相对位置链表实现难度中等需拆分链表 找前驱简单直接交换数据使用建议链表已接近有序 → 优先用插入排序时间复杂度接近 O (n)追求实现简单 → 用选择排序数据交换逻辑清晰大规模数据 → 不建议用这两种应使用归并排序链表排序最优算法时间复杂度 O (nlogn)。五、总结与学习建议5.1 核心知识点回顾插入排序将无序区元素逐个插入有序区数组版靠「后移元素」链表版靠「指针插入」链表插入排序关键是「拆分链表」和「找到前驱节点」是面试高频考点选择排序为每个位置选最小数链表实现可通过「交换数据」简化指针操作时间复杂度两种排序均为 O (n²)适合小规模数据。5.2 学习建议先练数组版理解插入排序的核心思想再迁移到链表画图理解用草稿纸画出指针变化过程比死记代码更有效边界测试测试空链表、单节点链表、已排序链表、逆序链表覆盖所有边界情况进阶学习掌握这两种后可尝试学习链表归并排序。