STL的list::sort()使用哪种排序算法？
我有一个随机整数列表。我想知道 list::sort() 方法使用哪种算法。例如，在以下代码中：
list<int> mylist;
// ..insert a million values
mylist.sort();
编辑：另请参阅这个更具体问题。
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<int> mylist;
// ..insert a million values
mylist.sort();
EDIT: See also this more specific question.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
该标准不要求特定的算法，只要求它必须稳定，并且使用大约 N lg N 次比较来完成排序。例如，这允许合并排序或快速排序的链表版本（与流行的看法相反，快速排序不一定不稳定，尽管数组最常见的实现是）。
有了这个附带条件，简短的答案是，在大多数当前的标准库中，std::sort 被实现为内向排序（内省排序），这基本上是一个跟踪其递归深度的快速排序，如果快速排序使用的递归太深，则会切换到堆排序（通常较慢，但保证复杂度为 O(n log n)）。 Introsort 的发明时间相对较晚（1990 年代末）。较旧的标准库通常使用快速排序。
stable_sort的存在是因为对于排序类似数组的容器，大多数最快的排序算法都不稳定，因此该标准既包括std::sort（快速但不一定稳定）和std::stable_sort（稳定但通常速度较慢）。然而，这两种方法通常都需要随机访问迭代器，并且对于链表之类的东西来说效果不佳（如果有的话）。为了使链表获得良好的性能，该标准包括
list::sort。然而，对于链表来说，实际上并不存在任何这样的权衡——实现既稳定又与其他任何东西一样快的合并排序非常容易。因此，他们只需要一个需要稳定的sort成员函数。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 necessarily unstable, even though the most common implementation for arrays is).
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.stable_sortexists because for sorting array-like containers, most of the fastest sorting algorithms are unstable, so the standard includes bothstd::sort(fast but not necessarily stable) andstd::stable_sort(stable but often somewhat slower).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 onesortmember function that's required to be stable.它完全由实现定义。标准对此唯一的说明是它的复杂度是 O(n lg n)，并且排序是稳定。即保证相等元素的相对顺序在排序后不会改变。
std::list的排序成员函数通常使用某种形式的合并排序来实现，因为合并排序很稳定，并且当您使用链表时合并确实非常便宜。例如，在微软的实现中： https://github .com/microsoft/STL/blob/19c683d70647f9d89d47f5a0ad25165fc8becbf3/stl/inc/list#L512-L572希望有帮助:)
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.
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. For example, in Microsoft's implementation: https://github.com/microsoft/STL/blob/19c683d70647f9d89d47f5a0ad25165fc8becbf3/stl/inc/list#L512-L572Hope that helps :)
虽然它依赖于实现/供应商，但我知道的大多数实现都使用 Introsort，其最佳&最坏情况复杂度为 O(nlogn)。
参考：http://en.wikipedia.org/wiki/Introsort
Though is it implementation/vendor dependent, but most implementation I know uses Introsort whose best & worst case complexity is O(nlogn).
Reference:http://en.wikipedia.org/wiki/Introsort