快速排序的運行時間並不穩定，憑什麼被命名作「快速」排序？

01-09

快排最壞情況下，複雜度能達到 $O(n^2)$ 。我做演算法題的時候，有好幾次快排都被卡掉了，反而歸併排序一直十分穩定。堆排序的複雜度也是 $O(n log(n))$ ，而且沒有額外空間消耗。這麼多優秀的排序演算法，為什麼快排這種不穩定的排序演算法卻能叫做「快排」呢？（最關鍵的是，好像快排是工業界普遍採用的排序演算法。）
我知道快排肯定有它快的原因。通過數據分析，只能得到它「快」這個結果，卻不知道它為什麼快。而我想問的就是：它為什麼快？或者它根本不快？

quicksort的期望運行時間是 $O (nlog n)$ , 而且前面的常係數比較小。

在大量的隨機輸入下最壞情況 $O(n^{2})$ 出現的概率是極小的。

優化的partition過程進行原地排序(In place sort)，相比歸併排序這種非原地排序，可以更好地利用cache。堆排和歸併只是理論上的漸近最優(asymptotically optimal)，在實際應用中還要考慮體系結構的影響。更深入的解釋的就需要資訊理論的知識了，可以參考劉未鵬的博文數學之美番外篇：快排為什麼那樣快

就是因為能被卡掉，一般我們都用別的，比如introsort之類的

平凡快排確實容易被卡掉，你試試優化過的快排，幾乎不會遇到O(n^2)的情況。

參考資料《編程珠璣》

高效排序演算法里快排的常數1.38，最小，所以叫快排，這是算設常識。

另：快不快應該寫用理論分析，一般的就是寫遞歸式化解析式那一套，而不是用A題命中率判斷。

這麼說的原因是：

1.題目的數據可能存在特殊的分布，如果再細緻一點分析，可以把數據的分布考慮進去分析性能。

2.既然是題，那麼不一定只是簡單的排序，固定操作的時間與你要做的工作多複雜有關，也和數據量有關，性能是漸進意義下的。

可以看到，工業界多用快排當然是理論指導實踐的產物，因為工業界的數據分布更一般，更有說服力。

另：

如果非嫌不夠快，理論上的高效演算法多的是，隨機化演算法也許符合您的要求？但相信以A題為目的的話肯定不會有興趣搞那麼複雜了。

另：

深究排序問題請看TAOCP3

快速排序的常數因子小，是原址排序。

快速排序之所以不穩定是因為它根據基準數排序，基準數選不好的話兩邊就可能嚴重不協調。

因此有快速排序的進化隨機化快排和比如C++ stl里的sort.

歸併排序之所以穩定是因為它根據數組的下標排序，絕對協調。

推薦一個網站：數據結構和演算法動態可視化 (Chinese)

我覺得題主根本沒測過。大量數據快排實際運行比歸併和堆排序快的多。除非你是順序什麼的。這個你可以自己寫個測試程序什麼的。

還有快排的不穩定性是指同一鍵值的數據的相對順序會發生變化，這個實際運用一點也不重要。

如果說是海量隨機數據，快排的速度絕對是穩定的。

有一句話說得好：隨機總是能解決大部分問題的。

但是隨機會導致常數大……但是隨機好寫。

一般來說c++直接用sort就可以了