流行的 C++ 编译器对 std::sort 和 std::stable_sort 使用什么算法? [英] What algorithms do popular C++ compilers use for std::sort and std::stable_sort?

问题描述

流行的 C++ 编译器对 std::sort 和 std::stable_sort 使用什么算法?我知道标准只给出了某些性能要求，但我想知道流行的实现在实践中使用了哪些算法.

What algorithms do popular C++ compilers use for std::sort and std::stable_sort? I know the standard only gives certain performance requirements, but I'd like to know which algorithms popular implementations use in practice.

如果它引用每个实现的参考，答案会更有用.

The answer would be more useful if it cited references for each implementation.

推荐答案

首先:编译器不提供std::sort的任何实现.虽然传统上每个编译器都预先打包了一个标准库实现(它严重依赖于编译器的内置)，但理论上您可以将一个实现换成另一个.一个很好的例子是 Clang 编译 libstdc++(传统上使用 gcc 打包)和 libc++(全新).

First of all: the compilers do not provide any implementation of std::sort. Whilst traditionally each compiler comes prepackaged with a Standard Library implementation (which heavily relies on compilers' built-ins) you could in theory swap one implementation for another. One very good example is that Clang compiles both libstdc++ (traditionally packaged with gcc) and libc++ (brand new).

现在已经不碍事了……

std::sort 传统上被实现为 intro-排序.从高层次的角度来看，这意味着一个相对标准的快速排序实现(通过一些中值探测来避免 O(n²) 最坏的情况)加上小输入的插入排序例程.然而，libc++ 实现略有不同并且更接近于 TimSort:它检测输入中已经排序的序列并避免再次对它们进行排序，从而导致在完全排序的输入上出现 O(n) 行为.它还使用优化的排序网络来处理少量输入.

std::sort has traditionally been implemented as an intro-sort. From a high-level point of view it means a relatively standard quick-sort implementation (with some median probing to avoid a O(n²) worst case) coupled with an insertion sort routine for small inputs. libc++ implementation however is slightly different and closer to TimSort: it detects already sorted sequences in the inputs and avoid sorting them again, leading to an O(n) behavior on fully sorted input. It also uses optimized sorting networks for small inputs.

std::stable_sort 本质上更复杂.这可以从标准的措辞中推断出来:复杂度是 O(n log n) if 可以分配足够的额外内存(提示 merge-sort)，但如果不是，则退化为 O(n log² n).

std::stable_sort on the other hand is more complicated by nature. This can be extrapolated from the very wording of the Standard: the complexity is O(n log n) if sufficient additional memory can be allocated (hinting at a merge-sort), but degenerates to O(n log² n) if not.

这篇关于流行的 C++ 编译器对 std::sort 和 std::stable_sort 使用什么算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！