0
看過不同的快速排序算法:快速排序 - 爲什麼隨機數據透視?
我沒有看到使用隨機數據透視的好處。與使用最後一個元素相比,遞歸調用quickSort(a [],int p,int r),選擇隨機數是否會隨機提高效率?
THX
看過不同的快速排序算法:快速排序 - 爲什麼隨機數據透視?
我沒有看到使用隨機數據透視的好處。與使用最後一個元素相比,遞歸調用quickSort(a [],int p,int r),選擇隨機數是否會隨機提高效率?
THX
使用隨機擺動的原因是,不讓對手讓你的算法命中最壞情況下的時間。換句話說,隨機旋轉你的算法在所有數據集上的預期性能同樣好。
是的,它的確如此。隨機旋轉減少了碰到最壞情況的機會,尤其是對於完全或幾乎顛倒的數據 – Marcin
請參閱http://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/ – bigbounty
有道理,謝謝 –