哪个排序算法是使用STL的名单::排序（）？ [英] Which sorting algorithm is used by STL's list::sort()?

问题描述

我有随机整数的列表。我不知道使用哪种算法由列表:: sort（）方法。例如。在下面的code：

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();

编辑：另请参阅<一个href="http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort">this更具体的问题。

See also this more specific question.

推荐答案

不需要特定的算法，只知道它必须是稳定的，而且它使用大约ñLGñ比较完成排序标准。这使得，例如，合并排序或快速排序（出乎人们意料的链表版本，快速排序是没有的不一定的不稳定，即使是最常见的实现阵列是）。

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).

编辑：至于为什么有一个 stable_sort ：分拣阵列状的容器，大部分最快的排序算法是不稳定的，所以该标准既包括的std ::排序（快，但不一定稳定）和的std :: stable_sort （稳定，但往往有些慢）。

As to why there's a stable_sort: 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).

两个那些，然而，通常期望的随机访问迭代，并且将工作不良（如果有的话）的东西，如链表。要获得不俗的表现链表，该标准包括列表::排序。对于一个链表，但是，有没有真正的任何这样的权衡 - 这是pretty的易于实现合并排序这是既稳定的和的（约）尽可能快地别的。因此，他们只需要一个排序成员的需要的是稳定的功能。

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 sort member function that's required to be stable.

这篇关于哪个排序算法是使用STL的名单::排序（）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！