當我選擇像中位數或模式這樣的數據透視表時，快速排序不工作速度更快

Question

我在測試Quicksort實施時出現問題。我被告知，當我們選擇一個數字（如中位數）作爲關鍵點時，算法會更好，但是，我的結果並不符合我的預期。通常情況下，當我選擇第一個或最後一個元素作爲數據透視表時，最好的情況就是這樣，並且它們都是隨機數，就像數組中的所有其他元素一樣。我正在進行大量測試（超過5000次）並檢查平均時間（沒有時間查找模式或中位數）。謝謝。

Answer 1

計算數組的中位數或模式是一項昂貴的操作（特別是選擇中位數），所以即使您將獲得良好的支持，尋找這些支點的額外開銷可能會消耗大部分效率提升。

隨機快速排序（每次選擇隨機數據）最終會成爲一個更好的選擇。最糟糕的情況是幾乎不可能的，並且期望它在時間O（n log n）中運行。生成一個隨機或僞隨機數的方法比找到數組的中值或模式要快得多。

最後，如果你確實選擇了數組的模式，那麼就不能保證你有一個好的支點。事實上，如果你有一個沒有重複數組的數組，這可能會導致病態情況，並且你選擇模式的實現總是選擇最小值或最大值。這將退化爲Θ（n ）時間。

希望這會有所幫助！