c - 使用快速排序变体的第 k 个最小数

Question

我有以下分区方法和 kthsmallest 方法(快速排序的变体)，它们适用于某些情况，但在少数情况下给我值 32767。

void swap(int* a, int* b){

int temp = *b;
*b = *a;
*a = temp;
}

int partition(int* arr, int l, int r){

int pivot = arr[r];
int i = l, j=0;

for(j=l; j<=r-1; j++){
    if(arr[j] <= pivot){
        swap(&arr[i], &arr[j]);
        i++;
    }
}

swap(&arr[i], &arr[j]);
return i;
}

而第k小函数如下:-

int kthsmallest(int* arr, int low, int high, int k){
 /* low = 0 and high = #elements - 1 */
 /* k is in between 1 to high + 1 */

 if (k>0 & k<=high-low+1)     {
    // pos is partitioning index, arr[p] is now  at right place
    int pos = partition(arr, low, high);

    // Separately sort elements before / partition and after partition

    if(pos-low == k-1){
            return arr[pos];
    }
    //if position returned is greater than k, recurse left subarray
    else if(pos-low > k-1){
            return kthsmallest(arr, low, pos-1, k);
    }

    return kthsmallest(arr, pos+1, high, k-(pos+1));

}
}

但是，当我更改 kthsmallest 函数中的最后一次调用时它会起作用，即

更改:return kthsmallest(arr, pos+1, high, k-(pos+1));

到:return kthsmallest(arr, pos+1, high, k-(pos+1)+low);

我想了解为什么我需要将 low 添加到 k-(pos+1)。因为在我看来，当我们在递归进入的右侧有子数组时，大数组中第 k 个最小的数字归结为 k - 最后一个分区元素 -1 即 k-(pos+1)。

Answer 1

您需要 low，因为当您递归地从一个新数组开始时，low 将成为 pos 的引用。所以新的 k 将从 low 到 pos 计算。

也许举个例子会更清楚。

让我们找到这个数组中第 9 个最小的元素:

现在我们进行分区，所以我们得到:

从 pos 到左边，我们得到了数组中最小的元素，这是 3 个最小的元素。现在我们将使用从 pos+1 开始的子数组。我们需要得到第 6 个最小的元素:

我们对这个子数组进行分区:

请记住，我们正在处理一个子数组，试图找到第 6 个最小的元素。在本例中，我们分离了子数组中第 (pos - low + 1) 个最小的元素。所以我们的新 k 将是: 我们做一个新的分区: 现在我们超过了最后一个子数组的第 4 个最小元素，所以我们修剪最后一部分: 我们再次进行分区:

我们得到:

所以我们的号码是 17。

希望对您有所帮助。

PD:正如 David C. Rankin 在评论中所说，您可能应该将 & 更改为 &&。