在选择算法中使用枢轴重复出现

Question

我遇到了问题，无法获得此网站的Select（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 ^第项必须位于正确的分区中，因此我们会重新进入该分区。

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