快速排序 - 爲什麼隨機數據透視？

Question

看過不同的快速排序算法：

我沒有看到使用隨機數據透視的好處。與使用最後一個元素相比，遞歸調用quickSort（a []，int p，int r），選擇隨機數是否會隨機提高效率？

THX

Answer 1

使用隨機擺動的原因是，不讓對手讓你的算法命中最壞情況下的時間。換句話說，隨機旋轉你的算法在所有數據集上的預期性能同樣好。