通过使用 Select 算法中的主元来重复
我有一个问题，我无法获得该站点的 Select 算法的第 (14,15,16,17) 行的用途。
有此问题的网站位于 此处。
编辑：此外，为“使用数据透视进行分区和重复”部分编写这些行是否正确？ （“m”是我的主元，“i”是该算法的输入）
arrOne<--{a of arr : a<m}
arrTwo<--{a of arr : a>m}
if (i < m ) then
return Select(arrOne,i)
else if (i > m) then
return Select(arrTwo,i-m)
else
return m
I have a problem and I can not get the purpose of lines (14,15,16,17) of this site for Select algorithm.
The site which had this question was located here.
EDITED: Also, is this correct to write these lines for the part "partition and recur by using the pivot"? ("m" is my pivot and "i" is the input of this algorithm)
arrOne<--{a of arr : a<m}
arrTwo<--{a of arr : a>m}
if (i < m ) then
return Select(arrOne,i)
else if (i > m) then
return Select(arrTwo,i-m)
else
return m
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是它选择要递归的分区的地方。
为了便于说明，我们假设您正在查找包含 100 个元素的数组的中位数。第一次分区时，您会得到 60 和 40 个项目的分区。由于您正在查找第 50 个项目，因此您知道它必须位于左侧分区（其中有 60 个项目）。
然后对其进行分区，我们会说，左分区和右分区分别包含 25 个和 35 个项目。这次我们可以看到第 50 个项目必须位于正确的分区中，因此我们递归到该项目。
我们继续这样做，直到到达一个仅包含一项的分区——即我们要查找的项。
This is where it selects the partition in which to recurse.
For the sake of illustration, let's assume you're looking for the median of an array with 100 elements. The first time you partition, you get partitions of, say, 60 and 40 items. Since you're looking for the 50th item, you know it must be in the left partition (which has 60 items).
You then partition that, and get, we'll say, left and right partitions of 25 and 35 items respectively. This time we can see that the 50th item must be in the right partition, so we recurse into that one.
We continue this until we reach a partition that contains only one item -- the one we're looking for.