C 11标准保证 在最坏的情况下std::sort具有O（n logn）复杂度 。这与C 98/03中的 平均情况* 保证不同，后者可以通过Quicksort（可能与小n的插入排序结合使用）实现，后者在最坏的情况下（对于某些特定情况，具有O（n ^ 2））输入，例如已排序的输入）。 ***std::sort
std::sort
std::sort不同的STL库中的实现是否有任何更改？如何std::sort在不同的STL中实现C ++ 11 ？
浏览 libstdc ++ 和 libc ++ 的在线资源，可以看到这两个库都使用了intro- sort主循环中的全部已知排序算法：
对于std::sort，有一个辅助例程insertion_sort（一种O(N^2)算法，但具有良好的缩放常数，使其对于小的序列具有竞争力），以及一些特殊的大小写，分别用于0、1、2和3个元素的子序列。
insertion_sort
O(N^2)
对于std::partial_sort，这两个库都使用heap_sort（O(N log N)通常）版本，因为该方法具有很好的不变性，可以保留排序后的子序列（通常具有较大的缩放常数，从而使其在进行完整排序时更加昂贵）。
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。
std::nth_element
selection_sort
nth_element
