实现快速选择

Question

我正在尝试实现快速选择算法。不过，我已经很好地理解了它背后的理论；我发现很难把它转换成一个运行良好的程序。

下面是我如何一步一步地实现它，以及我面临的问题所在：

问题：在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)应用分区algo；将枢轴放置在正确的位置([<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)了。

步骤4)我们将k的值修改为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)在上面的数组上应用分区algo的-

3|7|5|4|6 (数组保持不变，因为枢轴本身是最低值)。i = 3

pivot_index = i-1 = 2 pivot_value = 3

步骤7)比较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: %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");

}

Answer 1

您所描述的是实现快速选择的有效方法。选择支点的方法有很多种，其中大多数都会给出更好的预期复杂度，但从本质上说，算法是一样的。

Answer 2

"Step 2：将支点放在正确的位置“：不要这样做。事实上，你不能把枢轴放在正确的位置，因为你不知道它是什么。分区规则是将比枢轴更小或等于的所有元素放在较大的元素之前。把枢轴放在那里就行了！

快速选择的方法如下: 1)选择一个枢轴值，2)在其它元素之前移动所有小于或等于枢轴的元素，形成长度为K和Ngt的两个区域，3)在相关区域上进行(K，Nle)或(K-Nle，Ngt)，直到N=1。

实际上，任何值都可以用于支点，即使是数组中不存在的值；但是分区必须使Nle和Ngt为非零。