c++ - 无法理解快速选择算法

Question

我在理解快速选择算法时遇到问题。我知道它是基于快速排序算法(我很熟悉)并且它给你所需的结果可能留下数组的一部分未排序。现在这是我遇到困难的地方。问题是从数组中找到第二小的元素:

int a[4] = {1,3,5,2} ;

现在假设我们根据 this 随机选择 pivot发布我们有以下条件:

• k == pivot .那么你已经找到了第 k 个最小的。这是因为分区的工作方式。恰好有 k - 1 个元素小于第 k 个元素。

• k < pivot .那么第k小的在pivot的左边。

• k > pivot .然后第 k 个最小的在 pivot 的右侧。要找到它，您实际上必须在右侧找到 k-pivot 最小数字。

如果有人能解释一下如何k==pivot，我将不胜感激。意味着我们找到了第 k 个(在我的例子中是第二小的元素)。另外如果它是k < pivot我们是否对枢轴的左侧重复该过程？

Answer 1

如果 k = pivot，你将在 pivot 的左侧有 k-1 个项目。由于分区，这些中的每一个都小于枢轴项。此外，由于分区，右边的每个项目都大于主项。因此，枢轴项必须是第 k 个最大的。有道理吗？