快速排序，給出3個值，我怎樣才能達到9個操作？

Question

嗯，我想用快速排序給定3值，無所謂什麼值，怎麼才能得到最差的情況，那就是9的操作？

任何人都可以繪製樹並顯示它如何顯示nlogn和n^2操作？我試圖在網上找到，但我仍然沒有設法正確地繪製一個來顯示。

Answer 1

快速排序的最壞情況複雜度取決於所選的樞軸。如果選擇的樞軸是最左邊或最右邊的元素。那麼在下列情況下會出現最差情況複雜度：

1）數組已按照相同的順序排序。

2）數組已按相反順序排序。

3）所有元素相同（情況1和2的特例）。

由於這些情況非常頻繁發生，因此主題是隨機選擇的。通過隨機選擇樞軸，減少最壞情況的機會。

快速排序算法的分析在khan academy的this blogpost中進行了解釋。