2.2 链表排序

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

1.1 算法适用性分析适用性排序算法说明完全适合冒泡排序、选择排序、插入排序、归并排序、快速排序天然适合链表结构需要额外空间计数排序、桶排序、基数排序需要辅助数组，但算法逻辑适合不适合希尔排序依赖随机访问，链表无法高效实现不推荐堆排序完全二叉树结构用链表存储效率低1.2 关键限制因素希尔排序的限制：希尔排序需要访问序列中第 i+gapi + gapi+gap 个元素，链表无法直接跳转，必须从头遍历，时间复杂度从 O(1)O(1)O(1) 退化为 O(n)O(n)O(n)。

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

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

2.1 比较排序算法算法核心思想时间复杂度空间复杂度特点冒泡排序相邻节点比较交换O(n2)O(n^2)O(n2)O(1)O(1)O(1)实现简单，适合小规模数据选择排序选择最小节点交换O(n2)O(n^2)O(n2)O(1)O(1)O(1)交换次数少，适合交换成本高的场景插入排序逐个插入到有序序列O(n2)O(n^2)O(n2)O(1)O(1)O(1)链表上表现优异，适合部分有序数据归并排序分治合并O(nlog⁡n)O(n \log n)O(nlogn)O(1)O(1)O(1)链表上的最优选择，稳定高效快速排序基准分割递归O(nlog⁡n)O(n \log n)O(nlogn)O(1)O(1)O(1)平均性能好，但最坏情况 O(n2)O(n^2)O(n2)2.2 非比较排序算法算法核心思想时间复杂度空间复杂度适用条件计数排序统计频率重建O(n+k)O(n + k)O(n+k)O(k)O(k)O(k)值域范围小，kkk 为值域大小桶排序分桶排序合并O(n)O(n)O(n)O(n+m)O(n + m)O(n+m)数据分布均匀，mmm 为桶数基数排序按位分桶排序O(n×d)O(n \times d)O(n×d)O(n+k)O(n + k)O(n+k)数字位数 ddd 较小2.3 算法选择建议小规模数据：选择冒泡排序或插入排序大规模数据：优先考虑归并排序特定场景：根据数据特征选择相应的非比较排序参考资料【文章】单链表的冒泡排序_zhao_miao的博客 - CSDN博客【文章】链表排序总结（全）（C++）- 阿祭儿 - CSDN博客【题解】快排、冒泡、选择排序实现列表排序 - 排序链表 - 力扣【题解】归并排序+快速排序 - 排序链表 - 力扣【题解】排序链表（递归+迭代）详解 - 排序链表 - 力扣【题解】Sort List （归并排序链表） - 排序链表 - 力扣