如何证明均匀分区是快速排序算法的最佳案例？

Question

为什么我们说quicksort的最佳情况是“每次我们执行分区时，我们将列表分成两个几乎相等的部分”？如何证明这正是所谓的“最佳案例”？

Answer 1

采取长度2^N（为简单起见）。

比较每个阶段（N到N/2+N/2）的完美分区情况的操作次数以及将段长度N分成1和N-1的情况

Answer 2

我创建了一个程序而不是尝试进行分析。我比较了1 / 2,1 / 2（50％50％）分裂与1 / 4,3 / 4（25％75％）分割的情况，当n变大时，这似乎接近22％的操作。代码设置为1 / 4,3 / 4分割：对于1 / 2,1 / 2分割，将线从左=（n + 3）/ 4更改为左=（n + 1）/ 2。左边的舍入点是确保left> = 1，以避免无限递归。

#include <stdio.h>
typedef unsigned long long uint64_t;
static uint64_t sum;

void qsa(uint64_t n)
{
uint64_t left, right;
    if(n < 2)
        return;
    sum += n;
    left = (n+3)/4;         /* or left = (n+1)/2  */
    right = n - left;
    qsa(left);
    qsa(right);
}

int main()
{
    qsa(1024*1024);
    printf("%llu\n", sum);
    return(0);
}

结果

n = 1024*1024
20971520     1/2 1/2   n log2(n)
25331387     1/4 3/4   ~1.208 n log2(n)

n = 16*1024*1024

402653184    1/2 1/2   n log2(n)
488049677    1/4 3/4   ~1.212 n log2(n)

n = 1024*1024*1024

32212254720  1/2 1/2   n log2(n)
39180282211  1/4 3/4   ~1.216 n log2(n)

n = 16*1024*1024*1024

584115552256 1/2 1/2   n log2(n)
711608157825 1/4 3/4   ~1.218 n log2(n)