流行的C++编译器对std::sort和std::stable_sort使用哪些算法?我知道该标准仅给出某些性能要求,但是我想知道流行的实现在实践中使用哪种算法。
如果它为每个实现引用了引用,那么答案将更加有用。
最佳答案
首先:编译器不提供std::sort
的任何实现。传统上,每个编译器都预先打包了一个标准库实现(在很大程度上依赖于编译器的内置程序),但从理论上讲,您可以将一种实现换成另一种。一个很好的例子是Clang编译了libstdc++(传统上与gcc打包)和libc++(全新)。
现在,这已不复存在...std::sort
传统上已实现为intro-sort。从高级的角度来看,这意味着相对标准的快速排序实现(通过一些中位数探测来避免O(n2)最坏的情况),以及针对小输入的插入排序例程。但是,libc++实现略有不同,并且更接近TimSort:它检测输入中已经排序的序列,并避免再次对其进行排序,从而导致对完全排序的输入进行O(n)行为。它还将优化的sorting networks用于较小的输入。
另一方面,std::stable_sort
本质上更加复杂。这可以从标准的措辞推断:如果可以分配足够的额外内存(在合并排序时提示),复杂度为O(n log n),但如果不分配则退化为O(n log2 n)。