快速排序的核心思想很朴素：先挑一个“枢轴”（pivot），把数组按小于等于和大于它分成两边，再对两边递归排序。因为每次都在原问题里切一刀，这个过程天然适合分而治之。为什么它“快”？平均情况下，每次切得比较均匀，递归高度是 log n，每层分区要线性扫描一遍，总体就是 O(n log n)。

分区这一步到底做了什么：

分区（partition）就是把数组就地改造，保证左边都不大于枢轴，右边都不小于枢轴。常见有两种分区法：Lomuto 与 Hoare。Lomuto实现简单，典型做法是用一个“慢指针”维护“≤ pivot”的尾部；Hoare 的好处是交换次数更少，对重复元素更友好，也更接近很多教科书版本。这里我更喜欢 Hoare，它对大量重复值时的性能更稳定。

枢轴怎么选

理想情况是每次都切成差不多两半。最简单的枢轴是“取中间”，但遇到有序或近乎有序的输入时会很差。工程上常用“随机化”或“三数取中”（首中尾取中位数）。面试里随手用 random.randint 把枢轴随机化就足够了，能有效避开构造的最坏情况。

两种写法各有场景

如果只是讲思想、追求简洁，可以用“非原地”的函数式写法：把小于、等于、大于枢轴的部分分别递归。这很好读，但会产生额外列表，空间不够省。要贴近真实工程，建议写“原地”版本，时间复杂度相同，额外空间 O(1)（不计递归栈）。

import random

def quicksort_simple(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[random.randint(0, len(arr) - 1)]
    left  = [x for x in arr if x <  pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x >  pivot]
    return quicksort_simple(left) + mid + quicksort_simple(right)

这段代码读起来就像题意的翻译：选枢轴，分三堆，递归。它很适合讲解或写脚本，但会频繁分配内存和拷贝元素。

import random
from typing import List

def quicksort(nums: List[int]) -> None:
    """就地排序，平均 O(n log n)，最坏 O(n^2)。"""
    if len(nums) <= 1:
        return

    def partition(lo: int, hi: int) -> int:
        # 随机化枢轴，换到 lo 位置，使用 Hoare 分区
        p = random.randint(lo, hi)
        nums[lo], nums[p] = nums[p], nums[lo]
        pivot = nums[lo]
        i, j = lo - 1, hi + 1
        while True:
            i += 1
            while nums[i] < pivot:
                i += 1
            j -= 1
            while nums[j] > pivot:
                j -= 1
            if i >= j:
                return j
            nums[i], nums[j] = nums[j], nums[i]

    def _qsort(lo: int, hi: int) -> None:
        while lo < hi:
            mid = partition(lo, hi)
            # 先递归较小的一侧，再用循环“尾递归消除”，降低栈深
            if mid - lo < hi - (mid + 1):
                _qsort(lo, mid)
                lo = mid + 1
            else:
                _qsort(mid + 1, hi)
                hi = mid

    _qsort(0, len(nums) - 1)

# 小测试
if __name__ == "__main__":
    a = [5, 1, 1, 2, 0, 0, 9, 3, 7, 7]
    quicksort(a)
    print(a)  # 已原地有序

这份实现有几个点值得注意：

Hoare 分区返回的是“分割点” j，保证 [lo..j] ≤ pivot ≤ [j+1..hi]。两侧继续排序即可。 随机枢轴能有效缓解退化；不随机的“取端点”在已排序数组上会退化到 O(n^2)。 尾递归消除：每次只递归较小一侧，较大一侧用循环展开，这样递归深度上界变成 O(log n)，避免深栈。 重复元素：Hoare 的双向扫描对大量相等值更友好，数组里有很多和枢轴相等的数字时，交换次数和栈深会更稳定。

正确性与边界考虑

空数组和单元素数组天然有序，函数入口快速返回。分区循环里，双指针分别“找到第一个 ≥ pivot 的左指针”和“第一个 ≤ pivot 的右指针”，若 i < j 就交换，直到交错时返回分割点。这个不变量保证了分区结束时的两边已经相对有序。递归区间选择为 [lo..mid] 与 [mid+1..hi]，不重不漏。

复杂度与稳定性

平均时间复杂度 O(n log n)，最坏 O(n^2)（不断选到极端枢轴导致劈得不均）。通过随机化或三数取中，最坏情况概率极低。空间复杂度就地是 O(1)，但递归栈会占用 O(log n) 平均空间。快速排序不稳定，相等元素的相对顺序可能改变，如果你需要稳定排序，面试里可以顺带提一下 Python 内置的 list.sort() 使用 Timsort，稳定而且对部分有序输入有更好表现。

列表切片会复制数据，所以非原地版本虽然写起来很优雅，但在大数组上代价明显；原地版本避免了这类开销。random.randint 会带来轻微随机数开销，但相比退化风险，这是值得的。若对可复现性有要求，可以在调用前设定 random.seed()。另外，Python 的递归深度默认大约是千级，极端情况下可能触发 RecursionError，上面的尾递归消除策略能显著降低风险；实在需要，还可以改写成手工栈的迭代版。

什么时候不该用你自己写的快排

在工程里，自己实现排序通常不是最佳选择：内置排序经过大量优化，稳定且对局部有序、重复多等情况有专门优化。面试题写快排，更多是考察你对分而治之、指针移动、不变量维护以及复杂度、边界的把握。能写出原地版本、解释枢轴选择与尾递归消除，基本就到位了。

快速排序的关键在“选枢轴 + 分区 + 递归”。掌握 Hoare 分区可以更自然地处理重复元素；随机枢轴能规避构造数据；尾递归消除能保护栈空间。面试里先给出简洁版讲思路，再给出原地版展现工程意识，是一个清晰且稳妥的答题方式。

更多相关技术内容咨询欢迎前往并持续关注好学星城论坛了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。