lak*_*oma 7 c sorting programming-languages standard-library
从我的(简要)阅读,Java和Python看起来他们在他们的标准库中使用timsort,而C的stdlib中的排序方法被称为qsort,因为它曾经是快速排序.
今天典型语言在其标准库中实现了什么算法,为什么他们选择该算法呢？此外,C是否偏离了快速排序？
我知道这个问题缺乏"我面临的实际问题",并且可能看起来对某些人开放,但知道如何/为什么选择某些算法作为标准看起来非常有用但相对没有用处.我还觉得,如果一个深入的答案解决特定于语言(数据类型？)和机器特定(缓存命中？)的问题,将提供更多洞察不同语言和算法的工作方式,而不是单一关心解释.
我的机器的 C 库提供了qsort、heapsort、 和，在手册页mergesort中说：
和函数是 CAR Hoare 的“快速排序”算法的实现，该算法是分区交换排序的一种变体
qsort()；qsort_r()特别是，请参阅 DE Knuth 的算法 Q。快速排序平均需要O(n lg n)时间。此实现使用中值选择来避免其O(n 2 )最坏情况行为。该
heapsort()函数是 JWJ William 的“堆排序”算法的实现，该算法是选择排序的一种变体；特别是，请参阅 DE Knuth 的算法 H。堆排序在最坏情况下需要O(n lg n)时间。它唯一的优点qsort()是它几乎不使用额外的内存；whileqsort()不分配内存，是使用递归实现的。该函数
mergesort()需要额外的 size 字节内存nel * width；仅当空间不宝贵时才应使用它。该mergesort()函数针对已有订单的数据进行了优化；最坏情况时间为O(n lg n)；最好的情况是O(n)。通常，
qsort()比 更快 比mergesort()更快heapsort()。内存可用性和数据中预先存在的顺序可能会使这种情况变得不真实。
如果您想了解实现的具体细节，有很多开源 C 库可供您查看。
至于“为什么系统 X 选择算法 Y”，这是一个很难有意义地回答的问题 - 如果你没有足够幸运在文档中找到基本原理，你就必须直接询问设计者。