我們可以做快速排序與n logn最壞情況的複雜性？

我想知道我們是否可以修改快速排序算法來產生O（n logn）的最壞情況時間複雜度。雖然這可以通過排列數據來完成，然後假設我們將得到平均情況複雜度而不是最差情況。但這不是一個完整的證明解決方案，因爲我們可以在排列後再次陷入最壞的情況。有什麼其他的方式可以建議嗎？我們可以做快速排序與n logn最壞情況的複雜性？

來源

2012-03-01 pseudocode

一個簡單的方法是在函數的頂部添加兩行：一行進行堆或合併排序，第二行返回。我明白，這可能不是你想到的，但我希望這說明你需要更具體地說明標準快速排序算法允許什麼樣的「修改」......你將要必須非常精確地限制你的侷限性，使之像我建議的禁區一樣。 – Patrick87 2012-03-01 16:28:29

我在想如果我們可以調整快速排序本身。就像對數據透視一些限制一樣。我可以使用合併排序而不是快速排序，而不是使用多種排序。我正在尋找快速排序中的一些調整。 – pseudocode 2012-03-01 16:33:01

See：http://stackoverflow.com/a/70631/44522 – MicSim 2012-03-01 16:36:06

嗯，是的，我們可以把它放到O（nlogn）。我所看到的所有算法都試圖降低這個算法是基於選擇你的支點。如果你可以「智能地」選擇你的支點，它可以被降低。

選項 1. Intro Sort。它現在不再是一個「純粹的」快速排序。它稍後使用合併排序。 2.選擇中位數作爲關鍵點。現在如果以正常方式完成尋找中位數可能需要大量時間，但在Introduction to Algorithms中有提及。

下面是一些直接從馬的嘴Introduction to Algorithms

鴻溝陣列成[N/5]基團與具有5個元素
每組使用插入排序找到每個組的中值，然後挑從此列表中的中位數
然後，您將需要遞歸嘗試並找出從每個組計算的[n/5]箇中位數的中位數。
分區解決此位數

數組有這個算法，我已經隱藏了一些更復雜的東西。如果你願意，你可以在同一本書中閱讀。通常，我不會嘗試使用這種算法。我使用隨機選擇操作來查找關鍵點，並使用該操作。

來源

2012-03-01 16:36:00

謝謝S.P.我想這是我正在尋找。 – pseudocode 2012-03-01 16:40:11

+1提及來自CLRS中位數的中位數 – Adrian 2012-03-01 16:46:59

對於選項1，它不是合併排序，而是排序失控快速排序切換到的堆排序。你想保留quicksort的就地屬性。由於性能原因，合併排序很少在原地實現，儘管它可能是。 – user515430 2012-12-19 17:48:09

那麼「修改」在這裏是一個相當主觀的詞。有很多方法可以增強快速排序，使其在O(n log n)中運行。是否仍然可以稱之爲快速排序是待定的。

其中之一是introsort。 Introsort以快速排序開始，但隨後切換到最差情況複雜度爲O(n log n)的合併排序。插手的目的之一是打擊3中位數殺手名單。

來源

2012-03-01 16:36:38 tskuzzy

謝謝tskuzzy。這將有助於.. – pseudocode 2012-03-01 16:43:42

我們可以做快速排序與n logn最壞情況的複雜性？

回答

相關問題