stl的sort和手寫快排的執行效率哪個比較高？

1樓：MashPlant

std::sort對於日常使用的情形可以說是做到了很好，但是感覺也沒有必要盲目吹捧，畢竟它的演算法總體來說並沒有超出常規的認知範圍。

對於特定的應用，std::sort不一定是最快的選擇，甚至std::stable_sort都可能直接比它要快，這是由快排和歸併這兩種演算法的特性決定的，從比較次數來看，快排的最好情形=歸併的最壞情形，所以如果比較操作非常昂貴，可以考慮std::

stable_sort，比如這個例子

#include

namespace chrono = std::chrono;

struct Int

用g++ O3編譯，在我的機器上，sort耗時3.07894s，stable_sort耗時2.32972s

當然這個例子可能過於極端了，而且其實意義也不太大。

更加平常的例子是，單純的想排序整數，這時基數排序是否是乙個更好的選擇呢?這取決與記憶體和時間的權衡，stl不能為你做這種選擇，必須根據自己的應用場景來做。

2樓：lalala

STL的qsort在partition，遞迴，第一深度方面都做了優化。小資料下自己寫和用STL基本沒有區別。但是資料量一大，STL的優勢就顯示出來了。

3樓：

STL的sort必然要比你自己寫的快排要快，因為你自己手寫乙個這麼複雜的sort，那就太閒了。STL的sort是盡量讓複雜度維持在O(N log N)的，因此就有了各種的Hybrid sort algorithm。

題主你提到的先quicksort到一定深度之後就轉為heapsort，這種是introsort。

每種STL實現使用的演算法各有不同，GNU Standard C++ Library的實現就是先introsort，然後再來個insertion sort。

References:

sort (C++)

Introsort

libstdc++: Sorting Algorithms