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

Question

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

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

Answer 1

浏览 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。