我正在尝试实现快速选择算法。虽然，我已经非常了解它背后的理论;我发现很难把它转换成一个运行良好的程序。
这是我如何一步一步地实现它，以及我面临的问题:
问题:求A[] ={2,1,3,7,5,4,6}中的第4个最小元素
k = 4 .
index: 0|1|2|3|4|5|6
对应值:2|1|3|7|5|4|6
初始，l = 0和r = 6
步骤1)将pivot作为最左边的元素(在这个问题中pivot总是最左边的元素)-
pivot_index = 0
pivot_value = 2
step2)应用分区算法;把枢轴放在正确的位置([<p][p][>p])-
1|2|3|7|5|4|6
where, pivot_index = i-1 = 1
，因此pivot_value = 2
step3)比较pivot_index和k -
k=3, pivot_index = 1;k> pivot_index
因此，我们的第k个最小的数位于数组的右侧。
右数组= i to r，我们不再关心左边的部分(l to i-1)了。
step4)将k的值修改为k - (pivot_index) => 4-1 = 2;k = 3 .
这里是问题: k的值不应该是2吗?因为我们在数组的左边有两个值:1|2 ?我们是否应该将k计算为k - (pivot_index+1) ?
假设k = 3是正确的。
step5) "New" array to work: 3|7|5|4|6 and相应的索引:2|3|4|5|6
现在pivot_index = 2和pivot_index = 3
步骤6)对上述数组应用分区算法-
3|7|5|4|6(数组保持不变，因为枢轴本身是最低值)。i = 3
pivot_index = i-1 = 2pivot_value = 3
step7)比较pivot_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: %dn", i-1);
printf("Value of k: %dn", k);
if(k == (i-1)){
printf("Found: %dn", 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");
}
您所描述的是实现快速选择的有效方法。还有许多其他的方法来选择枢轴，它们中的大多数会给出一个更好的预期复杂度，但本质上算法是相同的。
"步骤2:把枢轴放在正确的位置":不要这样做。事实上，你不能把主元放在正确的位置，因为你不知道它是什么。划分规则是把所有比主元小或等于的元素放在大的元素前面。把枢轴放在那里就行了!
快速选择的步骤如下:在N元素中找到第1个K, 1)选择一个枢轴值，2)将所有小于或等于该枢轴的元素移动到其他元素之前，形成两个长度为Nle和Ngt的区域，3)在相关区域上递归(K, Nle)或(K-Nle, Ngt)，直到N=1。
实际上，枢轴可以取任何值，甚至是数组中不存在的值;但分区必须使Nle和Ngt非零