QuickSelect算法理解

Question

我一直在研究讨论快速排序和快速选择的各种教程和文章,但是我对它们的理解仍然不稳定.

鉴于这种代码结构,我需要能够掌握并解释quickselect的工作原理.

// return the kth smallest item
int quickSelect(int items[], int first, int last, int k) {
    int pivot = partition(items, first, last);
    if (k < pivot-first) {
        return quickSelect(items, first, pivot, k);
    } else if (k > pivot) {
        return quickSelect(items, pivot+1, last, k-pivot);
    } else {
        return items[k];
    }
}

我需要一些帮助来分解伪代码,虽然我没有提供分区功能代码,但我想了解在提供quickselect功能的情况下它会做什么.

我知道quicksort是如何工作的,只是没有快速选择.我刚才提供的代码就是如何格式化快速选择的一个例子.

编辑:更正后的代码是

int quickSelect(int items[], int first, int last, int k) 
{
    int pivot = partition(items, first, last);
    if (k < pivot-first+1) 
    { //boundary was wrong
        return quickSelect(items, first, pivot, k);
    } 
    else if (k > pivot-first+1) 
    {//boundary was wrong
        return quickSelect(items, pivot+1, last, k-pivot);
    }
    else 
    {
        return items[pivot];//index was wrong
    }
}

Courtesty:@Haitao

Answer 1

快速选择的重要部分是分区.所以我先解释一下.

快速选择中的分区选择a pivot(随机或第一个/最后一个元素).然后它重新排列列表,使得所有元素都小于pivot枢轴左侧,而其他元素则位于右侧.然后它返回pivot元素的索引.

现在我们在这里找到第k个最小的元素.分区案例后:

1. k == pivot.然后你已经找到了最小的第k个.这是因为分区的工作方式.确切的k - 1元素小于kth元素.
2. k < pivot.然后第k个最小的位于左侧pivot.
3. k > pivot.然后第k个最小的位于枢轴的右侧.要找到它,你实际上必须k-pivot在右边找到最小的数字.

Answer 2

顺便说一句，您的代码有一些错误。

int quickSelect(int items[], int first, int last, int k) {
    int pivot = partition(items, first, last);
    if (k < pivot-first+1) { //boundary was wrong
        return quickSelect(items, first, pivot, k);
    } else if (k > pivot-first+1) {//boundary was wrong
        return quickSelect(items, pivot+1, last, k-pivot);
    } else {
        return items[pivot];//index was wrong
    }
}