Hello Algo 快速排序深度解析：Pivot 分区、三数取中与尾递归优化的 Python 实现

Hello Algo 快速排序深度解析Pivot 分区、三数取中与尾递归优化的 Python 实现【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文以 hello-algo 仓库ru/codes/pythontutor/chapter_sorting/quick_sort.md中收录的 4 段可在线逐步可视化的 Python 快速排序代码为主体结合仓库内可直接运行的完整源码 quick_sort.py系统讲解 pivot 分区的指针运动过程、三数取中median of three选主元的原理、以及通过先递归短子数组将最坏空间复杂度从 O(n) 压到 O(log n) 的尾递归改造。读完本文你可以读懂分区函数每一行代码的意图并能在本仓库中复现与验证三种实现。一、文档定位pythontutor 目录与主源码的对应关系ru/codes/pythontutor/chapter_sorting/quick_sort.md是《Hello 算法》教程的辅助文件它不是一篇长文而是把快速排序的 4 个核心代码版本分别编码为 Python Tutor 在线可视化工具的 URLURL 编码后嵌入render.html#code...链接注释头标注了对应的[file]{quick_sort}-[class]{...}-[func]{...}映射读者可以在浏览器中逐指令step-by-step观察指针i、j的移动与元素交换。这 4 个可视化代码块与可运行源码 quick_sort.py 的映射关系如下可视化块顺序映射注释对应源码类/方法代码规模1[file]{quick_sort}-[class]{quick_sort}-[func]{partition}QuickSort.partition仅分区函数2[file]{quick_sort}-[class]{quick_sort}-[func]{quick_sort}QuickSort.quick_sort分区 完整递归3[file]{quick_sort}-[class]{quick_sort_median}-[func]{partition}QuickSortMedian.partition三数取中分区4[file]{quick_sort}-[class]{quick_sort_tail_call}-[func]{quick_sort}QuickSortTailCall.quick_sort尾递归优化版4 个块共用同一测试用例nums [2, 4, 1, 0, 3, 5]与教程主文档 quick_sort.md 的配图序列完全一致形成图 → 逐步动画 → 源码的三层印证。二、核心机制双指针 pivot 分区partition快速排序的关键操作是「带主元的分区」选一个元素作为 pivot把所有不大于它的元素移到左边、不小于它的元素移到右边。可视化块 1 对应的分区代码与 QuickSort.partition 逐行一致为def partition(nums: list[int], left: int, right: int) - int: Разбиение с опорными указателями # 双指针分区 # 取 nums[left] 作为主元pivot i, j left, right while i j: while i j and nums[j] nums[left]: j - 1 # 从右向左找第一个小于主元的元素 while i j and nums[i] nums[left]: i 1 # 从左向右找第一个大于主元的元素 # 交换两个错位的元素 nums[i], nums[j] nums[j], nums[i] # 将主元交换到两个子数组的交界处 nums[i], nums[left] nums[left], nums[i] return i # 返回主元最终所在的索引逐步拆解以nums [2, 4, 1, 0, 3, 5]、left0、right5为例主元固定在最左端pivot 取nums[left] 2i、j从两端相向扫描j 先动从右向左跳过所有 2的元素5、3停在nums[3] 0第一个比主元小的i 再动从左向右跳过所有 2的元素停在nums[2] 4第一个比主元大的交换nums[2], nums[3]互换此时数组为[2, 4, 0, 1, 3, 5]——注意 4 与 0 交换后i处仍 主元、j处仍 主元两个内层循环条件天然保证指针不会越过正确位置继续直到i j两指针在索引 2 相遇元素为 0收尾把主元nums[left]与nums[i]交换得到[0, 1, 2, 4, 3, 5]返回主元索引 2。此时满足不变式左子数组所有元素 ≤ 主元 ≤ 右子数组所有元素。从源码结构看该实现有两个值得注意的细节内层循环使用/而非/相等元素不参与交换这减少了交换次数但也正是主文档 quick_sort.md 指出快速排序不稳定的原因——最后一步nums[i], nums[left]会把主元与一个相等元素交换相对次序可能改变返回的是主元落点i而非主元值外层递归只需要这个索引来切分左右子问题避免了重复查找。三、递归框架divide and conquer 的完整闭环可视化块 2 在分区之上叠加了递归主体与 QuickSort.quick_sort 一致def quick_sort(nums: list[int], left: int, right: int): Быстрая сортировка # 快速排序 # 子数组长度等于 1 时终止递归 if left right: return # 双指针分区 pivot partition(nums, left, right) # 递归处理左、右两个子数组 quick_sort(nums, left, pivot - 1) quick_sort(nums, pivot 1, right)三个要点递归基left right子数组长度为 0 或 1 时无需排序。注意它同时兜住了pivot - 1 left、pivot 1 right的边界情况——当主元恰好是子数组最小或最大值时某侧子问题为空区间主元索引被排除在递归区间之外pivot - 1与pivot 1分区结束时主元已在最终位置无需再参与排序原地排序全程只交换nums内部元素不分配辅助数组这是空间开销全部来自递归调用栈的前提。以教程统一用例[2, 4, 1, 0, 3, 5]执行完整流程后输出为[0, 1, 2, 3, 4, 5]本仓库实际运行 quick_sort.py 的输出为После быстрой сортировки nums [0, 1, 2, 3, 4, 5]四、优化一三数取中选择主元median of three问题当输入已完全有序升序或降序时永远取最左元素为主元的朴素策略每次分区都把数组切成0与n-1递归深度退化到n时间复杂度从平均 O(n log n) 退化为 O(n²)。随机化主元能缓解但无法保证伪随机序列仍可被针对性构造攻破。方案从left、mid (left right) // 2、right三个候选中取中位数作为主元。可视化块 3 额外引入了median_three函数与 QuickSortMedian.median_three 一致def median_three(nums: list[int], left: int, mid: int, right: int) - int: Выбрать медиану из трех кандидатов # 从三个候选中选出中位数 l, m, r nums[left], nums[mid], nums[right] if (l m r) or (r m l): return mid # m 介于 l 与 r 之间 if (m l r) or (r l m): return left # l 介于 m 与 r 之间 return right这段代码没有调用排序而是用 6 个链式比较两个方向各 2 个条件覆盖了 3 个元素的全部 6 种大小关系返回中位数所在索引。随后partition只需多两步与 QuickSortMedian.partition 一致med median_three(nums, left, (left right) // 2, right) # 把中位数交换到数组最左端复用取 nums[left] 为主元的分区逻辑 nums[left], nums[med] nums[med], nums[left]设计上很克制不重写分区逻辑只把中位数换到left位置让后续双指针流程与朴素版完全一致。对于nums [2, 4, 1, 0, 3, 5]三个候选为2, 1, 5中位数是1索引 2换到最左后主元变为 1——比朴素版取 2 更靠近数据中位数降低了主元过大或过小的概率使时间复杂度退化到 O(n²) 的概率显著下降。本仓库运行该版本同样输出[0, 1, 2, 3, 4, 5]。五、优化二尾递归优化压缩调用栈深度问题即使平均情况下快速排序时间最优若某侧子数组始终很长如已排序输入被切成0 n-1递归树退化为深度n的链调用栈需要 O(n) 空间。方案每轮分区后只对较短的一侧发起递归较长的一侧改为循环更新边界与 QuickSortTailCall.quick_sort 一致即可视化块 4def quick_sort(nums: list[int], left: int, right: int): while left right: # 双指针分区 pivot partition(nums, left, right) # 对两个子数组中较短的一侧执行递归 if pivot - left right - pivot: quick_sort(nums, left, pivot - 1) # 递归处理左侧 left pivot 1 # 剩余未排序区间 [pivot 1, right] else: quick_sort(nums, pivot 1, right) # 递归处理右侧 right pivot - 1 # 剩余未排序区间 [left, pivot - 1]其正确性论证如下短侧长度 ≤(right - left) / 2每递归一层剩余待处理区间的长度至少减半因此递归深度上界为 log₂n最坏空间复杂度从 O(n) 优化到 O(log n)。注意它只是把长侧延迟处理并未消除递归本身——Python 解释器不会做尾调用优化TCO此处的收益来自长侧用 while 循环承接这一结构而非常规意义的尾调用改写。另外可以看到可视化块 4 中的partition是紧凑写法去掉了注释与类型注解交换写成(nums[i], nums[j]) (nums[j], nums[i])的括号元组形式——目的是让可视化窗口内单屏容纳完整程序逻辑与 QuickSort.partition 完全等价。六、算法特性与适用性小结结合主文档 quick_sort.md 的「Характеристики алгоритма」一节本实现nums[left]为主元、原地交换版的特性为时间复杂度平均 O(n log n)每层分区合计 O(n) 次比较、递归深度 O(log n)最坏 O(n²)每次分区切成0 n-1深度 n。算法不具自适应性已排序输入不会更快空间复杂度O(n)最坏时递归调用栈深度 n启用第五节的尾递归优化后最坏 O(log n)。排序本身原地进行无辅助数组稳定性不稳定。分区收尾时主元与相等元素的交换可能打乱等值元素的相对次序为何实践中快主文档给出三点——最坏情况概率极低、分区阶段对连续子数组的顺序扫描缓存命中率高对比堆排序的跳跃式访问、比较/交换的常数因子小。七、延伸阅读与仓库资源可视化代码文档本文主体ru/codes/pythontutor/chapter_sorting/quick_sort.md可运行完整源码含三个类与 Driver Coderu/codes/python/chapter_sorting/quick_sort.py教程主文档分区九步图解 复杂度分析 两项优化的动机说明ru/docs/chapter_sorting/quick_sort.md分区过程分步图step1~step9ru/docs/chapter_sorting/quick_sort.assets/pivot_division_step3.png同章其他排序算法源码归并、堆排等用于横向对比复杂度ru/codes/python/chapter_sorting运行方式Python 3 环境下直接执行python ru/codes/python/chapter_sorting/quick_sort.py文件自带__main__Driver Code依次演示三种实现并打印排序结果无需安装任何依赖。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考