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

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

stl sorting algorithm c++

sharkin · 技术社区 · 16 年前

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

list<int> mylist;

// ..insert a million values

mylist.sort();

编辑:参见 this more specific question .

3 回复 | 直到 8 年前

Jerry Coffin 10 年前

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

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

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

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

Billy ONeal IS4 16 年前

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

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

希望有帮助:)

-2

whacko__Cracko 16 年前

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

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

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

2 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

2 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前