hello-algo 快速排序深度解析：哨兵划分、三数取中与递归深度优化（附 Python Tutor 可视化）

本文围绕 hello-algo 仓库中《快速排序》一章的 Python Tutor 逐步可视化教程（codes/pythontutor/chapter_sorting/quick_sort.md）展开，系统讲解快速排序的核心操作“哨兵划分”、分治递归流程、时间/空间复杂度与稳定性特征，并结合 Python 源码实现 深入剖析“三数取中”基准数优化与“仅递归较短子数组”的递归深度优化两种实战技巧。读完本文，你将能够独立实现标准快速排序及其两种经典优化，并理解每一步指针移动与元素交换的精确语义。

哨兵划分：快速排序的核心操作

快速排序（quick sort）是一种基于分治策略的排序算法，运行高效、应用广泛。它的核心操作是“哨兵划分（partition）”，目标是：选择数组中的某个元素作为“基准数（pivot）”，将所有小于基准数的元素移到其左侧，而将大于基准数的元素移到其右侧。

哨兵划分的具体流程为：

1. 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端；
2. 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素；
3. 循环执行步骤 2，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。

哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足“左子数组任意元素 $\leq$ 基准数 $\leq$ 右子数组任意元素”。接下来只需对这两个子数组分别排序即可。哨兵划分的实质，是将一个较长数组的排序问题简化为两个较短数组的排序问题。

对应 hello-algo 的 Python 实现位于 QuickSort.partition，完整代码如下：

def partition(self, nums: list[int], left: int, right: int) -> int:
    """哨兵划分"""
    # 以 nums[left] 为基准数
    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  # 返回基准数的索引

实现上有几个关键点值得注意：

• 内外双循环的边界条件：内层两个 while 都带有 i < j 的前置判断，这保证了指针交叉前不会越过对方；
• 比较运算符采用 $\geq$ 和 $\leq$：允许相等元素停在指针位置，因此划分结果只满足“左右两侧元素不越过基准数两侧”的弱不变式，而不强制相等元素归到某一侧——这正是快速排序“非稳定”的来源之一；
• 最后一次交换：循环结束时 i == j 指向分界线，把基准数与 nums[i] 交换，基准数随即“就位”，函数返回 i 作为基准数的最终索引。

分治策略：整体算法流程

在哨兵划分的基础上，快速排序的整体流程为：

1. 首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组；
2. 然后，对左子数组和右子数组分别递归执行“哨兵划分”；
3. 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

对应实现在 QuickSort.quick_sort：

def quick_sort(self, nums: list[int], left: int, right: int):
    """快速排序"""
    # 子数组长度为 1 时终止递归
    if left >= right:
        return
    # 哨兵划分
    pivot = self.partition(nums, left, right)
    # 递归左子数组、右子数组
    self.quick_sort(nums, left, pivot - 1)
    self.quick_sort(nums, pivot + 1, right)

从源码结构看，递归边界条件 if left >= right: return 覆盖了“区间长度为 1”和“区间为空”两种情形：前者是天然的递归终止条件，后者则发生在基准数恰好处于区间端点、某一侧子数组为空时。驱动代码对三种实现分别用 nums = [2, 4, 1, 0, 3, 5] 作测试输入，执行后应输出 [0, 1, 2, 3, 4, 5]（见 Driver Code）。

算法特性：时间、空间与稳定性

结合 中文文档的算法特性一节，快速排序的关键特性如下：

特性	结论	依据
时间复杂度（平均）	$O(n \log n)$，非自适应	平均情况下哨兵划分的递归层数为 $\log n$，每层总循环数为 $n$
时间复杂度（最差）	$O(n^2)$	每轮划分都产生长度为 $0$ 和 $n-1$ 的两个子数组时，递归层数达到 $n$，每层循环数为 $n$
空间复杂度（最差）	$O(n)$ 栈帧空间	输入完全倒序时递归深度达到 $n$；排序在原数组上进行，不借助额外数组（原地排序）
稳定性	非稳定排序	哨兵划分最后一步，基准数可能会被交换至相等元素的右侧

以 QuickSort.quick_sort 的实现验证：两次递归调用 quick_sort(nums, left, pivot - 1) 与 quick_sort(nums, pivot + 1, right) 是顺序执行的，因此栈帧占用由“递归树高度”而非“单次路径上并发调用的数量”决定——对于偏斜划分，栈深度随输入偏斜程度线性增长，最差 $O(n)$ 与文档结论一致。

快速排序为什么快

尽管快速排序的平均时间复杂度与归并排序和堆排序同为 $O(n \log n)$，通常它的实际效率更高，仓库文档给出的原因有三：

• 出现最差情况的概率很低：虽然最差时间复杂度为 $O(n^2)$，不如归并排序稳定，但在绝大多数情况下快速排序都能在 $O(n \log n)$ 下运行；
• 缓存使用效率高：执行哨兵划分时，系统可将整个子数组连续加载到缓存，元素访问效率高；而堆排序这类算法需要跳跃式访问元素，缺乏这一特性；
• 复杂度的常数系数小：在三种 $O(n \log n)$ 算法中，快速排序的比较、赋值、交换等操作总数量最少，这与“插入排序比冒泡排序快”的原因类似。

基准数优化：三数取中

快速排序在某些输入下的时间效率可能降低。极端例子：输入数组完全倒序时，由于选择最左端元素作为基准数，每次哨兵划分后基准数都被交换至最右端，左子数组长度为 $n-1$、右子数组长度为 $0$。如此递归下去，每轮都有一个子数组长度为 $0$，分治策略失效，快速排序退化为“冒泡排序”的近似形式。

为避免这种情况，可以优化基准数的选取策略。一种朴素做法是随机选取一个元素作基准数；但需要注意，编程语言通常生成的是伪随机数，若针对伪随机数序列构造特定测试样例，效率仍可能劣化。

更稳健的做法是三数取中（median-of-three）：选取数组的首、尾、中点三个候选元素，取它们的中位数作为基准数，使基准数“既不太小也不太大”的概率大幅提升。仓库中 QuickSortMedian.median_three 的实现无需排序，只用两轮大小比较即可定位中位数的索引：

def median_three(self, 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

其逻辑是：若 m 的值介于 l 和 r 之间（两种单调方向都考虑），返回 mid；否则若 l 介于 m 和 r 之间，返回 left；三者都不满足时中位数必为 r，返回 right。

随后 QuickSortMedian.partition 在中位数确定后，先将中位数交换到数组最左端，再复用与标准版完全相同的哨兵划分逻辑：

def partition(self, nums: list[int], left: int, right: int) -> int:
    """哨兵划分（三数取中值）"""
    # 以 nums[left] 为基准数
    med = self.median_three(nums, left, (left + right) // 2, right)
    # 将中位数交换至数组最左端
    nums[left], nums[med] = nums[med], nums[left]
    # 以 nums[left] 为基准数
    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  # 返回基准数的索引

采用三数取中后，时间复杂度劣化至 $O(n^2)$ 的概率大大降低；也可以选取更多候选元素进一步提升稳健性。对应的 quick_sort 递归入口见 QuickSortMedian.quick_sort，与标准版结构相同，只是划分阶段多了一次“选基准”的前置操作。

递归深度优化：只递归较短的子数组

在某些输入下，快速排序可能占用空间较多。以完全有序的输入为例，设递归中子数组长度为 $m$，每轮哨兵划分都产生长度为 $0$ 的左子数组和长度为 $m-1$ 的右子数组，每层递归只把问题规模减少一个元素，递归树高度达到 $n-1$，需要 $O(n)$ 大小的栈帧空间。

hello-algo 给出的优化方案是：每轮划分完成后比较两个子数组的长度，仅对较短的子数组执行递归，较长的一侧改用循环（尾调用消除思想）继续处理。由于较短子数组长度不超过 $n/2$，递归深度被限制在 $\log n$ 以内，最差空间复杂度随之优化至 $O(\log n)$。

QuickSortTailCall.quick_sort 的实现如下，partition 与标准版完全一致（L84-L97）：

def quick_sort(self, nums: list[int], left: int, right: int):
    """快速排序（递归深度优化）"""
    # 子数组长度为 1 时终止
    while left < right:
        # 哨兵划分操作
        pivot = self.partition(nums, left, right)
        # 对两个子数组中较短的那个执行快速排序
        if pivot - left < right - pivot:
            self.quick_sort(nums, left, pivot - 1)  # 递归排序左子数组
            left = pivot + 1  # 剩余未排序区间为 [pivot + 1, right]
        else:
            self.quick_sort(nums, pivot + 1, right)  # 递归排序右子数组
            right = pivot - 1  # 剩余未排序区间为 [left, pivot - 1]

实现细节值得细读：

• 循环替代一层递归：while left < right 取代了标准版的 if left >= right: return，把“处理较长子数组”从函数调用变成了修改 left / right 后继续循环；
• 较短侧判定：pivot - left < right - pivot 比较左右子数组的“长度”（元素个数即索引跨度），短侧递归、长侧更新边界后进入下一轮循环；
• 不变式保持：每一轮循环中，nums[left..right] 始终是待排序区间，区间外的元素都已就位，因此循环退出（left >= right）时整个数组有序。

由于 Python 解释器本身不做尾调用优化，这种“手动消除一侧递归”的写法是控制栈深度的有效手段。

用 Python Tutor 逐步观察每一次交换

Python Tutor 可视化文件 中为上述四段核心代码分别内嵌了逐步可视化页面，与源码中的 [file]-[class]-[func] 标记一一对应：

可视化条目	对应源码	观察重点
[file]{quick_sort}-[class]{quick_sort}-[func]{partition}	QuickSort.partition	单趟哨兵划分：i/j 双指针移动与逐对交换，直到基准数归位
[file]{quick_sort}-[class]{quick_sort}-[func]{quick_sort}	QuickSort.quick_sort	分治递归全过程：递归进入/返回与每次划分后的数组状态
[file]{quick_sort}-[class]{quick_sort_median}-[func]{partition}	QuickSortMedian.partition	三数取中：中位数先被交换至左端，再执行标准哨兵划分
[file]{quick_sort}-[class]{quick_sort_tail_call}-[func]{quick_sort}	QuickSortTailCall.quick_sort	递归深度优化：短侧递归、长侧循环，栈帧数量始终可控

以 [2, 4, 1, 0, 3, 5] 为例，第一趟以 2 为基准的哨兵划分结束后数组变为 [1, 0, 2, 4, 3, 5]，基准数 2 落在索引 2，左子数组 [1, 0] 与右子数组 [4, 3, 5] 各自独立递归——这与上文流程图展示的状态完全一致。在 Python Tutor 中逐步执行时，建议重点观察：内层 while 中指针空转（不交换）的轮次、i 与 j 相遇时刻 nums[i] 与基准数的相对位置，以及最后一次 nums[i], nums[left] = nums[left], nums[i] 交换后数组如何形成“左 $\leq$ 基准 $\leq$ 右”的三段结构。

小结

hello-algo 仓库通过 Python 源码 与 中文文档 共同刻画了快速排序的完整知识脉络：以 QuickSort 实现经典的哨兵划分与分治递归（平均 $O(n\log n)$、原地、非稳定），以 QuickSortMedian 通过三数取中降低基准数偏斜的概率，再以 QuickSortTailCall 通过“短侧递归、长侧循环”把最差栈深度压到 $O(\log n)$。配合 Python Tutor 逐步可视化，你可以逐指令验证每一次指针移动和元素交换，把“快速排序为什么快”从结论变成可观察的事实。