快速排序最差情況

Question

我正在研究下面需要的程序以更好地理解它。

Quicksort最糟糕的情況下運行時間是什麼，什麼可能會導致這種更糟的情況下性能？我們如何修改quicksort程序來緩解這個問題？

我知道它有最壞的情況O(n^2)，我知道它發生時，樞軸唯一最小值或最大元素。我的問題是如何修改程序來緩解這個問題。

一個好的算法會很好。

Answer 1

這已經有一段時間了，但我認爲快速排序最糟糕的情況是數據已經排序。快速檢查數據是否已經排序可以幫助緩解這個問題。

Answer 2

一個簡單的修改就是隨機選擇pivot。這給出了好的結果with high probability。

Answer 3

快速排序的性能取決於您的數據透視選擇算法。最樸素的樞軸選擇算法是隻選擇第一個元素作爲樞軸。很容易看出，如果您的數據已經排序，則會導致最差情況下的行爲（第一個元素始終爲最小值）。

有兩種常見的算法來解決這個問題：隨機選擇一個數據透視表，或者選擇三位數的中位數。隨機是顯而易見的，所以我不會詳談。三個中間值包括選擇三個元素（通常是第一個，中間和最後一個）並選擇這三個元素的中值作爲關鍵點。由於隨機數發生器通常是僞隨機的（因此是確定性的）並且三種算法的非隨機中值是確定性的，所以可以構造導致最壞情況行爲的數據，但是它很少出現正常使用。

您還需要考慮性能影響。隨機數生成器的運行時間會影響快速排序的運行時間。中位數爲三，你正在增加比較的數量。

Answer 4

最壞性能條件：

當選擇每次樞軸是 '最大' 或 '最小' 和此模式重複

所以對於1 3 5 4 2

如果樞轉按順序選1,2,3,4,5或5,4,3,2,1

那麼最壞的情況下運行時間是O（n * n）

如何避免最壞的情況下：

（1）除以陣列分爲五個sets.So如果1..100集合是（1..20）（21..40）（ 41..60）（61..80）（81 ..100）

（2）選擇第一五行的中位數在每個設定成（3）（23）（43）（63）（83）

（3）現在選擇之中的中值他們作爲支點在這裏它的（43）

Answer 5

最差的情況下運行時間取決於快速排序內的分區方法。這有兩個方面：

• 選擇樞軸
• 如何分區圍繞樞

良好的戰略選擇樞軸在以前的帖子已經被outlinied（中位數的中位數，或三個位或隨機化）。但即使樞軸是明智的選擇，在極端情況下，如果一個數組的所有相等的元素會導致最壞的情況下運行時，如果只有兩個分區建成，因爲一個將攜帶相等的元素，這是所有元素：

• 這將導致partion被稱爲n次，每次它取N/2的平均導致O（N²）
• 這是不好的，因爲它不是一個理論上的最壞的情況，但很常見的一個
• 注意，它不是通過檢測空分區解決，因爲樞軸可能具有最高或最低的元素值（例如中位數爲5分，以及最高的元素值，但仍可能幾個錯放<個5值）

解決此問題的一種方法是分割成三個分區，低級（元件<樞軸），相等（元素=樞軸）和上分區。 「=樞軸元素」處於最終位置。如果不是空的話，下部分區和上部分區仍然需要排序。

與隨機總之，中位數或某種組合的中間選擇一個支點最壞的情況是相當罕見的，但不是不可能，這讓與上限O（N²）的最壞情況下的算法。