7

根据我（简要）阅读的内容，Java 和 Python 看起来都在其标准库中使用了 timsort，而 C 的 stdlib 中的排序方法称为 qsort，因为它曾经是快速排序。

如今，典型语言在其标准库中实现了哪些算法，为什么选择该算法？另外，C 是否偏离了快速排序？

我知道这个问题缺乏“[我]面临的实际问题”，并且可能对某些人来说似乎是开放式的，但是知道如何/为什么选择某些算法作为标准似乎非常有用，但相对来说没有教过。我还觉得，解决语言特定（数据类型？）和机器特定（缓存命中？）的问题的深入答案将提供比 uni 关心解释的不同语言和算法如何工作的更多见解。

4

4 回答 4

2

在musl中，我们使用平滑排序。从概念上讲，它是堆排序的一种变体（同样是就地排序和 O(n log n) 时间），但它具有一个很好的特性，即对于已排序或接近排序的输入，最坏情况的性能接近 O(n)。我不相信这是最好的选择，但是使用 O(n log n) 最坏情况的就地算法似乎很难做得更好。

作为 Dijkstra 的一项鲜为人知的发明，它也很酷。:-)

于 2013-04-30T21:44:42.217 回答
1

C 没有具体说明要使用的算法qsort。

在当前的 glibc (2.17) 上qsort分配内存（使用malloc或者alloca如果需要的内存非常小）并使用合并排序算法。如果内存要求太高或malloc失败，则使用快速排序算法。

于 2013-04-30T20:48:33.060 回答
0

我在 C11 标准中对qsort()进行了快速扫描，但我找不到任何关于qsort()应该如何实现以及算法的预期时间/空间复杂度的参考。它所要说的只是关于比较器功能的某些条件。

这意味着实现可以选择任何适合 qsort() 的基于比较器的算法。例如，一个实现可以选择使用像冒泡排序这样的简单算法来实现 qsort() ，它不如真正的快速排序有效。底线是由实现决定实际算法。

于 2013-04-30T20:37:52.547 回答
0

我机器的 C 库提供qsort,heapsort和mergesort, 在手册页中说：

qsort()和qsort_r()函数是 CAR Hoare 的“快速排序”算法的一种实现，它是分区交换排序的一种变体；特别是，请参阅 DE Knuth 的算法Q。快速排序平均需要O(n lg n)时间。此实现使用中值选择来避免其O(n 2 )最坏情况行为。

该heapsort()函数是 JWJ William 的“堆排序”算法的一个实现，是选择排序的一种变体；特别是，请参阅 DE Knuth 的算法H。堆排序需要O(n lg n)最坏情况时间。它唯一的优势qsort()是它几乎不使用额外的内存。whileqsort()不分配内存，它是使用递归实现的。

该函数mergesort()需要额外的 sizenel * width个字节的内存；只有在空间不是很宝贵的情况下才应该使用它。该mergesort()功能针对已有订单的数据进行了优化；它的最坏情况时间是O(n lg n)；最好的情况是O(n)。

通常，qsort()快于mergesort()哪个 快于heapsort()。数据中的内存可用性和预先存在的顺序可能会使这不真实。

如果您想查看实现的具体细节，可以查看大量开源 C 库。

至于“为什么系统 X 选择算法 Y”，这是一个很难有意义地回答的问题——如果你没有足够幸运在文档中找到理由，你必须直接询问设计者。

于 2013-04-30T20:25:46.420 回答