快速排序

快速排序（quicksort）选一个基准值，把待排序区间分成“小于基准”“等于基准”“大于基准”三段，再分别排序两侧。这里采用三路划分，是为了让大量重复值一次归位；它与只把一个基准元素放到最终位置的两路实现同属快速排序，但划分状态不同。

一次三路划分

取 $(6, 3, 6, 2, 8, 3, 5)$ ，选首项 6 为基准。划分完成后，数组可能成为 $(3, 2, 5, 3 ∣ 6, 6 ∣ 8)$ 。竖线只标分区边界，不是数组元素；左侧每项小于 6，中间每项等于 6，右侧每项大于 6。此时两个 6 无须参与后续递归，只要再分别排序长度为 4 和 1 的两侧区间。

数组六三六二八三五以六为基准，三路划分后小于六区为三二五三，等于六区为六六，大于六区为八 — 三路划分只保证三个区域的大小关系；左侧的 3、2、5、3 此时还没有排好序。

用三个下标 $l t, i, g t$ 把当前半开区间 $[l o, h i)$ 分成四段：

$[l o, l t)$ ：小于基准。
$[l t, i)$ ：等于基准。
$[i, g t)$ ：尚未检查。
$[g t, h i)$ ：大于基准。

开始时 $l t = i = l o, g t = h i$ ，四段条件显然成立。检查 $a_{i}$ ：它小于基准，就与 $a_{l t}$ 交换并同时推进 $l t, i$ ；它等于基准，只推进 $i$ ；它大于基准，就先减小 $g t$ ，再与 $a_{g t}$ 交换，暂不推进 $i$ ，因为换过来的数尚未检查。

在示例中，读到 8 时把它与右端的 5 交换，5 会落到待检查位置；接下来仍要比较这个 5。每一步都使未检查区间 $[i, g t)$ 缩短一格，最终 $i = g t$ ，恰得到图中的三个区域。

排序的正确性

划分时四段条件保持不变。例如遇到小于基准的数， $a_{l t}$ 原先位于等于区，交换后左区多一个小值；它移到 $i$ 处仍属于等于区，两个下标一起前进即可。遇到大于基准的数，右区多一个大值，换来的未知数留待下一轮判断。循环结束后等于区已经处在所有小值与大值之间。

两侧递归处理的是比原区间更短的区间，因此终会停在长度 0 或 1。假设递归分别将左右两侧排好序，因为左侧每项小于基准、中间等于基准、右侧每项大于基准，三段接起来就是完整有序列。重复值并未被误分到两个递归分支。

快速排序的三路划分

跟随三个下标，看未检查区间怎样缩短。

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

此版本直接改动传入的列表，并固定选当前区间首项为基准，以便代码、例子与图一致。函数返回同一列表，便于查看结果。

Python 3

def quick_sort(a):
    def sort(lo, hi):
        if hi - lo < 2:
            return
        pivot = a[lo]
        lt = i = lo
        gt = hi
        while i < gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                gt -= 1
                a[i], a[gt] = a[gt], a[i]
            else:
                i += 1
        sort(lo, lt)
        sort(gt, hi)

    sort(0, len(a))
    return a


if __name__ == "__main__":
    values = [6, 3, 6, 2, 8, 3, 5]
    assert quick_sort(values) == [2, 3, 3, 5, 6, 6, 8]
    assert quick_sort([]) == []
    assert quick_sort([4, 4, 4]) == [4, 4, 4]

代价与次序

一次划分检查每个元素一次，成本为 $Θ (n)$ 。若每次两侧规模接近各半，递归深度约为 $\log_{2} n$ ，总时间为 $Θ (n \log n)$ 。本代码固定选首项，不能保证平衡：已经有序且值互异的输入可使一侧空、另一侧只少一个元素，比较量达到 $Θ (n^{2})$ ，递归栈最坏也会有 $O (n)$ 层。随机选基准可以改变期望表现，但那是另一项算法条件，不能据此把本代码的最坏界改成 $O (n \log n)$ 。

三路划分在全为同一值时只扫一遍，两个严格大小区都为空，时间为 $Θ (n)$ 。它不保证稳定性：例如三张按数值排序的卡片 $(1, 2_{B}, 2_{C})$ ，划分时首项 1 使右端的 $2_{C}$ 换到 $2_{B}$ 前面。若必须保持相等关键字的原次序，可读归并排序。

参考资料

TheAlgorithms/Python：quick_sort_3_partition.py：三路分区选题参考；本站用半开区间和独立编写的代码。
Sedgewick、Wayne，Quicksort：划分、不平衡情形与三路排序。
先修：算法与复杂度；对照：归并排序。