c++ - std::sort 是否实现快速排序？

Question

这个问题在这里已经有了答案:

关闭 9年前。

Possible Duplicate:
which type of sorting is used in the function sort()?

std::sort 是否实现了快速排序？

Answer 1

传统上使用两种算法。

std::sort最有可能使用QuickSort ，或者至少是 QuickSort 的一种变体，称为 IntroSort ，它“退化”为 HeapSort当递归太深时。

来自标准:

Complexity: O(N log(N)) comparisons.

std::stable_sort 最有可能使用 MergeSort , 因为稳定性要求。但是请注意，MergeSort 需要额外的空间才能提高效率。

来自标准:

Complexity: It does at most N log²(N) comparisons; if enough extra memory is available, it is N log(N).

我还没有看到实现 TimSort 的 std::sort这是很有前途的，并已在 Python(实际上是为它精心设计的)、Java 和 Android(迄今为止)中采用。