arrays - 使用从 1 开始的数组索引转换算法

Question

我有一个递归算法的伪代码，该算法在数组中找到第 k 个最大的数字。伪代码使用从索引 1 开始的数组，但是当我实际编写代码时，我需要数组从索引 0 开始。我不知道如何调整算法来做到这一点。

Select-kth-Algorithm4(A: array [1…n] of n distinct integers; left, right, k: integers between 1 and n)
pivotIndex = a randomly generated integer such that left≤pivotIndex≤right
pivotNewIndex = partition(A, left, right, pivotIndex)
if pivotNewIndex−left≥k then
    return Select-kth-Algorithm4(A, left, pivotNewIndex−1, k)
else if pivotNewIndex−left=k−1 then
    return A[pivotNewIndex]
else
    return Select-kth-Algorithm4(A, pivotNewIndex+1, right, k−pivotNewIndex+left−1)
//(Initial call to this algorithm should be Select-kth-Algorithm4(A,1, n, 5) for any particular value of n.}

partition(A, left, right, pivotIndex)
pivotValue = A[pivotIndex]
swap A[pivotIndex] and A[right]
storeIndex = left
for i = left to (right−1)
if A[i] > pivotValue then
    swap A[storeIndex] and A[i]
    storeIndex = storeIndex + 1
swap A[right] and A[storeIndex] 
return storeIndex

我意识到不需要对算法进行任何更改，只需初始调用即可。但是，当我这样做时，它并没有给我正确的值。如果这是问题所在，这是我的实际代码:

void Algorithm4(int *A, int left, int right, int k) {
int pivotIndex = rand() % right + left;
int pivotNewIndex = partition(A, left, right, pivotIndex);
if(pivotNewIndex - left>= k) {
    Algorithm4(A, left, pivotNewIndex-1, k);    
}
else if(pivotNewIndex-left == k-1){
    cout<< A[pivotNewIndex];
}
else {
    Algorithm4(A, pivotNewIndex+1, right, k-pivotNewIndex+left-1);
}
}
int partition(int *A, int left, int right, int pivotIndex) {
int pivotValue = A[pivotIndex];
int temp = A[pivotIndex];
A[pivotIndex] =  A[right];
A[right] = temp;
int storeIndex = left;
for(int i = left; i < right; i++) {
    if(A[i] > pivotValue) {
        int temp = A[storeIndex];
        A[storeIndex] = A[i];
        A[i] = temp;
        storeIndex= storeIndex + 1;
    }
}
temp = A[right];
A[right] = A[storeIndex];
A[storeIndex] = temp;
return storeIndex;
}

Answer 1

您无需更改任何内容。不同之处在于对该函数的根调用，在这里您使用 A, 0, n-1 而不是 A, 1, n 调用它。

原因是绝对的第一个或最后一个元素仅在根调用中使用——在其他任何地方，变量都用于位置。