Quicksort 的两种不同范式比较

前情提要

事情起源于我在某一天刷 leetcode 题时，遇到了这么一道题目：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

这便是个标准的 Quicksort 问题，每次 partition 之后获得的 pivot 位置，有着前面的元素都比它小，后面的元素都比它大的特性。这样我们只需要选取一边进行递归，理想情况下 $ T(n) = T(n/2) + O(n) $，根据 Master) 定理，我们可以求出时间复杂度为 $ O(n) $。

然而，当我写完代码提交后，发现虽然通过了所有用例，但是时间却远远超过了 $ O(n) $，于是上网搜索，得到了 Quicksort 的两种范式。

两种范式

首先介绍一下两种范式：

Lomuto partition scheme

algorithm partition(A, L, R) is
    pivot := A[R]
    i := L
    for j := L to R - 1 do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
        end if
    swap A[i] with A[R]
    return i

Hoare partition scheme

algorithm partition(A, L, R) is
    pivot := A[R]
    i := L - 1
    j := R
    while i < j do
        repeat
            j := j - 1
        until A[j] <= pivot
        repeat
            i := i + 1
        until A[i] >= pivot
        if i < j then
            swap A[i] with A[j]
        end if
    swap A[i] with A[R]
    return i

两种范式的比较

乍一看，两种范式的代码逻辑差别不大，而且 Lomuto partition scheme 的代码更加简洁且易懂，但实际上，Hoare partition scheme 的性能要优于（或在某些情况下，远优于）Lomuto partition scheme。下面我们来仔细分析一下两种范式的性能。

在开始之前，我们只关注 Comparison 和 Swap 的次数，并由此来推定程序的性能。我们很难分析一个算法在任意条件下的性能，因此我们考虑这样一个 Model：数组是一个$[1, n]$集的随机排列。

注意到这样的性质：每次 partition 之后，pivot 的位置都是确定的，并根据算法正确性，两边分别是$[1, p-1]$和$[p+1, n]$的随机排列。因此我们可以得到如下的递归式：

$$ C_n = pc_n + \frac{1}{n}\sum_{p=i}^{n}(C_{p-1} + C_{n-p}) $$

这里 $C_n$ 表示数组长度为 $n$ 时的总 Cost，而 $pc_n$ 表示 partition 的 Cost。根据对称性，我们有 $C_{n-p} = C_{p-1}$，因此我们可以得到如下的递归式：

$$ \begin{aligned} C_n &= pc_n + \frac{2}{n}\sum_{p=i}^{n}C_{p-1}, n \geq 2 \\ C_0 &= C_1 = 0 \end{aligned} $$

因此

$$ nC_n - (n-1)C_{n-1} = npc_n - (n-1)pc_{n-1} + 2C_{n-1} $$

整理而后有 $(1)$ 式：

$$ \begin{aligned} \frac{C_n}{n+1} &= \frac{C_{n-1}}{n} + \frac{npc_n-(n-1)pc_{n-1}}{n(n+1)} \\ &= \frac{C_2}{3} + \sum_{i=3}^{i}\frac{ipc_i-(i-1)pc_{i-1}}{i(i+1)} \end{aligned} $$

现在我们考虑两种范式在 Comparison 上的次数差别。对于 Hoare partition scheme，我们发现，在 partition 中，i 与 j 每次移位都会进行一次比较，而最终我们知道有 i = j + 1 关系式，因此 partition 中总比较次数，即 $pc_n$，为 $n+1$。而对于 Lomuto partition scheme，我们同样有移位一次比较一次，不过我们最终循环变量位置落在 n 上，因此 $pc_n = n-1$。

这样看来，两者的 Comparison 次数差距并不大，性能瓶颈似乎不在此，不过我们还是将上界 $pc_n = n+1$ 代入 $(1)$ 式中，得到：

$$ \begin{aligned} C_n &= (n+1)(1+\sum_{i=3}^{n}\frac{i(i+1)-i(i-1)}{i(i+1)}) \\ &= (n+1)(1+\sum_{i=3}^{n}\frac{2}{i(i+1)}) \\ &= 2(n+1)(H_{n+1}-\frac43) \\ &where \ H_n = \sum_{i=1}^{n}\frac{1}{i} \end{aligned} $$

最后将结果交给万能的 Mathematica，得到无穷远处渐进式为：

$$ \begin{aligned} C_n &\sim n(2\log n+2\gamma-\frac83)+2\log n+2\gamma+\frac13+\frac{5}{6n}-\frac1{6n^2} + O(\frac{1}{n^3}) \\ &\sim 2n\log n - 1.5123n + O(\log n) \\ \end{aligned} $$

经过上述分析，可以看出两种范式的 Comparison 次数差别并不大，那就意味着 Swap 次数可能是性能瓶颈。下面我们继续分析 Swap 次数。

我们首先分析两个范式的 $pc_n$。对于 Lomuto partition scheme，我们发现，对元素集合 $[1, n]$，每次 partition 都会对所有比 pivot 小的元素进行 Swap，因此 Swap 次数为 $p-1+1=p$（注意循环外还有一次 Swap）。则：

$$ pc_n = \frac1n\sum_{p=1}^np = \frac{n}2 + \frac12 $$

现在考虑 Hoare partition scheme。其需要 Swap 的情况是对于选定的 pivot 对应的下标 $p$，在下标范围 $[1, p-1]$ 中比 pivot 大的元素的个数（或右侧比 pivot 小的元素的个数），即我们在 $n-1$ 个数中随机取 $p-1$ 个数（不放回），取出共计 $n-p$ 个满足条件的数的数量 $k$。因此 $k$ 满足 Hypergeometric 分布，有 $k \sim \text{Hyp}(n-1, n-p, p-1)$ ，其期望为 $\frac{(p-1)(n-p)}{n-1}$ （相似的，这里也省略了一次循环外 Swap，后文计算时需要加上），因此 Swap 次数为：

$$ pc_n = 1+\frac1n\sum_{p=1}^n\frac{(p-1)(n-p)}{n-1} = \frac{n}6 - \frac13 + 1 = \frac{n}6 + \frac23 $$

可以看出，Hoare partition scheme 的 Swap 次数足足接近 3 倍小于 Lomuto partition scheme 的 Swap 次数。我们将 Hoare 的 $pc_n$ 代入 $(1)$ 式中，得到：

$$ \begin{aligned} C_n &= (n+1)(\frac13+\sum_{i=3}^{n}\frac{i(i+4)-(i-1)(i+3)}{6i(i+1)}) \\ &= (n+1)(\frac13+\sum_{i=3}^{n}(\frac1{2i}-\frac1{6(i+1)})) \\ &= \frac13(n+1)(H_{n+1}-\frac13)-\frac12 \\ &where \ H_n = \sum_{i=1}^{n}\frac{1}{i} \end{aligned} $$

将结果交给 Mathematica，得到无穷远处渐进式为：

$$ \begin{aligned} C_n &\sim \frac13n\log n + \frac{3\gamma-1}9n + O(\log n) \\ &\sim \frac13n\log n + 0.08129n + O(\log n) \\ \end{aligned} $$

特殊情况

在最后，我们来分析一下两种范式在特殊情况下的性能。对于完全有序的数组，Hoare's 不进行任何 Swap，而 Lomuto's 仍然需要进行大概 $n/2$ 次 Swap 操作。在这种情况下，Hoare's 的性能略优于 Lomuto's。

但是对于元素全部相同（或几乎相同）的数组，Hoare's 会对每一个 Pair 进行 Swap，但是由于两个下标 $i$ 和 $j$ 会在中间相遇，因此 QuickSort 所需时间仍然是 $O(n\log n)$。而 Lomuto's 的比较始终为真，因此不仅每次比较都要 Swap，而且还需要对每个元素都要比较！也就是说，Lomuto's 所需 Swap 次数大概是 Hoare's 的 2 倍，更恐怖的是，由于 predicate 始终为真，partition 返回的下标总是 $n-1$，算法也因此退化为 $O(n^2)$。

Hypergeometric distribution - Wikipedia
algorithms - Quicksort Partitioning: Hoare vs. Lomuto - Computer Science Stack Exchange
Java 7's Dual Pivot Quicksort
analyze the sequence (n+1)(H(n+1)-1/3)/3 -1/2, H is Harmonic series - Wolfram|Alpha