algorithm - 通过使用 Select 算法中的枢轴重复出现

Question

我有一个问题，我无法获得此站点的第 (14,15,16,17) 行的目的以选择算法。

有这个问题的网站位于here .

已编辑:此外，为“使用枢轴分区和递归”部分编写这些行是否正确？ (“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

Answer 1

这是它选择要递归的分区的地方。

为了便于说明，我们假设您要查找包含 100 个元素的数组的中位数。第一次分区时，您会得到 60 和 40 个项目的分区。由于您要查找第 50 个 项目，您知道它必须在左侧分区(有 60 个项目)中。

然后您对其进行分区，然后分别得到 25 项和 35 项的左分区和右分区。这次我们可以看到第 50^th 项必须在正确的分区中，所以我们递归到那个。

我们继续这样做，直到我们到达一个只包含一个项目的分区——我们正在寻找的那个。