代码之家 › 专栏 › 技术社区 › 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 回复 | 直到 6 年前

Jerry Coffin 8 年前

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

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

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

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

Billy ONeal IS4 15 年前

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

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

希望有帮助:)

-2

whacko__Cracko 15 年前

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

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

推荐文章

Julia · 矢量中相加为总和S的值的数量

1 年前

Codeforces Fan · 如何在c中的STL集合中添加lambda函数或执行自定义操作++

2 年前

C_Rod · 在模板方法中确定STL容器中项目的数据类型

2 年前

quantumwell · 将空向量放入std::map()

6 年前

BugShotGG · 如何正确地将托洛尔()应用于C中的德语大写字母,,á++

6 年前

GreyCat · C++参数类型,用于接受适用于基于范围的for循环的所有序列

6 年前

OutOfBound · 对未初始化内存使用算法的优点

6 年前

Adrian · 在容器、PTR和对象不可修改的情况下,如何传递unique\u ptr的容器?

6 年前

xskxzr · 为什么std::unordered\u set会重新刷新,即使负载系数限制没有打破?

6 年前

DarthRubik · 在使用列表删除之后,迭代器如何不无效

6 年前