什么是C++标准库中std :: sort()的时间复杂度？

Question

std::sort()C++标准库的复杂性是什么？应用哪种？有没有在那里应用任何特定排序算法的规则？

Answer 1

std::sort必须具有平均情况线性(n log n)时间复杂度.只要满足时间复杂度要求,可以使用任何算法.没有最坏情况时间复杂度要求.

如果您想要保证最坏情况时间复杂度函数,请使用std::stable_sort具有拟线性最坏情况时间复杂度(n log ^ 2 n)的函数.

我不知道C++ 03,但是C++ 0x草案声称O(n log n)**最坏情况**复杂性.并且`std :: stable_sort`保证在O(n log ^ 2 n)中运行. (4认同)
给我介绍"linearithmic"这个词的+1 - 之前没有遇到它,但它绝对是一个守护者:) (2认同)

Answer 2

特定的排序算法不是强制性的,并且可以在实现中变化.例如,GNU标准C++库使用混合排序算法:首先执行introsort,最大深度为2×log2 n,其中n是元素数,然后是结果的插入排序.[1 ] 无论实现什么,复杂性应该是平均O(n log n)比较.[2]

Answer 3

复杂性是O(n log n).据我所知,一些常见的实现使用introsort:

@jon_darkstar：您可能会想到 Timsort。http://en.wikipedia.org/wiki/Timsort (3认同)
刚读了介绍 introsort，很酷。让我想起了一个带有某人名字的排序，但我找不到它。nicksort，petesort，类似的东西。有谁知道这叫什么？ (2认同)

Answer 4

标准保证

根据C ++ 11/14标准，std::sort保证具有：

§25.4.1.1/ 3

复杂度：（O(N log(N))其中N == last - first）比较。

另一种稳定的标准排序算法（即std::stable_sort）保证具有：

25.4.1.2/3

复杂度：最多只能进行N log2(N)（where N == last - first）比较。如果有足够的可用额外内存，则为N log(N)。

对于std::forward_list::stable，则：

23.3.4.6/26

复杂性：约N log(N)比较，这里N是distance(begin(), end())。

同样适用于std::list：

23.3.5.5/31

复杂度：大约N log(N)比较，其中N == size()。

C ++标准未指定在上述任何情况下要应用的排序算法。这通常是不必要的实施限制。

如果您需要了解特定的编译器规范，可能会很幸运。例如，对于GNU GCC，您将从此处开始。