在不同的STL实现中，C 11d::排序中使用了哪些算法？

Question

C 11标准保证在最坏的情况下，std:：sort具有O（n logn）复杂性。这与C 98/03中的平均情况保证不同，在C 98/03中，std:：sort可以通过快速排序（可能与小n的插入排序相结合）实现，在最坏的情况下（对于某些特定的输入，例如排序输入），插入排序有O（n^2）。

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

Answer 1

浏览libstdc和libc的在线资源，你可以看到这两个库都使用了来自介绍排序主循环的众所周知的排序算法的全部色域：

对于std::排序，有一个insertion_sort的辅助例程（一个O（N^2）算法，但具有良好的缩放常数，使其对小序列具有竞争力），外加一些特殊的大小写0、1、2和3元素的子序列。

对于std:：partial_sort，这两个库都使用heap_sort（O（N log N））的一个版本，因为该方法有一个很好的不变量，它保持了一个排序后的子序列（它通常有一个更大的缩放常数，使完全排序的成本更高）。

对于std:：N_元素，有一个用于选择_排序的辅助程序例程（同样是一个O（N^2）算法，该算法具有良好的sclaing常量，使其对小序列具有竞争力）。对于常规排序插入\u排序通常占主导地位选择\u排序，但对于第n个元素而言，具有最小元素的不变量与选择\u排序的行为完全匹配。

Answer 2

问题是，STL怎么能说std:：sort最坏的情况是O（N log（N）），即使它本质上是一个快速排序。STL的排序是IntroSort。IntroSort本质上是一种快速排序，引入的差异改变了最坏情况下的复杂性。

无论您选择什么分区，都存在一个序列，QuickSort将在O（N^2）上运行。您选择的分区只会降低最坏情况发生的概率。（随机轴选择、三个中位数等）

编辑：感谢@Maxims 1000的更正。中位数枢轴选择算法的快速排序最坏情况复杂度为O（N log（N）），但由于它引入的开销，在实践中没有使用它。它从理论上说明了好的选择算法如何通过枢轴选择改变最坏情况的复杂性。

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

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

现在，（n logn）之和是最坏情况的复杂性。

对于最坏的快速排序情况；假设我们有一个已经排序的数组，我们总是选择这个数组中的第一个元素作为轴心。在每次迭代中，我们只去掉第一个元素。如果我们一直这样走到最后，显然是O（N^2）。使用IntroSort，当到达深度日志（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-记录（N））操作已完成。我们可以简单地说，N（N-1）。。。（N-对数（N））

HeapSort部分是（N-log（N））log（N-log（N））

整体复杂度

由于常数可以省略，IntroSort的最坏情况复杂度是O（nlog（N））。

添加信息：GCC STL实现源代码在这里<代码>排序功能位于第5461行。

更正：*微软。NET*排序实现是自2012年引入排序。相关信息在这里。