algorithm - 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];
    }
}

我需要一些帮助来分解成伪代码，虽然我没有得到分区函数代码，但我想了解在提供快速选择函数的情况下它会做什么。

我知道快速排序是如何工作的，只是不知道快速选择。我刚刚提供的代码是我们获得的有关如何格式化快速选择的示例。

编辑:更正后的代码是

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
    }
}

Answer 1

quick select 中最重要的部分是分区。所以让我先解释一下。

快速选择中的分区选择一个 pivot (随机或第一个/最后一个元素)。然后它以所有小于 pivot 的元素的方式重新排列列表。位于枢轴的左侧，其他位于右侧。然后返回 pivot 的索引元素。

现在我们正在寻找第 k 个最小的元素。分区后的情况是:

1. k == pivot .那么你已经找到了第 k 个最小的。这是因为分区的工作方式。正好有 k - 1小于 kth 的元素元素。
2. k < pivot .那么第k小的在pivot的左边.
3. k > pivot .然后第 k 个最小的在 pivot 的右侧。要找到它，您实际上必须找到 k-pivot右边最小的数字。