C++ STL 的 list::sort() 使用哪种排序算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1717773/
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
Which sorting algorithm is used by STL's list::sort()?
提问by sharkin
I have a list of random integers. I'm wondering which algorithm is used by the list::sort()method. E.g. in the following code:
我有一个随机整数列表。我想知道该list::sort()方法使用哪种算法。例如在以下代码中：
list<int> mylist;
// ..insert a million values
mylist.sort();
EDIT: See also this more specific question.
编辑：另见这个更具体的问题。
回答by Jerry Coffin
The standard doesn't require a particular algorithm, only that it must be stable, and that it complete the sort using approximately N lg N comparisons. That allows, for example, a merge-sort or a linked-list version of a quick sort (contrary to popular belief, quick sort isn't necessarilyunstable, even though the most common implementation for arrays is).
该标准不需要特定的算法，只要求它必须是稳定的，并且它使用大约 N lg N 次比较来完成排序。例如，这允许快速排序的合并排序或链表版本（与流行的看法相反，快速排序不一定不稳定，即使最常见的数组实现是）。
With that proviso, the short answer is that in most current standard libraries, std::sortis implemented as a intro-sort (introspective sort), which is basically a Quicksort that keeps track of its recursion depth, and will switch to a Heapsort (usually slower but guaranteed O(n log n) complexity) if the Quicksort is using too deep of recursion. Introsort was invented relatively recently though (late 1990's). Older standard libraries typically used a Quicksort instead.
有了这个限制，简短的回答是，在大多数当前的标准库中，它std::sort是作为内省排序（introspective sort）实现的，它基本上是一个跟踪其递归深度的快速排序，并将切换到堆排序（通常较慢但如果快速排序使用太深的递归，则保证 O(n log n) 复杂度。Introsort 是最近发明的（1990 年代后期）。较旧的标准库通常使用快速排序来代替。
stable_sortexists because for sorting array-like containers, most of the fastest sorting algorithms are unstable, so the standard includes both std::sort(fast but not necessarily stable) and std::stable_sort(stable but often somewhat slower).
stable_sort存在是因为对于类数组容器的排序，大多数最快的排序算法都是不稳定的，因此标准包括std::sort（快速但不一定稳定）和std::stable_sort（稳定但通常有点慢）。
Both of those, however, normally expect random-access iterators, and will work poorly (if at all) with something like a linked list. To get decent performance for linked lists, the standard includes list::sort. For a linked list, however, there's not really any such trade-off -- it's pretty easy to implement a merge-sort that's both stable and(about) as fast as anything else. As such, they just required one sortmember function that's required to be stable.
然而，这两者通常都期望随机访问迭代器，并且在使用链表之类的东西时效果不佳（如果有的话）。为了获得链表的良好性能，标准包括list::sort. 然而，对于链表，实际上并没有任何这样的权衡——实现一个既稳定又（大约）与其他任何东西一样快的合并排序非常容易。因此，他们只需要一个sort稳定的成员函数。
回答by Billy ONeal
It's completely implementation defined. The only thing the standard says about it is that it's complexity is O(n lg n), and that the sort is stable. That is, relative order of equal elements is guaranteed to not change after sorting.
它是完全实现定义的。标准关于它的唯一说明是它的复杂性是 O(n lg n)，并且排序是stable。即保证相等元素的相对顺序排序后不改变。
std::list's sort member function is usually implemented using some form of merge sort, because merge sort is stable, and merges are really really cheap when you are working with linked lists.
std::list的 sort 成员函数通常使用某种形式的归并排序来实现，因为归并排序是稳定的，而且当你使用链表时，归并真的很便宜。
Hope that helps :)
希望有帮助:)
回答by whacko__Cracko
Though is it implementation/vendor dependent, but most implementation I know uses Introsort whose best & worst case complexity is O(nlogn).
虽然它依赖于实现/供应商，但我知道的大多数实现都使用 Introsort，其最佳和最坏情况的复杂度为 O(nlogn)。
Reference:http://en.wikipedia.org/wiki/Introsort
