關於快速排序殺手

Question

有些人可能已經在這個可愛的文章跌跌撞撞 - http://igoro.com/archive/quicksort-killer/ \

什麼是真正有趣的是他如何修復快速排序爲O（N日誌N）對定義的對手來執行。

快速排序可能會選擇中間元素作爲每個步驟的支點，因此總是會將輸入序列完美分割爲兩半。中位數可以在O（N）運行時間中確定性地找到，因此總運行時間總是O（N log N）。

我的問題是線性時間中值尋找算法會不會使用相同的比較函數並在O（N^2）而不是O（N）中執行？

編輯：

準確地說：我質疑它採用類似於快速排序，它會使用相同的比較函數作爲一個的策略基於分區的中值選擇算法的複雜性快速排序使用。這個對手在O（N）中如何運作？

Answer 1

不會線性時間中位數調查 算法最終使用相同 比較功能的O型執行（N^2） 代替O（N）？

否，通過添加O（N）函數來找到中間的複雜性變得

O((N+N) log N) == O(2N log N) == O(N log N) 

但是，作爲文章指出，增加的常數使得它不具吸引力。

標準技術被稱爲3的中位數，全中位搜索不會真正改善。

如果最壞的情況非常嚴重，就不要使用Quicksort。 Shellsort有更好的上限。