代码之家 › 专栏 › 技术社区 › sharkin

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

stl sorting algorithm c++

sharkin · 技术社区 · 15 年前

我有一个随机整数的列表。我想知道 list::sort() 方法。例如,在以下代码中:

list<int> mylist;

// ..insert a million values

mylist.sort();

编辑:参见 this more specific question .

3 回复 | 直到 7 年前

Jerry Coffin 9 年前

标准不需要特定的算法,只需要它必须是稳定的,并且它使用大约n lg n的比较完成排序。例如,允许合并排序或快速排序的链接列表版本(与流行的观点相反,快速排序不是 必要地 不稳定,即使最常见的数组实现是)。

有了这个条件,最简单的答案是在大多数当前的标准库中, std::sort 是作为一个内省排序(内省排序)实现的,它基本上是一个跟踪递归深度的快速排序,如果快速排序使用的递归深度太深,它将切换到一个堆排序(通常较慢但有保证的o(n log n)复杂性)。不过,IntroSort的发明相对较晚(20世纪90年代末)。旧的标准库通常使用快速排序。

stable_sort 存在的原因是,对于像容器这样的排序数组,大多数最快的排序算法都是不稳定的,因此标准包括 标准::排序 (快速但不一定稳定)和 std::stable_sort (稳定,但通常较慢)。

但是,这两种方法通常都需要随机访问迭代器,并且在处理类似于链表的内容时工作得很糟糕(如果有的话)。为了获得链接列表的良好性能,标准包括 list::sort . 然而,对于一个链表,实际上并没有任何这样的权衡——实现一个既稳定又稳定的合并排序是非常容易的。和 (大约)和其他东西一样快。因此,他们只需要一个 sort 需要稳定的成员函数。