c++ - C++11 std::sort 在不同的 STL 实现中使用了哪些算法？

Question

C++11 标准保证 std::sort 具有 O(n logn) complexity 在最坏的情况下。这与 C++98/03 中的 average-case 保证不同，其中 std::sort 可以使用 Quicksort 实现(可能结合插入排序用于小 n )，最坏的情况是 O(n^2)(对于某些特定的输入，例如排序的输入)。

不同 STL 库中的 std::sort 实现是否有任何变化？ C++11的std::sort在不同的STL中是如何实现的？

Answer 1

问题是，STL 怎么能说 std::sort最坏的情况是 O(N log(N))，尽管它本质上是一个 QuickSort。 STL 的排序是IntroSort。 IntroSort 本质上是 QuickSort，引入的差异改变了最坏情况的复杂性。

---

QuickSort 最坏情况是 O(N^2)

无论您选择什么分区，QuickSort 都会在 O(N^2) 上运行一个序列。您选择的分区只会降低最坏情况发生的概率。 (Random Pivot Selection，三中位数，etc.)

编辑:感谢@maxim1000 的修正。使用枢轴选择算法进行快速排序Median of Medians具有 O(N log(N)) 最坏情况复杂度，但由于它引入的开销，它在实践中并未使用。它展示了优秀的选择算法在理论上如何通过枢轴选择来改变最坏情况的复杂性。

---

IntroSort 有什么作用？

IntroSort 限制了 QuickSort 的分支。这是最重要的一点，限制是 2 * (log N)。当达到限制时，IntroSort 可以使用最坏情况复杂度为 O(N log(N)) 的任何排序算法。

当我们有 O(log N) 个子问题时，分支停止。我们可以解决每个子问题 O(n log n)。 (小写的 n 代表子问题的大小)。

现在，(n log n) 的总和是我们最坏情况的复杂度。

对于快速排序的最坏情况；假设我们有一个已经排序的数组，并且我们总是选择这个数组中的第一个元素作为枢轴。在每次迭代中，我们只删除第一个元素。如果我们一直这样走到最后，那显然是O(N^2)。使用 IntroSort 我们停止 QuickSort，当我们达到深度 log(N) 时，我们使用 HeapSort 来处理剩余的未排序数组。

16 -> 1  /**N**/
   \
    > 15 -> 1 /**N - 1**/
         \
          > 14 -> 1 /**N - 2**/
               \
                > 13 -> 1 /**N - log(N)**/  
                     \
                      > 12 /**(HeapSort Now) (N - log(N)) log (N - log(N))**/

总结一下；

直到分支停止，N + (N - 1) + ... + (N - log(N))完成的操作。不用高斯来总结，我们可以简单地说N + (N - 1) + ... + (N - log(N)) < N log(N) .

堆排序部分是 (N - log(N)) log(N - log(N)) < N log(N)

总体复杂性 < 2 N log(N) .

由于常量可以省略，IntroSort的最坏情况复杂度为O(N log(N))。

---

添加信息: GCC STL 实现源代码为 here . Sort函数位于 5461 行。

更正: *Microsoft .NET* sort 自 2012 年起实现为 IntroSort。相关信息为 here .