当使用快速排序对具有不同键的 N 项数组进行排序时，大小为 0、1 和 2 的子数组的预期数量是多少？

Question

我正在阅读 Robert Sedgewick 的书 Algorithms 4th edition，他有以下练习题：What is the expected number of subarrays of size 0, 1和 2 当使用快速排序对具有不同键的 N 项数组进行排序时？

然后他说，如果你有数学倾向，就做数学，如果没有，运行实验，我有运行实验，看起来像大小为 0 和 1 的数组具有完全相同的出现次数，大小为 2 的数组仅为出现次数的一半。

有问题的快速排序版本是 2 路分区。

我知道当分区项是子数组中的 smallest/biggest 时，我们得到大小为 0 的子数组，因此随后的 2 次排序调用将是

sort(a, lo, j-1); // here if j-1 < lo, we have an array of size 0
sort(a, j+1, hi); // here if j+1 > hi, we have an array of size 0

当分区项是第 2 个到第一个 smallest/biggest 项时，大小为 1 的数组发生，当它是第 3 个到第一个 smallest/biggest 项时，大小为 2。

那么，我究竟如何推导出数学公式？

这是 C# 中的代码

class QuickSort
{
    private static int zero = 0, one = 0, two = 0;
    private static int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
    {
        T v = a[lo];
        int i = lo, j = hi + 1;
        while(true)
        {
            while(Alg.Less(a[++i], v)) if(i == hi) break;
            while(Alg.Less(v, a[--j])) if(j == lo) break;
            if(i >= j) break;
            Alg.Swap(ref a[i], ref a[j]);
        }
        Alg.Swap(ref a[lo], ref a[j]);
        return j;
    }
    private static void Sort<T>(T[] a, int lo, int hi) where T : IComparable<T>
    {
        if(hi < lo) zero++;
        if(hi == lo) one++;
        if(hi - lo == 1) two++;

        if(hi <= lo) return;
        int j = Partition(a, lo, hi);

        Sort(a, lo, j - 1);
        Sort(a, j + 1, hi);
    }
    public static void Sort<T>(T[] a) where T : IComparable<T>
    {
        Alg.Shuffle(a);
        int N = a.Length;
        Sort(a, 0, N - 1);
        Console.WriteLine("zero = {0}, one = {1}, two = {2}", zero, one, two);
    }
}

有证据表明，平均而言，快速排序使用 2NlnN ~ 1.39NlgN 比较来对具有不同键的长度为 N 的数组进行排序。

我猜我们可以想到 1.39NlgN 因为我们进行了 N 次比较 ~lgN 次，所以平均而言我们将数组分成两半，因此在某些时候我们将留下成对进行比较，并且由于只有对进行比较，例如：<1,2>、<3,4>、<5,6> 等...，我们将在划分它们之后得到大小为 0 和 1 的子数组，只有证明大小为 0 和 1 的频率更高，但我仍然不明白为什么大小为 2 的频率几乎恰好是频率的一半。

Answer 1

QuickSort 会在位置 k 处递归地将数组分成两个较小的数组。 k 可以从 1 到 n。每个k都有相同的出现概率。令 C0(n) 为 0 大小子集的平均出现次数，C1(n)、C2(n) 为 1 大小子集和 2 大小子集相同。

除了初始条件外，每一个都满足：

C(n) = 1/n sum(C(k-1) + C(n-k) for k=1..n)

求和的两部分相同但求和的顺序相反，所以：

C(n) = 2/n sum(C(k-1) for k=1..n)

或

n*C(n) = 2*sum(C(k-1) for k=1..n)

假设n和n-1都不是初始条件的一部分，我们可以通过从两边减去(n-1)C(n-1)来简化：

n*C(n) - (n-1)C(n-1) = 2*C(n-1)

或

C(n) = (n+1)/n * C(n-1)

从递归关系导出结果

我们现在有一个递归关系 C(n)，它同样适用于 C0、C1 和 C2。

对于C0，我们有初始条件C0(0)=1、C0(1)=0。我们计算 C0(2) 得到 1，然后我们可以对 n>2 应用简化的递归关系 C0(n) = (n+1)/n * C0(n-1) 得到一般结果 C0(n)=(n+1)/3.

对于C1，我们有初始条件C1(0)=0、C1(1)=1。和以前一样，我们计算 C1(2) 得到 1，并应用与计算 C0 相同的过程得到一般结果 C1(n)=(n+1)/3.

对于C2，我们有初始条件C2(0)=C2(1)=0和C2(2)=1。这次我们计算 C2(3) = 1/3 * 2 * (C2(0) + C2(1) + C2(2)) = 2/3。然后应用简化的递归关系来推断一般结果 C2(n)=(n+1)/4 * C2(3) = (n+1)/4 * 2/3 = (n+1)/6.

结论

我们已经显示了当对大小为 n 的数组进行快速排序时，大小为 0 和大小为 1 的子数组的平均出现次数为 (n+1)/3。对于大小为 2 的子阵列，我们已经证明它是 (n+1)/6。

这证实了您最初的观察，即大小为 2 的子集出现的频率恰好是大小为 0 和 1 的子集的一半，并给出了均值的精确公式。

Answer 2

撇开数学不谈，有一件事是完全清楚的：当使用二元素分区调用快速排序时，它将发出两次递归调用，其中一个具有零元素分区，另一个具有单元素分区。

所以每统计一个二元分区，必然会统计一个单元分区和一个零元分区。

此外，如果选定的分区元素是 largest/smallest 或第二个 largest/smallest 元素，则在没有双元素父元素的情况下，可以自发地进行一元素和零元素分区当前分区。粗略地说，它们之间的可能性应该差不多，也应该与出现二元分区的可能性一样大。

所以观察到的结果并不出人意料。

当使用快速排序对具有不同键的 N 项数组进行排序时，大小为 0、1 和 2 的子数组的预期数量是多少？

What is the expected number of subarrays of size 0, 1 and 2 when quicksort is used to sort an array of N items with distinct keys?

sorting

algorithm

math

probability

quicksort