不同的语言如何在它们的标准库中实现排序? [英] How do different languages implement sorting in their standard libraries?

问题描述

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

From what I have (briefly) read, Java and Python both look like they make use of timsort in their standard libaries, while the sorting method in C's stdlib is called qsort because it once was quicksort.

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

What algorithm do typical languages have implemented in their standard libraries today, and why did they choose that algorithm? Also, did C deviate from quicksort?

我知道这个问题缺少[我]面临的实际问题"，并且对某些人来说似乎是开放式的，但是知道如何/为什么选择某些算法作为标准似乎非常有用，但相对未学.我还觉得，解决特定于语言(数据类型?)和特定于机器(缓存命中?)的问题的深入答案将比 uni 想要解释的更深入地了解不同语言和算法的工作原理.

I know this question lacks an "actual problem(s) that [I] face" and may seem open ended to some, but knowing how/why certain algorithms are chosen as standard seems pretty useful but relatively untaught. I also feel as though an in depth answer addressing concerns that are language specific (data types?) and machine specific (cache hits?) would provide more insight to how different languages and algorithms work than uni cares to explain.

推荐答案

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

In musl, we use Smooth Sort. Conceptually it's a variant of heap sort (and likewise in-place and O(n log n) time), but it has the nice property that the worst-case performance approaches O(n) for already-sorted or near-sorted input. I'm not convinced it's the best possible choice, but it appears very difficult to do better with an in-place algorithm with O(n log n) worst-case.

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

Being a little-known invention of Dijkstra's also makes it kind of cool. :-)

这篇关于不同的语言如何在它们的标准库中实现排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！