在不同的STL实现中,哪些algorithm用于C ++ 11 std :: sort?

C ++ 11标准保证std::sort 在最坏的情况下具有O(n logn)的复杂性 。 这与C ++ 98/03中的平均保证有所不同,在这种情况下 std::sort可以用Quicksort来实现(可能与小n的插入sorting相结合),在最坏的情况下有O(n ^ 2) (对于一些特定的input,例如sorting的input)。

不同的STL库中的std::sort实现有没有改变? C ++ 11的std::sort如何在不同的STL中实现?

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

对于std::sort ,有一个辅助函数用于insertion_sort (一个O(N^2)algorithm,但是有一个很好的比例常数,以使它在小序列上具有竞争力),加上一些特殊的子序列0,1, 2和3个元素。

对于std::partial_sort ,两个库一般都使用heap_sortO(N log N) )版本,因为该方法有一个很好的不变性,保持一个已sorting的子序列(它通常具有更大的缩放常量,使其更加昂贵为了完整的分类)。

对于std::nth_element ,有一个用于selection_sort的辅助例程(又一个O(N ^ 2)algorithm,具有良好的sclaing常量,使其在小序列中具有竞争力)。 对于常规的sorting, insertion_sort nth_element通常支配selection_sort ,但对于nth_element ,具有最小元素的不variables完全匹配selection_sort的行为。

问题是, STL怎么说std::sort最坏的情况是O(N log(N)) ,即使它本质上是一个QuickSort 。 STL的sorting是IntroSort 。 IntroSort本质上是一个QuickSort,所引入的差异改变了最糟糕的情况下的复杂性。


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

你select什么分区,存在一个QuickSort将在O(N ^ 2)上运行的序列。 您select的分区只会降低最坏情况发生的概率。 ( 随机枢轴select ,三位中间值等 )

编辑:感谢@ maxim1000的更正。 枢轴selectalgorithm的快速sorting中间值Medians具有O(N log(N))最坏的情况下的复杂性,但是由于它引入的开销,它在实践中不被使用。 这说明了selectalgorithm有多好,理论上可以通过枢纽select来改变最坏情况下的复杂度。


IntroSort做什么?

IntroSort限制了QuickSort的分支。 这是最重要的一点,限制是2 * (log N) 。 当达到限制时,IntroSort可以使用具有最坏情况复杂度O(N log(N))的任何sortingalgorithm。

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

(n log n)之和现在是我们最糟糕的情况。

对于QuickSort最糟糕的情况; 假设我们有一个已经sorting的数组,并且我们总是select这个数组中的第一个元素作为枢轴。 在每一次迭代中,我们只摆脱了第一个元素。 如果我们这样走到最后,显然是O(N ^ 2) 。 使用IntroSort时,我们停止QuickSort,当我们到达深度日志(N)时 ,我们使用HeapSort来处理剩余的未sorting数组。

 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实现源代码在这里 。 Sortfunction在5461行。

更正: * Microsoft .NET *sorting实现是自2012年以来的IntroSort。相关信息在这里 。