C++ 标准库中 std::sort() 的时间复杂度是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4484900/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the time complexity of std::sort() in the C++ standard library?
提问by Hari Chaudhary
What is the complexity of std::sort()in the C++ Standard Library? Which sort is applied? Is there any rule of applying any particular sorting algorithm there?
std::sort()C++ 标准库中的复杂度是多少？应用哪种类型？是否有任何应用任何特定排序算法的规则？
回答by James McNellis
Before C++11:
在 C++11 之前：
std::sortmust have average case linearithmic (n log n) time complexity. Any algorithm may be used so long as that time complexity requirement is met. There is no worst case time complexity requirement.
std::sort必须具有平均情况线性 (n log n) 时间复杂度。只要满足时间复杂度要求，就可以使用任何算法。没有最坏情况的时间复杂度要求。
If you want a guaranteed worst case time complexity function, use std::stable_sort, which has quasilinear worst case time complexity (n log^2 n).
如果您想要有保证的最坏情况时间复杂度函数，请使用std::stable_sort，它具有拟线性最坏情况时间复杂度 (n log^2 n)。
回答by Shoe
The standard guarantees
标准保证
From the C++11/14 standard, std::sortis guaranteed to have:
从 C++11/14 标准开始，std::sort保证具有：
§25.4.1.1/3
Complexity:
O(N log(N))(whereN == last - first) comparisons.
§25.4.1.1/3
复杂性：（
O(N log(N))其中N == last - first）比较。
The other, stable, standard sorting algorithm (namely std::stable_sort) is guaranteed to have:
另一种稳定的标准排序算法（即std::stable_sort）保证具有：
25.4.1.2/3
Complexity: It does at most
N log2(N)(whereN == last - first) comparisons; if enough extra memory is available, it isN log(N).
25.4.1.2/3
复杂性：它最多进行
N log2(N)(whereN == last - first) 比较；如果有足够的额外内存可用，则为N log(N).
For std::forward_list::stable, instead:
对于std::forward_list::stable，改为：
23.3.4.6/26
Complexity: Approximately
N log(N)comparisons, whereNisdistance(begin(), end()).
23.3.4.6/26
复杂性：近似
N log(N)比较，其中N是distance(begin(), end())。
The same goes for std::list:
这同样适用于std::list：
23.3.5.5/31
Complexity: Approximately
N log(N)comparisons, whereN == size().
23.3.5.5/31
复杂性：近似
N log(N)比较，其中N == size().
Sorting algorithm
排序算法
The C++ standard does not specify which sorting algorithm to apply in any of the above cases. This would be oftentimes and unnecessary implementation restriction.
C++ 标准没有指定在上述任何情况下应用哪种排序算法。这通常是不必要的实施限制。
If you need to know you might have luck looking in a specific compiler specification. For example for GNU GCC you would start here.
如果您需要知道，您可能会很幸运地查看特定的编译器规范。例如，对于 GNU GCC，您可以从这里开始。
回答by Stuart Golodetz
The complexity is O(n log n). Some common implementations use introsort as far as I know:
复杂度是O(n log n)。据我所知，一些常见的实现使用 introsort：
回答by Adam Vandenberg
http://en.wikipedia.org/wiki/Sort_(C%2B%2B)
http://en.wikipedia.org/wiki/Sort_(C%2B%2B)
The specific sorting algorithm is not mandated and may vary across implementations. The GNU Standard C++ library, for example, uses a hybrid sorting algorithm: introsort is performed first, to a maximum depth given by 2×log2 n, where n is the number of elements, followed by an insertion sort on the result.[1] Whatever the implementation, the complexity should be O(n log n) comparisons on the average. [2]
特定的排序算法不是强制性的，并且可能因实现而异。例如，GNU 标准 C++ 库使用混合排序算法：先执行 introsort，最大深度为 2×log2 n，其中 n 是元素数，然后对结果进行插入排序。 [1 ] 无论是什么实现，平均复杂度应该是 O(n log n) 次比较。[2]
回答by wkl
If you mean std::sort():
如果你的意思是std::sort()：
This is from C++03 standard, section 25.3. The performance guarantee:
这是来自 C++03 标准的第 25.3 节。性能保证：
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
1 Effects: Sorts the elements in the range [first, last).
2 Complexity: Approximately N log N (where N == last - first) comparisons on the average.
1 效果：对范围 [first, last) 中的元素进行排序。
2 复杂性：平均约 N log N（其中 N == last - first）比较。
回答by maxschlepzig
The C++ standard specifiesthat the worst-case runtimeof std::sort()is in O(n log n)- where nis number of sorted elements (cf. C++11, Section 25.4.1.1).
在C ++标准规定了最坏情况下的运行时间的std::sort()是在O(n log n)- ，其中n是有序元素的数目（参见C ++ 11，第25.4.1.1）。
The standard doesn't specify a particular sorting algorithm.
该标准没有指定特定的排序算法。
Thus, a conforming std::sort()implementation is free to choose any algorithm that satisfies the above runtime requirement.
因此，符合要求的std::sort()实现可以自由选择满足上述运行时要求的任何算法。
Note that C++ standard revisions before C++11 just required that the averageruntimeof std::sort()is in O(n log n).
请注意，前C C ++标准的修订++ 11只是需要将平均运行的std::sort()是O(n log n)。
See also the stackoverflow question What algorithms are used in C++11 std::sort in different STL implementations?to get an idea what actual sorting algorithms are used in real-world STL implementations.
另请参阅 stackoverflow 问题C++11 std::sort 在不同的 STL 实现中使用了哪些算法？了解实际 STL 实现中使用的实际排序算法。
