C11 标准保证在最坏情况下std::sort具有O(n logn) 复杂度 。这与 C98/03 中的平均情况保证不同，在 C++98/03 中可以使用快速排序（可能与小 n 的插入排序结合）来实现，在最坏的情况下（对于某些特定的输入，例如排序输入）。std::sort
std::sort
std::sort不同 STL 库中的实现是否有任何变化？C++11 是如何std::sort在不同的 STL 中实现的？
可以看到这两个库都使用了 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
