快速排序平均和最差情況下的複雜性混淆？

Question

對於快速排序的平均和最差情況，我有點困惑。我知道以下內容：

1. 快速排序爲O（nlogn）的平均情況複雜選擇了中間的支點時。
2. 快速排序最差情況下的複雜性是選擇Minimum或Maximum元素作爲關鍵點。
3. 上述兩種情況都會爲幾乎排序的元素列表和未排序的數據列表提供相同的複雜度。

是以上三點是真的嗎？如果沒有，我想知道如何快速排序行爲幾乎排序列表和未排序的列表？

Answer 1

你說得對（1）和（2）。如果樞軸將數據分成大約一半（理想情況下樞軸爲中位數），則快速排序表現良好，並且當分區不均勻時排列不佳。

輸入數據是否被排序的重要性取決於如何選擇關鍵點。

樞紐的最簡單的可能的選擇是把你劃分部分的第一要素。如果你這樣做，並且數據被排序或者反向排序，那麼你得到最不平均的可能的除法，因爲你選擇的數據是該範圍中最小或最大的值。

下最簡單的，我想，是沿輸入中途取作爲樞軸的元素。那麼如果數據已經被排序，你會得到最好的分割。歡呼！但是這個中間元素仍然可能是這個範圍內的最小值（或者最大值），在這種情況下，你會得到一個不好的分割。噓！使用各種技術可以做出更好的樞軸選擇：「三位數中位數」，「僞中位數九」或隨機的（在這種情況下，惡意用戶不能構造出最壞情況，案件發送給你，並且一個壞案件的可能性對於顯着大小的投入是如此之小以至於在實踐中你不能合理照顧）。

你可以甚至使用中位數的位數quickselect找到線性時間中位數和使用它作爲樞軸，從而完全避免爲O（n^2）最壞情況。實際上，有一個更好的方法可以避免O（n^2）最差的情況：Introsort。

當人們談論「快速排序」，他們並不一定意味着轉動的任何特定的選擇，所以你不能說什麼快速排序將不指定一個選擇這樣做。 Hoare對Quicksort的第一個描述使用第一個元素作爲關鍵點，我認爲，所以它對接近排序或接近反向排序的數據的速度很慢。