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

Question

C++ 11标准保证在最坏的情况下std::sort具有O(n logn)复杂度 .这与C++ 98/03中的平均情况保证不同,可以使用Quicksort实现(可能与小n的插入排序结合使用),在最坏的情况下具有O(n ^ 2)(对于某些特定情况)输入,例如排序输入).std::sort

std::sort不同的STL库中的实现是否有任何变化？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)上运行的序列.您选择的分区只会降低最坏情况发生的概率.(随机选择透视,中位数的三,等等)

编辑:感谢@ maxim1000的修正.具有枢轴选择算法的Quicksort 中位数中位数具有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)的总和是我们最坏的情况复杂度.

对于最坏的QuickSort案例; 假设我们已经有一个已排序的数组,我们总是选择此数组中的第一个元素作为数据透视表.在每次迭代中,我们只消除第一个元素.如果我们这样走到最后,那显然是O(N ^ 2).使用IntroSort,我们停止QuickSort,当我们达到深度日志(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).

HeapSort部分是 (N - log(N)) log(N - log(N)) < N log(N)

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

由于可以省略常量,因此IntroSort的最坏情况复杂度为O(N log(N)).

补充信息: GCC STL实现源代码在这里.Sort功能在5461行.

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

Answer 2

浏览libstdc ++和libc ++的在线资源,可以看到两个库都使用了来自intro-sort主循环的众所周知的排序算法:

因为std::sort,有一个辅助例程insertion_sort(一个O(N^2)算法,但具有良好的缩放常数,使其适用于小序列),加上一些特殊的套管,用于0,1,2和3个元素的子序列.

因为std::partial_sort,两个库都使用heap_sort(O(N log N)通常)版本,因为该方法具有良好的不变性,它保持排序的子序列(它通常具有更大的缩放常数,以使其对于完全排序更昂贵).

因为std::nth_element,有一个辅助程序selection_sort(同样是一个O(N ^ 2)算法,具有良好的sclaing常数,使其对小序列具有竞争力).对于常规排序insertion_sort通常占主导地位selection_sort,但对于nth_element具有最小元素的不变性与完全匹配的行为selection_sort.