快速排序的分区、递归过程如何实现？

核心回答

快速排序先选一个基准值，把数组按它分区，再递归处理较小和较大的部分。**分区只保证两侧与基准的大小关系，不保证两侧内部已经有序。**当待排区间为空或只剩一个元素时结束。

一种适合重复值的实现是三路分区：把当前区间整理成“小于基准、等于基准、大于基准”三段，等于段无需继续排序，只处理另外两段。下面随机选基准，并把较长一侧改为循环、只递归较短一侧，控制调用栈深度。

在随机选基准的通常分析下，期望时间为 O(n log n)，仍有 O(n²) 的最坏时间；这里的三路写法在全相等输入上只需扫描一遍。代码原地修改数组，递归栈最坏为 O(log n)，不属于稳定排序。

Python 实现

from random import randrange


def partition(nums: list[int], left: int, right: int) -> tuple[int, int]:
    pivot = nums[randrange(left, right + 1)]
    lt, i, gt = left, left, right

    while i <= gt:
        if nums[i] < pivot:
            nums[lt], nums[i] = nums[i], nums[lt]
            lt += 1
            i += 1
        elif nums[i] > pivot:
            nums[i], nums[gt] = nums[gt], nums[i]
            gt -= 1  # 换来的元素尚未检查，i 不前进
        else:
            i += 1

    return lt, gt  # 闭区间 [lt, gt] 中都等于 pivot


def quick_sort(nums: list[int]) -> list[int]:
    def sort(left: int, right: int) -> None:
        while left < right:
            lt, gt = partition(nums, left, right)
            if lt - left < right - gt:
                sort(left, lt - 1)
                left = gt + 1
            else:
                sort(gt + 1, right)
                right = lt - 1

    sort(0, len(nums) - 1)
    return nums

quick_sort 返回的仍是传入的同一个列表；如果调用方需要保留原数据，可以先复制再传入，这份额外复制空间应另算。

分区的四个区间分别表示什么？

循环中保持以下关系，区间两端均按下面的括号约定理解：

• [left, lt)：严格小于基准。
• [lt, i)：等于基准。
• [i, gt]：还没检查。
• (gt, right]：严格大于基准。

若当前值小于基准，就把它放到左段末尾，并同时推进 lt、i；若大于基准，就交换到右段，并缩小 gt。后一种情况不能推进 i，因为从右端换过来的元素还没有分类。等于基准则直接推进 i。

每一步都使未知区间缩小，直到 i > gt。因为基准取自当前区间，结束时等于段至少含一个元素，不会出现分区后还对原区间重复递归的问题。

例如对 [4, 2, 4, 1, 5, 4, 3]，假设这次选中基准 4，分区后可以得到 [2, 1, 3, 4, 4, 4, 5]。左边的 [2, 1, 3] 还没排好，但已经全部小于 4；三个 4 不必再参与递归。

递归边界为什么这样写？

当前使用闭区间 [left, right]，所以 left >= right 时无需处理。分区返回的是整段等于基准的左右边界，后续区间分别是 [left, lt - 1] 与 [gt + 1, right]，两边都排除等于段。

普通写法可以对这两段都递归。上面的代码每次只递归较短的一段，较长的一段更新左右边界后继续循环。递归进入的子区间最多是原区间的一半，因此调用栈深度为 O(log n)，即便某次分区极不均衡，也不会因此形成 O(n) 层调用栈。

这项改动控制的是栈空间，不会把最坏时间也自动变为 O(n log n)。若连续选中极端基准，比较和分区的总工作量仍可能达到 O(n²)。

怎样理解复杂度和优化？

一次分区扫描当前 m 个元素，耗时 O(m)。若划分较均衡，每层总工作量约为 O(n)，层数约为 log n，因而得到 O(n log n)；若每次只排除一个元素，就会累积成 n + (n - 1) + … + 1 的平方级工作量。

随机选基准降低了输入顺序持续造成坏划分的风险，但不提供最坏时间保证。三路分区则让大量重复值一次退出后续递归，解决的是另一类问题。

工程上还可对小区间使用插入排序，或在分区深度异常时切换到堆排序形成内省排序。具体阈值与实现有关，不能仅凭“叫快速排序”就认定它在所有数据和语言里最快。

常见追问

为什么说它不稳定？

稳定性要求相同键的记录保留原相对顺序。分区交换可能改变这个顺序：把 2a、2b、1 按基准 2 分类时，1 与 2a 交换，就可能变为 1、2b、2a。数值排对了，相同键的记录顺序却变了。

分区为什么有的返回一个下标，有的返回两个？

取决于分区契约。某些写法把一个基准放到最终位置，返回它的下标；Hoare 的部分写法返回两段的分界，基准不一定就位；这里返回整个等于段。递归边界必须与采用的契约配套，不能把不同模板的返回值和边界拼在一起。

面试时最容易写错什么？

常见错误是混用开闭区间、交换未知元素后漏检、重复值导致指针不动，以及递归没有缩小。先解释分区中每一段的含义，再写代码，比只背交换语句更容易自查。

参考资料