快速选择算法的最小kth

Question

我一直在开发一个程序，该程序旨在测试快速选择算法在不同组大小设置下的性能。找到中心，算法会将所有元素分成5个一组。它应该找到每组的中位数，并使用所有组的中位数的中位数作为轴心。我对最小的第k部分有个问题。我得到的错误是，n不是一个常量变量，所以它不能分配数组，并且它导致median的大小未知。我应该怎么做才能纠正这个问题呢？

int smallestKth(int ray[], int l, int r, int k)

 {
if (k > 0 && k <= r - l + 1)

{

    int n = r-l+1; 
    int i, median[(n+4)/5]; 
    for (i=0; i<n/5; i++)
        median[i] = medianFind(ray+l+i*5, 5);
    if (i*5 < n) 

    {
        median[i] = medianFind(ray+l+i*5, n%5);
        i++;
    }   


    int medOfMed = (i == 1)? median[i-1]:
        smallestKth(median, 0, i-1, i/2);


    int pivotPosition = part(ray, l, r, medOfMed);
    if (pivotPosition-l == k-1)
        return ray[pivotPosition];

    if (pivotPosition-l > k-1) 
        return smallestKth(ray, l, pivotPosition-1, k);      
    return smallestKth(ray, pivotPosition+1, r, k-pivotPosition+l-1);

}
return INT_MAX;

}

Answer 1

int median[(n+4)/5];是一些编译器作为扩展支持的非标准声明。应该使用std::vector，而不是使用可变长度数组(VLA)。

std::vector median((n+4)/5);

Answer 2

你不需要创建一个新的数组来保存中值。只需使用原始数组的五分之一。

要做到这一点，一种方法是stride数组；将数组表示为起始指针、元素数和步长，步长是两个连续元素之间的距离。例如，一旦你在数组start，n，stride中正确的位置放置了每组5的中位数，你就可以在数组start+2，(n+2)/5，5*stride上递归。

Answer 3

这是通过为中间数组创建指针来解决的。

int n = right-left+1;
    int *median = new int[(n+4)/5];