Python快速排序：分治法与基准值解析

本文深入剖析Python中快速排序实现的常见陷阱与最佳实践，聚焦递归终止条件错误导致的栈溢出、基准值（pivot）选择不当引发的性能退化、原地交换失效、切片滥用破坏空间效率等核心问题，强调统一使用`if left >= right: return`作为安全递归基、采用随机或三数取中法选pivot、严格校验子数组下标合法性，并推荐在小规模子数组切换插入排序或改用迭代方案，帮助开发者写出健壮、高效、真正原地且可稳定通过LeetCode等严苛测试的快排代码。

为什么你的快速排序递归没出口，跑着就栈溢出了

递归终止条件写错是最常见的崩溃原因。快速排序必须在子数组长度 ≤ 1 时直接返回，而不是等 left >= right 才停——后者在空数组或单元素数组里可能跳过判断，导致无限递归。

实操建议：

• 统一用 if left >= right: return 作为递归基，别写 if left == right
• 划分后递归调用前，确保传入的下标范围合法：左半段是 quick_sort(arr, left, pivot_idx - 1)，右半段是 quick_sort(arr, pivot_idx + 1, right)；漏掉 -1 或 +1 就会重复处理 pivot 或越界
• Python 默认递归深度约 1000 层，对 10⁴ 量级数组容易爆栈；生产环境慎用纯递归，改用迭代或混入插入排序（如长度

选 pivot 用 arr[left] 还是 random.choice(arr[left:right+1])

固定取首/尾元素当 pivot，在已排序或逆序数组上会退化成 O(n²)，因为每次划分都极不均衡。随机选能大概率避开最坏情况，代价几乎可忽略。

实操建议：

• 别手写随机数逻辑，直接用 import random 后调 random.randint(left, right)，再和 arr[left] 交换
• 如果追求确定性（比如测试可复现），可用三数取中法：median_of_three(arr, left, mid, right)，但要注意 mid 计算用 (left + right) // 2，防整数溢出（Python 一般不溢出，但习惯要留）
• 内置 sorted() 不用你操心 pivot——它用的是 Timsort，不是快排

原地排序时 swap 写成 a, b = b, a 为什么有时不生效

Python 的元组解包赋值在列表索引场景下看似简洁，但若写成 arr[i], arr[j] = arr[j], arr[i]，本质是先求右值再批量赋左值，中间无副作用。问题出在「你以为 swap 了，其实没进 partition 函数作用域」——常见于把 swap 抽成独立函数却忘了传引用。

实操建议：

• 别封装 swap 函数，就在 partition 里直写 arr[i], arr[j] = arr[j], arr[i]，安全且清晰
• 如果非要用函数，得传 arr 和下标，返回新数组？不行——那就得用 arr.__setitem__，太绕，不值得
• 验证是否真 swap 成功：在 partition 结束后打印 arr[left:right+1]，别只信逻辑推导

LeetCode 提交报 Time Limit Exceeded 但本地秒出

本地跑得快，是因为小数据+缓存友好；线上用大随机数据+严格时间限制，暴露的是 pivot 策略和边界处理缺陷。尤其注意 Python 切片 arr[left:right+1] 会新建列表，O(n) 空间+时间开销，彻底破坏原地排序优势。

实操建议：

• 绝对不用切片传子数组，所有操作基于原数组+下标参数
• partition 函数里避免任何 list.append()、sorted()、sum() 等隐式遍历
• 提交前加一句 assert len(arr) 自测大数据，比等报错更快发现问题

分治本身不难，难在每层划分时 pivot 的位置、左右指针的停步条件、以及交换时机这三个点稍一松动，整个逻辑就滑向不可控。写完务必用 [3,1,4,1,5] 和 [5,4,3,2,1] 这类极端 case 过一遍指针移动过程。

到这里，我们也就讲完了《Python快速排序：分治法与基准值解析》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！