algorithm - 了解选择算法

Question

我无法理解分区集 S 中元素的数量与第 k 个最小数字的关系。假设我有这个伪代码:

 Select (k,S)
  if |S|=1 then return a in S
  Choose random a in S
  Let S1,S2,S3 be sets of elements in S (<,=,> to a)
  If |S1|>=k then return Select(k,S1)
  Else if |S1| + |S2| >= k then return a
  Else return Select(k-|S1|-|S2|, S3)

据我所知，为了找到第 k 个最小的元素，我选择了一个主元并围绕该主元对数字进行排序，这样所有较小的数字都在主元的左侧，所有较大的数字都在主元的右侧。然后，如果我想找到第 k 个最小的数字，我将它与枢轴的位置进行比较，如果枢轴的位置大于 k，我查看枢轴的左侧，如果枢轴的位置小于 k , 我向右看并从那里递归。

但是，在上面的伪代码中，我看不到上面与 pivot 和 k 的比较发生在哪里。我的意思是，它不应该与 >= k 而不是 |S1| 进行比较吗？ >= k，因为 a 是枢轴？

集合中元素的数量如何影响与 k 的比较？

Answer 1

S1是小于a的数集。 S2 是数字的集合 == a。而S3是数>=a的集合。这已经包含很多比较。

现在如果|S1| >= k，则小于a的数集合超过k个元素。因此第k个最小的数已经包含在S1中。

如果不是这种情况，则它不包含在 S1 中，因此它必须在 S2 或 S3 中。

如果|S1|+|S2| >= k，那么当然是在S1或者S2中。因为它不在 S1 中，所以它必须在 S2 中。由于 S2 = {a} 第 k 个最小的数是 a。

如果这些都不是，那么它一定在 S3 中。因此可以将搜索限制在 S3。由于 S1 和 S2 中包含的数字在 S3 中丢失，并且由于它们小于 S3 中的所有数字，这意味着我们必须搜索 k-|S1|-|S2|。 S3 中最小的数字。