std::sort是否实现了快速排序算法？

Question

可能是重复问题：
sort()函数使用哪种类型的排序算法？

std::sort 是否实现了快速排序算法？

- ajay

---

维基百科指出该特定算法未被具体说明。 - Sapph

Answer 1

传统上使用了两种算法。

std::sort 最有可能使用 快速排序，或者至少是一个变体的快速排序称为 内省排序，当递归深度过深时，“退化”成 堆排序。

来自标准库：

复杂度：O(N log(N)) 次比较。

std::stable_sort 最有可能使用 归并排序，因为要求稳定性。但请注意，为了使归并排序高效，需要额外的空间。

来自标准库：

复杂度：最多进行 N log²(N) 次比较；如果有足够的额外内存，则为 N log(N)。

我还没有看到实现 TimSort 的 std::sort，它很有前途，并已在 Python、Java 和 Android 中得到采用（实际上是为其打造的）。

- Matthieu M.

---

@maxim-yegorushkin：维基百科文章似乎还声称introsort会切换到插入排序而不是堆排序:/ http://en.wikipedia.org/wiki/Sort_(C%2B%2B) “例如，GNU标准C++库使用混合排序算法：首先执行introsort，最大深度为2×log2 n（其中n是元素数量），然后对结果进行插入排序。” - Antony Stubbs

因为QuickSort的最坏情况是O(N^2)，你介意更新答案吗？因为在C++11+兼容实现中不再可以使用它。 - NathanOliver

Answer 2

来自维基百科 -

具体的排序算法并没有强制规定，可能会因实现而异。排序维基链接

- Mahesh

---

尽管在这种情况下可能是真的，但我会非常小心地阅读维基百科上的内容。当涉及到引用参考资料时，最好引用标准文献。 - ereOn

Answer 3

我认为是这样的。std::list有一个sort方法，或者你可以从中调用sort，它需要2个迭代器，即begin和end。

- Syl

Answer 4

由于快速排序的最坏时间复杂度较高（N^2），而且在链表上实现相对困难，我认为不应该使用快速排序来进行排序。

- ashmish2

---

std::sort 无法用于链表，因此这不是一个问题。 - Matthieu M.