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

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

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

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

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

它完全是实现定义的。标准所说的唯一一件事就是它的复杂性是O(n lg n),而这种复杂性是 稳定的 . 也就是说,等元素的相对顺序在排序后保证不变。

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

希望有帮助:)

尽管它依赖于实现/供应商,但我知道的大多数实现都使用IntroSort,其最佳和最差的情况复杂性是O(nlogn)。

参考文献: http://en.wikipedia.org/wiki/Introsort