在選擇算法中使用樞軸重複出現

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 ^第項必須位於正確的分區中，因此我們會重新進入該分區。

我們繼續這樣做，直到我們到達只包含一個項目的分區 - 我們正在尋找的項目。