STL的list :: sort()使用哪种排序算法？

Question

我有一个随机整数列表.我想知道该list::sort()方法使用哪种算法.例如,在以下代码中:

list<int> mylist;

// ..insert a million values

mylist.sort();

编辑:另见这个更具体的问题.

Answer 1

该标准不需要特定的算法,只需要它必须是稳定的,并且它使用大约N lg N个比较来完成排序.例如,这允许快速排序的合并排序或链接列表版本(与普遍看法相反,快速排序不一定是不稳定的,即使数组的最常见实现是).

有了这个附带条件,简短的回答是,在大多数当前的标准库中,std::sort实现为一个介绍排序(内省排序),它基本上是一个跟踪其递归深度的Quicksort,并将切换到一个Heapsort(通常较慢但是如果Quicksort使用太深的递归,则保证O(n log n)复杂度.Introsort最近发明了(1990年代后期).较旧的标准库通常使用Quicksort.

stable_sort存在是因为对于类似数组的容器的排序,大多数最快的排序算法都是不稳定的,因此标准包括std::sort(快速但不一定稳定)和std::stable_sort(稳定但通常稍慢).

但是,这两者通常都需要随机访问迭代器,并且在链接列表等方面效果不佳(如果有的话).为了获得链接列表的良好性能,该标准包括list::sort.然而,对于链表而言,实际上并没有任何这样的权衡 - 实现合并排序非常容易,这种合并排序既稳定又和其他任何东西一样快.因此,他们只需要一个sort要求稳定的成员函数.

Answer 2

它是完全实现定义的.标准中唯一指出的是它的复杂性是O(n lg n),并且排序是稳定的.也就是说,相等元素的相对顺序保证在排序后不会改变.

std::list排序成员函数通常使用某种形式的合并排序来实现,因为合并排序是稳定的,并且当您使用链接列表时合并确实非常便宜.

希望有帮助:)