1樓：
@愛麗絲欣 很贊同！補充點：
事實上不止歸併排序、快速排序，還有堆排序也是達到了線性對數級別的複雜度。比較這幾種線性對數級別的演算法時，乙個是要考慮到複雜度前面的常數因子的區別；二是要考慮在實際的運用中，堆排序用的非常少，很大程度就是因為堆排序排序時，資料位置相隔很遠，而快排等則很多時候是和相鄰的元素進行比較，因此快取命中率高很多，這也造成了實際執行時，堆排序速度不理想的原因之一。
另外，快速排序最糟糕的情況達到了平方級別，這無法否認，所以通常情況下，排序前都會將資料打亂，這樣執行時出現平方級別的概率我想比你買彩票中500萬的概率大不了多少。這種概率保證讓我們可以放心的使用快速排序。
2樓：
在《計算機程式設計藝術》卷三里Knuth分析了在乙個典型的計算機中幾種排序演算法的確切的時間複雜度：
快速排序是
歸併排序是
至少在Knuth給定的設定下，快速排序的常數小於歸併排序。當然，實際應用中多數場景下快速排序比歸併排序確實快一些。
3樓：花椰菜君
我記得有個測試結果表明在大量的資料測試集中快排確實快那麼一點。而且通過改變軸值的選擇方式，可以有效地避免最壞情況出現。從這個角度說，叫快排也無可厚非。
4樓：answer
了解不全面，試圖簡單作答：
1. 當初起的就是這名字；
2. 我記得，似乎quicksort用的compare數量和mergesort差不多，但涉及到的元素的交換要少很多，因此一般情況下quicksort確實很快；因此就加深了人對這個名字的印象。
5樓：Coldwings
因為馮老爺子想出merge sort的時候起名就叫merge sort，當時是2023年。
Tony Hoare想出Quicksort（注意拼寫，中間沒有空格）的時候，雖然也是基於遞迴分治的思想，總不能改了馮老爺子想出來的名兒，所以就直接叫quicksort了，當時是2023年……
然後到國內大家按詞素翻譯，就撐了歸併排序&快速排序了。
為什麼快速排序比原生排序快？
甄士隱 首先，阮一峰老師的快排序是存在問題的，具體請看我另乙個回答 阮一峰版快速排序完全是錯的 一文是否存在事實錯誤？真正正確且標準的快排序，可參考我自己實現的一版 go 語言實現 Wang Kai algorithm 至於你的排序比原生 sort 快 4倍，可能的原因有兩個 js 中 sort 排...
多路歸併排序的時候，為什麼要採用敗者樹？
田冬冬 首先勝者樹敗者樹都叫Tournament Tree，所謂多路歸併場景是指不斷poll offer各多路資料的過程。那麼維護操作 不是建立 比較如下 堆是頂點資料彈出後，最後的葉子節點代替其位置，然後做比較倆子節點下沉動作，新來的資料再放在最新的葉子節點，再做比較父節點上浮動作。維護成本O 2...
關於演算法導論定理3 1，為什麼感覺快速排序的時間複雜度不滿足這個定理？
猥瑣的民工 快排無論你用什麼方法選基點，在運氣最倒霉的情況下，也就是每次選基點都剛好碰上區間內的最大或最小值的時候，複雜度提高為O n 2 是必然會發生的。儘管這種情況發生的概率極低，大約是1 n 但在你重複測試了n 次之後很可能會發生一次。 TravorLZH 對於某一種情況下 好 壞 平均 的時...