c++ - 流行的 C++ 编译器对 std::sort 和 std::stable_sort 使用什么算法？

Question

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

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

Answer 1

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

既然这已经不成问题了……

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

std::stable_sort另一方面，本质上更复杂。这可以从标准的措辞中推断出来：如果可以分配足够的额外内存（暗示合并排序），复杂性是 O(n log n)，但如果不是，则退化为 O(n log ² n)。

Answer 2

如果我们以 gcc 为例，我们会看到它是 introsort forstd::sort和 mergesort for std::stable_sort。

如果您浏览libc++ 代码，您会发现std::stable_sort如果范围足够大，它也会使用合并排序。

您还应该注意的一件事是，虽然一般方法始终是上述方法之一，但它们都针对各种特殊情况进行了高度优化。