STL 的 list::sort() 使用哪种排序算法? [英] Which sorting algorithm is used by STL's list::sort()?

问题描述

我有一个随机整数列表.我想知道 list::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();

另见这个更具体的问题.

推荐答案

该标准不要求特定算法，只要求它必须是稳定的，并且它使用大约 N lg N 次比较完成排序.例如，这允许快速排序的合并排序或链表版本(与流行的看法相反，快速排序并非必然不稳定，即使最常见的数组实现是).

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

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

With that proviso, the short answer is that in most current standard libraries, std::sort is 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_sort 的存在是因为对于类数组容器的排序，大多数最快的排序算法都是不稳定的，因此标准中同时包含了 std::sort(快速但不一定稳定)和 std::stable_sort(稳定但通常有点慢).

stable_sort exists because 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).

然而，这两者通常都期望随机访问迭代器，并且在使用链表之类的东西时效果不佳(如果有的话).为了获得链表的良好性能，标准包括 list::sort.然而，对于链表，实际上并没有任何这样的权衡——实现一个既稳定又(大约)与其他任何东西一样快的合并排序非常容易.因此，他们只需要一个稳定所需的 sort 成员函数.

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 的 list::sort() 使用哪种排序算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！