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

Question

我正在阅读Robert Sedgewick的书Algorithms第4版,他有以下练习题:当使用quicksort对具有不同键的N个项目的数组进行排序时,大小为0,1和2的子数组的预期数量是多少？

然后他说,如果你在数学上有倾向,做数学,如果没有,运行实验,我已经进行了实验,看起来大小为0和1的数组具有完全相同的出现次数和大小为2的数组只有一半是发生的.

有问题的quicksort版本是具有双向分区的版本.

据我所知,当分区项是子数组中最小/最大的分区项时,我们得到大小为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);
    }
}

有一个证据表明平均快速排序使用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，然后我们可以应用C0(n) = (n+1)/n * C0(n-1)n>2的简化递推关系来得到一般结果C0(n)=(n+1)/3。

对于C1，我们有初始条件C1(0)=0，C1(1)=1。和以前一样，我们计算C1(2)get 1，并应用与 for 相同的过程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 大小的子集的一半，并给出了均值的精确公式。