C++ std::sort 是否实现了快速排序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5038895/
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
Does std::sort implement Quicksort?
提问by ajay
Possible Duplicate:
which type of sorting is used in the function sort()?
可能的重复：
在函数 sort() 中使用哪种类型的排序？
Does std::sort implement Quicksort?
std::sort 是否实现了快速排序？
回答by Matthieu M.
There are two algorithms that are traditionally used.
有两种传统上使用的算法。
std::sortis most likely to use QuickSort, or at least a variation over QuickSort called IntroSort, which "degenerates" to HeapSortwhen the recursion goes too deep.
std::sort最有可能使用QuickSort，或者至少是QuickSort 的一个变体，称为IntroSort，当递归太深时，它“退化”为HeapSort。
From the standard:
从标准：
Complexity: O(N log(N)) comparisons.
复杂性：O(N log(N)) 次比较。
std::stable_sortis most likely to use MergeSort, because of the stability requirement. However note that MergeSort requires extra space in order to be efficient.
std::stable_sort由于稳定性要求，最有可能使用MergeSort。但是请注意，MergeSort 需要额外的空间才能提高效率。
From the standard:
从标准：
Complexity: It does at most N log2(N) comparisons; if enough extra memory is available, it is N log(N).
复杂性：最多进行 N log 2(N) 次比较；如果有足够的额外内存可用，则为 N log(N)。
I have yet to see a std::sortimplementing TimSortwhich is promising and has been adopted in Python (crafted for it in fact), Java and Android (to date).
我还没有看到有前途的TimSortstd::sort实现，并且已经在 Python（实际上是为它设计的）、Java 和 Android（迄今为止）中采用。
回答by Mahesh
From Wikipedia -
来自维基百科——
The specific sorting algorithm is not mandated and may vary across implementations. Sort Wiki Link
特定的排序算法不是强制性的，可能因实现而异。排序维基链接
回答by Syl
I think so. std::list has a sort method, or you can call sort from which takes 2 iterators, begin and end.
我想是这样。std::list 有一个 sort 方法，或者您可以调用 sort 从中获取 2 个迭代器，开始和结束。
回答by ashmish2
because of high worst complexity of quicksort (N^2) and relatively tough to implement on linklist. I thinksort will not be done using quicksort
由于快速排序（N^2）的最坏复杂度很高，并且在链表上实现起来相对困难。我认为不会使用快速排序来完成排序
