AlgoNote 算法通关手册：链表快速排序（Linked List Quick Sort）分治原理与 Python 实现详解

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是 AlgoNote 算法通关手册「链表排序」系列的技术指南围绕 链表快速排序文档 展开深入讲解如何基于分治策略与快慢指针就地分区对单链表完成排序。读完你将掌握链表快速排序的分区不变量、左闭右开区间递归模型、复杂度边界并能对照仓库源码与 0148. 排序链表 实战题目理解为什么链表快排在有序数据上会退化并超时。1. 链表快速排序基本思想链表快速排序基本思想通过选择基准值pivot将链表分割为两部分使得左部分所有节点的值都小于基准值右部分所有节点的值都大于等于基准值然后递归地对左右两部分进行排序最终实现整个链表的有序排列。与数组上的快速排序参见 数组快速排序文档相比链表快速排序面临一个本质差异链表不支持随机访问只能通过next指针顺序遍历无法像数组那样以 $O(1)$ 下标访问任意元素参见 链表排序总览 与 链表基础。因此分区过程不能使用左右指针从两端向中间收缩的 Hoare 哨兵划分法而必须改用快慢指针单向扫描的方式。链表快速排序的核心思想是分治策略具体算法步骤如下选择基准值从链表中选择一个基准值pivot通常选择头节点的值作为基准值。分割链表通过快慢指针node_i、node_j遍历链表将链表分割为两部分左部分所有节点值都小于基准值右部分所有节点值都大于等于基准值。递归排序对分割后的左右两部分分别递归执行快速排序。合并结果当子链表长度小于等于 1 时递归结束最终得到有序链表。值得注意的是这里的分割并非物理断开链表并重新拼接next指针而是通过交换节点值实现逻辑上的分组。由于链表节点对象本身不移动排序完成后返回的头节点引用不变无需额外维护拼接结构。2. 左闭右开的区间递归模型链表快速排序与数组快排的另一个关键差异在于递归区间的表示。数组可以用下标[low, high]表示区间链表则直接用两个节点指针表示区间边界left左边界节点包含right右边界节点不包含通常为None或某个已经定位的分割节点。这种左闭右开的约定直接决定了递归终止条件与子区间划分方式# 边界条件区间没有元素或者只有一个元素直接返回第一个节点 if left right or left.next right: return leftleft right空区间left.next right区间内只有一个节点。以上两种情况下区间天然有序递归终止。分割完成后若基准节点最终落在pi位置则左右子区间分别为[left, pi)与(pi, right]即代码中的quickSort(left, pi)与quickSort(pi.next, right)。3. 分割函数 partition快慢指针就地分区分割是链表快速排序的核心。下面这段实现与仓库源码 linked_list_quick_sort.py 中的partition完全一致def partition(self, left: ListNode, right: ListNode): # 边界条件区间没有元素或者只有一个元素直接返回第一个节点 if left right or left.next right: return left # 选择头节点为基准节点 pivot left.val # 使用快慢指针进行分割 # node_i: 指向小于基准值的最后一个节点 # node_j: 遍历指针寻找小于基准值的节点 node_i, node_j left, left.next while node_j ! right: # 发现一个小于基准值的元素 if node_j.val pivot: # 将 node_i 向右移动一位 node_i node_i.next # 交换 node_i 和 node_j 的值保证 node_i 之前的节点都小于基准值 node_i.val, node_j.val node_j.val, node_i.val node_j node_j.next # 将基准节点放到正确位置上node_i 位置 node_i.val, left.val left.val, node_i.val return node_i3.1 两个指针的分工与不变量node_j快指针 / 遍历指针从left.next开始一路向后扫描直到遇到右边界rightnode_i慢指针 / 边界指针始终指向小于基准值的最后一个节点。在整个扫描过程中始终维护如下不变量这也是算法正确性的关键node_i之前的节点值都小于基准值pivotnode_i与node_j之间的节点值都大于等于基准值pivot。每当node_j发现一个小于pivot的节点时先将node_i向右移动一位——此时node_i指向的必然是大于等于基准值区间的第一个节点交换node_i.val与node_j.val——将刚发现的小元素挪进左区间同时把一个大元素换到右侧。扫描结束后所有小于pivot的元素都已集中到node_i及其左侧最后一步node_i.val, left.val left.val, node_i.val把基准值原头节点left.val与node_i的值交换使基准值落到左右分界的正确位置并返回node_i作为基准节点最终位置。3.2 为什么只交换值、不移动节点链表的优势本在于 $O(1)$ 的指针级插入删除但这里刻意选择值交换而非节点重排原因有二交换值不需要维护前驱指针代码简洁且不易出错分区过程中链表的next结构完全不变头节点引用head始终有效递归返回时直接返回原left即可无需拼接。代价是当节点携带大量数据时值交换成本较高这一点与数组快排的交换开销类似。4. 递归主函数 quickSort 与入口函数4.1 递归主函数def quickSort(self, left: ListNode, right: ListNode): # 递归终止条件区间长度小于等于 1 if left right or left.next right: return left # 分割链表获取基准值位置 pi self.partition(left, right) # 递归排序左半部分 self.quickSort(left, pi) # 递归排序右半部分 self.quickSort(pi.next, right) return left递归流程非常清晰先partition定位基准pi再对[left, pi)与[pi.next, right)两个子区间递归排序。由于只交换值不改变节点连接每次递归返回的left始终是原区间的头节点。4.2 入口函数仓库源码 linked_list_quick_sort.py 中入口名为sortLinkedList文档中写作sortList逻辑等价def sortLinkedList(self, head: ListNode): # 边界条件检查空链表或只有一个节点 if not head or not head.next: return head # 调用快速排序右边界为 None链表末尾 return self.quickSort(head, None)入口处的边界检查非常关键空链表或单节点链表无需排序直接返回同时quickSort(head, None)以None作为右边界表示对整个链表排序。4.3 完整可运行示例将ListNode、Solution与测试数据组合即可在本地直接验证算法正确性class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def partition(self, left: ListNode, right: ListNode): if left right or left.next right: return left pivot left.val node_i, node_j left, left.next while node_j ! right: if node_j.val pivot: node_i node_i.next node_i.val, node_j.val node_j.val, node_i.val node_j node_j.next node_i.val, left.val left.val, node_i.val return node_i def quickSort(self, left: ListNode, right: ListNode): if left right or left.next right: return left pi self.partition(left, right) self.quickSort(left, pi) self.quickSort(pi.next, right) return left def sortLinkedList(self, head: ListNode): if not head or not head.next: return head return self.quickSort(head, None) # 构造链表并排序 def build(nums): dummy ListNode(0) cur dummy for v in nums: cur.next ListNode(v) cur cur.next return dummy.next def show(head): res [] while head: res.append(head.val) head head.next return res head build([4, 2, 1, 3]) sorted_head Solution().sortLinkedList(head) print(show(sorted_head)) # 输出: [1, 2, 3, 4]5. 算法复杂度分析指标复杂度说明最佳时间复杂度$O(n \log n)$每次等分为两半递归层数约 $\log n$最坏时间复杂度$O(n^2)$已有序/逆序或重复值多划分极端不均平均时间复杂度$O(n \log n)$期望情况下划分较均匀空间复杂度$O(\log n)$递归调用栈深度原地就地分区无额外数组稳定性不稳定相等节点的相对顺序可能改变关于空间复杂度需要说明这里的 $O(\log n)$ 仅指递归调用栈深度。由于采用原地值交换分区全程不额外分配节点数组辅助空间开销远小于需要新建链表的计数排序/桶排序但最坏情况下递归深度可达 $O(n)$划分极端不均时栈空间随之退化为 $O(n)$与数组快排的行为一致。6. 实战警示为什么 0148 排序链表用快排会超时0148. 排序链表题解 的思路 5 明确给出了一个重要的工程结论虽然链表快速排序算法的平均时间复杂度为 $O(n \times \log_2 n)$但链表快速排序算法中基准值pivot的取值做不到数组快速排序算法中的随机选择。一旦给定序列是有序链表时间复杂度就会退化到 $O(n^2)$。这也是这道题目使用链表快速排序容易超时的原因。这一退化根源可以结合代码结构推断数组快排可以random.randint随机选基准参见 数组快速排序文档 中的randomPartition而链表没有随机访问能力随机选基准需要先遍历计数再走到指定位置代价过高因此实现上只能取头节点为基准。当输入已有序如[1,2,3,...,n]时每次分区都极端失衡递归深度与扫描总量均退化为 $O(n^2)$。与之对比链表归并排序通过快慢指针找中点、物理断开链表再归并参见 链表归并排序源码无论数据是否有序都能稳定保持 $O(n \log n)$因此在 0148. 排序链表 中被标记为通过而快速排序被标记为超时。实际工程中对大规模未知分布的链表排序应优先选择归并排序快速排序更适合作为理解分治与就地分区思想的练习。7. 总结链表快速排序通过分治与就地分区实现排序平均效率高但极端情况下退化明显且不稳定。优点平均时间复杂度 $O(n \log n)$就地分区、空间开销小实现不依赖随机访问天然适配链表结构。缺点最坏时间复杂度 $O(n^2)$不稳定对枢轴选择敏感链表场景下无法随机选基准有序数据会触发退化。8. 练习题目0148. 排序链表链表快速排序会超时仅做练习建议同时尝试归并排序解法链表排序题目列表覆盖 0148、0021 合并两个有序链表、0023 合并 K 个升序链表、0147 对链表进行插入排序等进阶练习赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐Hello 算法基数排序Radix Sort原理与 Python 完整实现详解Hello 算法基数排序Radix Sort原理与 Python 完整实现详解 本文基于《Hello 算法》仓库中的基数排序 Python Tutor 逐教程文档示例工程教育freeCodeCamp 课程设计解析用递归分治实现快速排序Quick SortfreeCodeCamp 课程设计解析用递归分治实现快速排序Quick Sort 本文基于 freeCodeCamp 课程大纲中的 Implement前端后端教育Swift 堆排序Heap Sort算法详解原理、实现与复杂度分析Swift 堆排序Heap Sort算法详解原理、实现与复杂度分析 堆排序Heap Sort是 swift algorithm club 仓库中实现的示例工程教程上一篇如何快速将R代码转换为PythonDataSciencePython中的json2tweets实现指南下一篇蓝鲸CMDB数据导入导出终极指南10步实现批量数据迁移与备份恢复创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考