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

我需要一点帮助来分解成伪代码，虽然我还没有得到分区函数代码，但我想知道它会做什么，因为它提供了快速选择函数。

我知道quicksort是如何工作的，只是不知道quickselect。我刚刚提供的代码是一个关于如何格式化快速选择的示例。

编辑:更正后的代码为

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

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

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

现在我们在这里找到第k个最小元素。分区后的情况是：

1. k == pivot.那么你已经找到了最小的第k个。这是因为分区的工作方式。确实存在比element.
2. k < pivot. k - 1更小的kth元素那么第k个最小的就在pivot.
3. k > pivot.的左边那么最小的第k个就在轴线的右边。要找到它，你必须在右边找到k-pivot最小的数字。

Answer 2

顺便说一句，你的代码有一些bug..

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 3

Partition非常简单:它重新排列元素，使那些小于所选枢轴的元素在数组中的索引低于枢轴，而大于枢轴的元素在数组中的索引较高。

我在previous answer中谈到了剩下的部分。