快速選擇算法 - 簡單解釋

Question

我在HERE之前詢問過這個，但是我希望快速選擇（基於快速排序）的解釋進一步簡化。我問的前一個問題包括一些示例代碼（所以你知道我在說什麼）。

我想知道是否有人在任何地方的任何地方總結了快速選擇作爲遊戲的規則和指導方針，在這裏可以通過遵循易於理解的規則來學習算法是如何工作的，可以應用於讓我們說一副牌或紙上的數字。

我認爲快速選擇算法的簡單解釋對於我理解它的工作原理至關重要，因爲我仍然收到的教程和解釋很難理解和可視化。即使YouTube上將視頻轉換成舞曲的視頻也沒有太大幫助。

在此先感謝堆棧，到目前爲止您一直是一個很好的幫助。

Answer 1

你走進一個包含200名兒童的健身房。這是9月8日，所以你有一個渴望找到第98個最矮小的孩子。你知道你可以將它們從最短到最高排成一行，但那會持續下去。 「我知道」，你認爲，「我可以使用QUICKSELECT！」

你走出人羣，閉上你的眼睛，伸出你的手指，並旋轉三次。當你睜開眼睛時，你直接指向一個孩子Peter Pivot。你說：「快，每個比彼得都短的人，站在這裏，每個人都比彼得高，站在那裏，如果你和彼得一樣高，你可以進入任何一組。」

孩子們洗牌，很快他們站在兩個小組。你計算並找到較短組中的120名兒童，以及較高組中的79名兒童。你知道第98個最矮的孩子必須在較矮的小組中，所以你告訴彼得和79個更高的孩子坐在看臺上。

你再閉上你的眼睛，伸出你的手指，並旋轉三次。當你睜開你的眼睛時，你直接指向彼得的姐姐，寶拉皮奧特。你說：「快！那些還站着的人，如果你比寶拉短，站在這裏，如果你比寶拉高，站在那裏，如果你是同一個高度，你可以進入任一組。「

孩子們洗牌，很快他們站在兩個小組。你計算並找到較短組中的59名兒童，以及較高組中的60名兒童。你知道第98個最矮的孩子必須在更高的組中，所以你告訴寶拉和59個矮小的孩子坐在看臺上。

你再閉上你的眼睛，伸出你的手指，並旋轉三次。當你睜開眼睛時，你直接指向寶拉的表弟Prudence Pivot。你說：「快！那些還在站立的人，如果你比普魯登斯短，站在這裏，如果你比普魯登斯高，站在那裏，如果你是同一高度，你可以進入任一組。「

孩子們洗牌，很快他們站在兩個小組。你計算並找到較短組中的37名兒童，以及較高組中的22名兒童。你知道寶拉和另外59個矮小的孩子正坐在看臺上。除了37個較矮的孩子仍然站立，你知道共有97個孩子比Prudence短。所以，普律當絲是第98個最矮小的孩子！

Quickselect FTW！