当快速排序只有两个不同键的 N 个项目数组时的最大函数调用堆栈大小是多少

Question

实际上，这是Coursera普林斯顿Sedgewick算法的一个问题。我想是~log2（N）。但我做了一个实验，当0.5N1s和0.5N0s互换时，它是~2ln（N），当N个不同的键时，它就是~2log2（N）。为什么？

这是Robert Sedgewick的《算法》第4版中的代码：

public class Quick 
{ 
    public static void sort(Comparable[] a)
    { 
        StdRandom.shuffle(a);  // Eliminate dependence on input.
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int j = partition(a, lo, hi); // Partition (see page 291).
        sort(a, lo, j-1);  // Sort left part a[lo .. j-1].
        sort(a, j+1, hi);  // Sort right part a[j+1 .. hi].
    }
    private static int partition(Comparable[] a, int lo, int hi) 
    { // Partition into a[lo..i-1], a[i], a[i+1..hi]. 
        int i = lo, j = hi+1;  // left and right scan indices
        Comparable v = a[lo];  // partitioning item
        while (true)
        {  // Scan right, scan left, check for scan complete, and exchange. 
            while (less(a[++i], v)) if (i == hi) break;
            while (less(v, a[--j])) if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);  // Put v = a[j] into position 
        return j;  // with a[lo..j-1] <= a[j] <= a[j+1..hi]. 
    }
}

Answer 1

如果你用大O符号分析它，它仍然是O（N^2），但如果你试图找到它的平均复杂度，它可能是~2log2（N）和AFAIK，那么找到算法的平均复杂程度有点困难。