快速排序中位數選擇

由於我們可以選擇3元素分區的中位數來實現快速排序。同樣，我們可以選擇5,7或11個元素的中位數來實現快速排序嗎？如果是這樣，那麼怎麼樣？快速排序中位數選擇

2011-04-09 james

嗯..基本上你只是選擇所述陣列的5,7，或11個元件被劃分並使用他們的位數作爲樞軸。這與3的中位數並沒有太大的區別。主要區別可能在於，對於小於5,7或11個元素的數組，您應該進行插入排序。再次，它會加快你的快速排序，幾乎不管你有多少元素用於查找你的數據透視表，對小於10-15個元素的數組進行插入排序。 – 2011-04-09 18:08:05

你應該看看Median of Medians algorithm。這是一種線性時間算法，具有以下重複...

T(n) ≤ T(n/5) + T(7n/10) + O(n)

...這是O（n）。該算法的細節...

將列表分爲5種元素各
的N/5個子找到每個列表的中位數，蠻力。將有n/5這些
讓m_1，...，m_n/5是這些中位數。
遞歸地找到這些中位數。這將是1個元素，這個關鍵點！

...和一些僞代碼...

MedianOfMedians (A[1],...,A[n]) 
begin 
    for i=1 to n/5 do { 
     let m_i be the median of A[5i − 4], A[5i − 3],..., A[5i]; 
    } 
    pivot = Select(m1,...,m_n/5, n/10); // the pivot 
    return pivot 
end

參考

我希望這有助於。
赫里斯託斯

來源

2011-04-09 16:01:59 Hristo

根據你的代碼，我們可以找到最接近整個數組中值的數據點，然後將整個數組分成2部分？如果下半部分的數字少於上半部分，那麼做什麼？ – Alcott 2011-10-11 02:59:20

快速排序中位數選擇

回答

相關問題