Median of medians方法在quicksort類型分區算法中非常流行，以產生相當好的支點，從而使其統一劃分數組。它的邏輯在維基百科中給出如下：Medians算法中值的說明
所選樞軸既小於也大於中位數列表中元素的一半，大約爲n/10個元素（1/2 *（n/5） ））每半年。這些元素中的每一個都是5的中位數，使得它在塊之外少於2個其他元素和多於2個其他元素。因此，該數據塊在數據塊外小於3（n/10）個元素，並且大於該數據塊外部另外3個（n/10）個元素。因此，所選擇的中位數在30％/ 70％和70％/ 30％之間分解，這確保了算法的最壞情況線性行爲。
有人可以爲我解釋清楚一點。我發現很難理解邏輯。
認爲以下組數字：
5 2 6 3 1
這些數字的中位數是3。現在，如果您的號碼是n，如果是n > 3，那麼它至少大於上述數字的一半。如果是n < 3，那麼它至少小於上述數字的一半。
這就是這個想法。也就是說，對於每組5個數字，你得到他們的中位數。現在你有n/5號碼。這很明顯。
現在，如果你得到這些數字的中位數（稱之爲m），它大於它們的一半並小於另一半（根據中位數的定義）。換句話說，m大於n/10數字（它們本身是小5元素組的中值）並且大於另一個n/10數字（它們也是小5元素組的中值）。
在上面的例子中，我們看到的是，如果中位數是k，你有m > k，然後m也是其它大於2點的數字（即是他們自己小於k）。這意味着對於其中m大於其中間的那些較小的5個元素組中的每一個，m比兩個其他數字更大。這使得至少3個數字（2個數字+中位數本身）在每個n/10小5個元素組中，小於m。因此，m至少大於3n/10數字。
類似邏輯的元素數量m大於。的 - -
位數的說明中位數算法找出n的第k大的整數，也可以在這裏找到：http://cs.indstate.edu/~spitla/presentation.pdf
又一個問題，請問這種方法保證，這個數字將是中位數？中位數是將陣列分成上半部分和下半部分的數字。那麼30-30-70這個數字意味着什麼？ – SexyBeast
那麼，中位數在中間，但是'm'（在上面的文本中）並不是所有數字的中位數。這個數字的中位數只有1/5（這本身就是5個元素組的中位數）。嘗試閱讀最後一段，更多關注。最後，在結論中，「m」大於數字的至少3n/10，那麼轉換爲「m」的數字至少大於數字的30％。所以最後，「m」大於至少30％，小於至少30％。剩下40％我們不確定。 – Shahbaz
那麼它是如何得到平均50-50分區的呢？ 50-50分區是由正常的中位數給出的，對吧？ – SexyBeast