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

Question

我正在阅读Robert Sedgewick的书算法第4版，他有以下练习问题:当快速排序用于排序N个具有不同键的项的数组时，大小为0,1和2的子数组的期望数量是多少?

然后他说，如果你喜欢数学，就做数学，如果不喜欢，就做实验，我做过实验，似乎大小为0和1的数组出现的次数完全相同大小为2的数组出现的次数只有它们的一半。

所讨论的快速排序版本是具有2路分区的版本。

我理解当分区项是子数组中最小/最大的项时，我们得到大小为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到第一个最小/最大的项时，大小为1的数组出现，当分区项是第3到第一个最小/最大的项时，大小为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);
    }
}

有证据表明，快速排序平均使用2nlgn ~ 1.39NlgN来排序长度为N且具有不同键的数组

我想我们可以把1.39NlgN看作是我们进行N次比较~lgN次，所以平均我们将数组分成两半，因此在某些时候我们将剩下成对进行比较，因为只有对进行比较，例如:<1,2>，<3,4>，<5,6>，等等…，我们将得到大小为0和1的子数组，这只能证明大小为0和1的子数组更频繁，但我仍然不明白为什么大小为2的子数组几乎是频率的一半。

Answer 1

快速排序将在位置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

不考虑数学问题，有一件事是完全清楚的:当使用双元素分区调用快速排序时，它将发出两个递归调用，其中一个具有零元素分区，另一个具有单元素分区。

所以对于每一个被计数的双元素分区，肯定会有一个单元素分区和一个零元素分区。

此外，当选择的分区元素是当前分区中最大/最小或第二大/最小的元素时，可以自发地发生单元素和零元素分区，而不需要双元素父元素。粗略地说，它们之间的可能性应该是一样的，也应该和出现双元素分区的可能性一样大。

所以观察到的结果并不意外。