我正在尝试实现快速选择算法。不过，我已经很好地理解了它背后的理论；我发现很难将其转换为运行良好的程序。
以下是我将如何逐步实施它以及我面临问题的地方：
问题：在 A[] = {2,1,3,7,5,4,6} 中找到第四小的元素
k = 4.
指数：0|1|2|3|4|5|6
对应值：2|1|3|7|5|4|6
最初，l = 0并且r = 6
第 1 步）将枢轴作为最左边的元素（在这个问题中，枢轴总是最左边的）-
pivot_index = 0
pivot_value = 2
步骤 2)应用分区算法；将枢轴放在正确的位置（[<p][p][>p]）-
我们得到以下数组：1|2|3|7|5|4|6
在哪里，pivot_index = i-1 = 1
因此，pivot_value = 2
步骤 3 )比较pivot_index-k
k=3, pivot_index = 1; k>pivot_index
因此，我们的第 k 个最小数字位于数组的右侧。
右数组 =i to r并且我们不再为左部分 ( l to i-1) 操心了。
Step 4)我们修改kas k - (pivot_index)=> 4-1 = 2 的值；k = 3.
问题是：不应该k是 2 吗？因为我们在数组的左边有两个值：1|2？我们应该计算k为k - (pivot_index+1)吗？
让我们假设k = 3是正确的。
步骤 5）要处理的“新”数组：3|7|5|4|6具有相应的索引：2|3|4|5|6
现在，pivot_index = 2和pivot_index = 3
步骤 6)在上述数组上应用分区算法-
3|7|5|4|6（数组保持不变，因为枢轴本身是最小值）。
i = 3
pivot_index = i-1 = 2
pivot_value = 3
步骤 7pivot_index )比较k
k=3和pivot_index=2
k > pivot_index
等等....
这种方法正确吗？
这是我的代码不起作用。我使用随机数生成器来选择一个随机枢轴，然后将枢轴与数组中的第一个元素交换。
#include<stdio.h>
#include<stdlib.h>
void print_array(int arr[], int array_length){
int i;
for(i=0; i<array_length; ++i) {
printf("%d ", arr[i]);
}
}
int random_no(min, max){
int diff = max-min;
return (int) (((double)(diff+1)/RAND_MAX) * rand() + min);
}
void swap(int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int get_kth_small(int arr[], int k, int l, int r){
if((r-l) >= 1){
k = k + (l-1);
int pivot_index = random_no(l, r);
int i, j;
swap(&arr[pivot_index], &arr[l]); //Switch the pivot with the first element in the array. Now, the pivit is in arr[l]
i=l+1;
for(j=l+1; j<=r; ++j){
if(arr[j]<arr[l]){
swap(&arr[j], &arr[i]);
++i;
}
}
swap(&arr[l], &arr[i-1]); //Switch the pivot to the correct place; <p, p, >p
printf("value of i-1: %d\n", i-1);
printf("Value of k: %d\n", k);
if(k == (i-1)){
printf("Found: %d\n", arr[i]);
return 0;
}
if(k>(i-1)){
k=k-(i-1);
get_kth_small(arr, k, i, r);
} else {
get_kth_small(arr, k, l, r-1);
}
//get_kth_small(arr, k, i, r);
//get_kth_small(arr, k, l, i-1);
}
}
void main(){
srand(time(NULL));
int arr[] = {2,1,3,7,5,4,6};
int arr_size = sizeof(arr)/sizeof(arr[0]);
int k = 3, l = 0;
int r = arr_size - 1;
//printf("Enter the value of k: ");
//scanf("%d", &k);
get_kth_small(arr, k, l, r);
print_array(arr, arr_size);
printf("\n");
}