c++ - 快速选择算法的最小 kth

Question

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

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]; 是一些编译器支持的非标准声明作为扩展。您不应使用可变长度数组 (VLA)，而应使用 std::vector。

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