c - 实现快速选择算法以找到第 k 个最小的数字

Question

我目前正在开发一个程序，使用快速选择算法查找数组中第 k 个最小的数字。我已经完成它并且它有效，但不是每次都给出正确的结果。

这是我的代码(我没有包含我的partition 或swap 算法，我相当确定它们是正确的):

/*
inputs...
*A: pointer to array
n: size of array
k: the item in question
*/
int ksmallest(int *A, int n, int k){

    int left = 0; 
    int right = n - 1; 
    int next = 1;

    return quickselect(A, left, right, k);
}

int quickselect(int *A, int left, int right, int k){

    //p is position of pivot in the partitioned array
    int p = partition(A, left, right);

    //k equals pivot got lucky
    if (p - 1 == k - 1){
        return A[p];
    }
    //k less than pivot
    else if (k - 1 < p - 1){
        return quickselect(A, left, p - 1, k);
    }
    //k greater than pivot
    else{
        return quickselect(A, p + 1, right, k);
    }
}

一切编译正常。然后我尝试在以下数组上使用该程序:[1,3,8,2,4,9,7]

这些是我的结果:

> kthsm 2
4
> kthsm 1
1
> kthsm 3
2

如您所见，它在第一个最小的项目上工作正常，但在其他项目上失败了。可能是什么问题呢？我猜是因为我的索引被关闭了，但我不太确定。

编辑:根据要求在下面添加了我的分区和交换代码:

int partition(int *A, int left, int right){

    int pivot = A[right], i = left, x;

    for (x = left; x < right - 1; x++){
        if (A[x] <= pivot){
            swap(&A[i], &A[x]);
            i++;
        }
    }

    swap(&A[i], &A[right]);
    return i;
}

//Swaps
void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

Answer 1

在您的分区函数中，循环条件应为 x < right , 不是 x < right - 1 .

此外，在 quickselect 的 if 语句中，您应该切换 p-1 的两种用法。至 p . p已经是一个索引，通过减少 k通过 1 你也把它变成一个索引(而不是一个订单)。不需要减少p又一个。

int partition(int *A, int left, int right){
    int pivot = A[right], i = left, x;
 
    for (x = left; x < right; x++){
        if (A[x] < pivot){
            swap(&A[i], &A[x]);
            i++;
        }
    }
 
    swap(&A[i], &A[right]);
    return i;
}
 
 
int quickselect(int *A, int left, int right, int k){
 
    //p is position of pivot in the partitioned array
    int p = partition(A, left, right);
 
    //k equals pivot got lucky
    if (p == k-1){
        return A[p];
    }
    //k less than pivot
    else if (k - 1 < p){
        return quickselect(A, left, p - 1, k);
    }
    //k greater than pivot
    else{
        return quickselect(A, p + 1, right, k);
    }
}

这是一个工作示例。 http://ideone.com/Bkaglb