c - 快速选择不同的枢轴选择算法结果

Question

我编写了以下快速选择随机化算法，它在线性时间内将数组的最小 k 个元素移动到它的开头（技术上最坏的情况 O(n^2)，但概率呈指数下降）：

// This function moves the smallest k elements of the array to
// the beginning of it in time O(n).
void moveKSmallestValuesToTheLeft( double       arr[] ,
                                   unsigned int n     ,
                                   unsigned int k     )
{
    int l = 0, r = n - 1; //Begginning and end indices of the array
    while (0 < k && k < n && n > 10)
    {
        unsigned int partition_index, left_size, pivot;

        //Partition the data around a random pivot
        pivot           = generatePivot(arr, l, n, k); //explained later
        partition_index = partition(arr, l, r, pivot); //standard quick sort partition
        left_size       = partition_index - l + 1;

        if (k < left_size)
        {
            //Continue with left subarray
            r = partition_index - 1;
            n = partition_index - l;
        }
        else
        {
            //Continue with right subarray
            l += left_size;
            n -= left_size;
            k -= left_size;
        }
    }
    if (n <= 10)
        insertionSort(arr + l, n);
}

我测试了 3 种不同的生成数据透视的方法，所有这些方法都是基于选择 5 个随机候选并返回其中一个，每种方法我运行代码 100,000。这些是方法：

1. 选择随机 5 个元素并返回它们的中位数

2. 随机选择 5 个元素，计算 k/n 并检查 5 个元素中哪个最接近它。即，如果k/n <= 1/5返回最小值，则k/n <= 2/5返回第二个最小值，如果k/n <= 3/5返回中位数，依此类推。

3. 与方法 2 完全相同，但我们根据它们的二项式系数为更接近中位数的枢轴赋予更多权重，即我计算了二项式系数n=5-1并得到[1 4 6 4 1]然后我对它们进行归一化并计算它们的总和并得到[0.0625 0.3125, 0.6875 0.9375 1]然后我did: 如果k/n <= 0.0625返回最小值，如果k/n <= 0.3125返回第二个最小值，如果k/n <= 0.6875返回中位数等等...

我的直觉告诉我，方法 2 会执行得最好，因为它总是选择最有可能最接近第 k 个最小元素的枢轴，因此可能会在每次迭代中最大程度地减少 k 或 n，但每次我跑我得到以下结果的代码（基于平均和最坏情况时间的最快方法到最慢方法的排名）：

平均运行时间：

First place (fastest): Method 3
Second place: Method 2
Last place: Method 1

最坏情况运行时间：

First place (fastest): Method 1
Second place: Method 3
Last place: Method 2

我的问题是有没有任何数学方法可以解释这些结果，或者至少给他们一些直觉？因为我的直觉是完全错误的方法 2 并没有优于其他两种方法。

编辑

所以显然问题是我只测试k=n/2了一个边缘情况，所以我得到了这个奇怪的结果。

标签： calgorithmprobabilityquicksort