原地快排比新建列表更值得优先写，因其省内存、贴近经典算法描述，且避免了每次分区新建子列表的空间开销与常见错误。
为什么原地快排比新建列表更值得优先写
因为绝大多数实际场景下，list.sort() 或 sorted() 已经足够快且稳定，手写快排通常只为理解分治逻辑或满足特定约束（比如内存受限、需定制比较规则）。如果真要实现，原地分区（in-place partition）比每次新建左右子列表更省内存、也更贴近经典算法描述。
常见错误是直接用 [x for x in arr if x 拼接，这会触发多次列表复制，时间复杂度看似 O(n log n)，但常数项大，且空间复杂度退化为 O(n) —— 递归栈之外还额外占 O(n) 临时空间。
- 原地实现只需一个
arr数组 + 两个游标（low,high），空间复杂度严格 O(log n)（仅递归调用栈） - 分区过程用
while双指针向中间收缩，避免索引越界的关键是：先移动左指针再检查，右指针同理，且循环条件必须带等号（left ） - 基准值选
arr[low]最简单，但遇已排序数组会退化成 O(n²)；生产环境若坚持手写，建议用「三数取中」或随机选pivot_idx = random.randint(low, high)后交换到low位置
partition 函数里最容易写错的边界细节
分区函数返回的是「最终基准值落定的索引」，这个位置必须能正确划分左右子区间。很多初学者卡在：返回 right 还是 left？交换顺序该不该包含等于基准的元素？
标准 Lomuto 分区（以 arr[low] 为 pivot）的可靠写法是：
立即学习“Python免费学习笔记（深入）”；
def partition(arr, low, high):
pivot = arr[low]
left, right = low + 1, high
while left <= right:
while left <= right and arr[left] < pivot:
left += 1
while left <= right and arr[right] >= pivot:
right -= 1
if left < right:
arr[left], arr[right] = arr[right], arr[left]
arr[low], arr[right] = arr[right], arr[low]
return right- 注意内层
while的条件顺序：left 必须放在前面，否则可能越界访问 -
arr[right] >= pivot中的等号决定「等于基准的元素放右边」，这是保证稳定性无关但影响分区平衡的关键；若去掉等号，等于基准的元素可能被反复交换 - 最后一步必须是
arr[low], arr[right] = arr[right], arr[low]，不能用left—— 因为退出外层循环时，right才是小于 pivot 的最右位置
递归调用时 high 和 low 的传参陷阱
快排递归调用的两个子区间必须互斥且覆盖完整范围，稍不注意就会漏元素或重复排序。典型错误是写成 quicksort(arr, low, right-1) 和 quicksort(arr, right+1, high)，看起来对称，但当 right == low 时，左区间变成 (low, low-1) —— 这个区间合法（空区间），但右区间从 low+1 开始，漏掉了 arr[low] 自身？不，其实没漏，因为 arr[low] 已经被换到 right 位置并固定了。真正危险的是：当分区后 right == high，右子调用变成 (high+1, high)，合法；但左子调用若写成 (low, right-1) 就刚好覆盖 [low, high-1]，没问题。
- 安全写法统一用：
quicksort(arr, low, right - 1)和quicksort(arr, right + 1, high) - 递归终止条件必须是
if low ，不能写 <code>if low —— 否则单元素区间会无限递归（<code>right == low，子调用仍满足low ） - Python 默认递归深度约 1000，对长度 >1000 的列表会报
RecursionError；若必须处理大数据，要么改用迭代模拟栈，要么切到sys.setrecursionlimit()（不推荐）
和内置 sorted 对比时要注意的真实瓶颈
自己写的快排跑得比 sorted() 慢，不是因为你算法错，而是 CPython 的 sorted() 底层用的是 Timsort —— 它针对真实数据（部分有序、重复多）做了大量优化，且是 C 实现。你的 Python 版本哪怕逻辑完全正确，在 10⁴ 量级数据上就大概率慢 3–5 倍。
- 想验证算法逻辑？用小数组（
len(arr) ）测正确性，别比速度 - 想压测性能？关掉所有 print，用
timeit.timeit跑 100 轮取平均，且确保测试数组是随机生成的（避免快排在已排序输入下暴露出最坏性能） - 真正需要自定义排序逻辑时（比如按对象某个字段、或复合条件），优先用
key=参数，而不是重写整个排序——sorted(arr, key=lambda x: (x.a, -x.b))比手写快排清晰安全得多
递归拆分本身不难，难的是每个边界判断都得同时满足逻辑正确、不越界、不漏元素、不重复——这些地方错一个，结果就全乱。
