sta*_*tti 17 c++ compiler-construction sorting algorithm computer-science
流行的C++编译器使用什么算法用于std :: sort和std :: stable_sort？我知道标准只提供了某些性能要求,但我想知道流行实现在实践中使用哪些算法.
如果引用每个实现的引用,答案会更有用.
Mat*_* M. 19
首先:编译器不提供任何实现std::sort.虽然传统上每个编译器都预先打包了一个标准库实现(它严重依赖于编译器的内置函数),但理论上可以将一个实现交换为另一个实现.一个非常好的例子是Clang编译libstdc ++(传统上用gcc打包)和libc ++(全新).
现在这已经不在了......
std::sort传统上已经实现为简介.从高级别的角度来看,它意味着一个相对标准的快速排序实现(通过一些中位数探测来避免O(n 2)最坏的情况)与小输入的插入排序例程相结合.然而,libc ++实现略有不同,更接近TimSort:它检测输入中已经排序的序列,并避免再次对它们进行排序,从而导致完全排序的输入上的O(n)行为.它还为小输入使用优化的排序网络.
std::stable_sort另一方面,本质上更复杂.这可以从标准的措辞中推断出来:如果可以分配足够的额外内存(在合并排序时暗示),则复杂度为O(n log n ),但如果不是,则退化为O(n log 2 n).
如果我们以gcc为例,我们会看到它是introsort for std::sort和mergesort for std::stable_sort.
如果你浏览libc ++代码,你会发现std::stable_sort如果范围足够大,它也会使用mergesort .
您还应该注意的一点是,虽然一般方法始终是上述方法之一,但它们都针对各种特殊情况进行了高度优化.