2.2 链表排序

ITCharge大约 3 分钟

---

1. 链表排序简介

链表排序相比数组排序具有独特的挑战性。由于链表 不支持随机访问，只能通过 $next$ 指针顺序遍历，这使得某些排序算法在链表上的实现更加复杂。

希尔排序的限制：希尔排序需要访问序列中第 $i + gap$ 个元素，链表无法直接跳转，必须从头遍历，时间复杂度从 $O(1)$ 退化为 $O(n)$ 。

堆排序的限制：堆排序基于完全二叉树结构，数组可以通过下标 $O(1)$ 访问父子节点，而链表需要遍历查找，效率极低。

链表排序算法可分为 比较排序 和 非比较排序 两大类，每种算法都有其适用场景和性能特点。

算法	核心思想	时间复杂度	空间复杂度	特点
冒泡排序	相邻节点比较交换	$O(n^2)$	$O(1)$	实现简单，适合小规模数据
选择排序	选择最小节点交换	$O(n^2)$	$O(1)$	交换次数少，适合交换成本高的场景
插入排序	逐个插入到有序序列	$O(n^2)$	$O(1)$	链表上表现优异，适合部分有序数据
归并排序	分治合并	$O(n \log n)$	$O(1)$	链表上的最优选择，稳定高效
快速排序	基准分割递归	$O(n \log n)$	$O(1)$	平均性能好，但最坏情况 $O(n^2)$

算法	核心思想	时间复杂度	空间复杂度	适用条件
计数排序	统计频率重建	$O(n + k)$	$O(k)$	值域范围小， $k$ 为值域大小
桶排序	分桶排序合并	$O(n)$	$O(n + m)$	数据分布均匀， $m$ 为桶数
基数排序	按位分桶排序	$O(n \times d)$	$O(n + k)$	数字位数 $d$ 较小