你需要知道的最重要的排序算法

蒂姆索特

蒂姆索特

Timsort 是最流行的排序算法，但你可能从未听说过。如果你曾在学术领域研究过排序算法，那么你可能对一些常见的排序算法并不陌生：归并排序、快速排序、二分排序等等。然而，Timsort 却非常独特。如果你使用过 Python 或 NodeJS 中的原生排序方法，那么你一定接触过 Timsort。让我们来看看 Timsort 是什么……

什么

Timsort 是一种 混合排序算法。 混合算法是指使用两个或多个子算法来解决同一问题（例如排序）的算法。混合算法会根据输入数据或在算法执行过程中的不同阶段使用其中一种子算法。混合算法的优点在于，它们可以让你结合两种算法的优点，从而找到问题的理想解决方案。

混合算法很棒，因为它们允许您结合两全其美的优势......

Timsort 内部使用了两种子算法：插入排序和合并排序。插入排序是一种排序算法，它通过逐个迭代列表中的每个项目并将其放置在正确的位置来对无序列表进行排序。

归并排序是一种分而治之的排序算法，它通过反复将列表划分为更小的列表、对这些列表进行排序，然后将排序后的列表合并在一起来对列表进行排序。

归并排序和插入排序各有优缺点。当输入列表较小时，Timsort 使用插入排序。Timsort 首先使用归并排序。输入列表被反复划分成更小的部分。

最终，如果其中一半的长度等于一次运行的长度，Timsort 将使用插入排序对列表进行排序。然后，Timsort 将使用归并排序将两个列表合并。然而，Timsort 的归并排序策略与传统的排序算法略有不同。它实现了飞驰排序方法。通常，在合并两个已排序列表时，归并排序会逐一查看输入列表中的项目，以确定应首先将哪个项目添加到结果列表中。

如何

Timsort 是 Python 编程语言中众所周知的默认排序算法。如果您胆子够大，可以去 GitHub 上看看 Timsort 的 CPython 实现。这个文件中有很多与排序相关的代码，但大多数都支持 Timsort 的基本需求，例如合并排序算法的实现。

原因

Timsort 的流行程度已超越 Python 编程语言。它是 Java、JavaScript、Node（通过 V8 JavaScript 引擎）以及 Octave 的默认排序实现。它之所以受欢迎，是因为它针对实际场景中可能遇到的列表类型进行了特别的调优。Timsort 在处理已部分排序的数据时性能卓越，因为它会在输入列表中查找“runs”。“runs”是列表的片段，至少包含两个严格按降序或升序排列的项目。

本质上，Timsort 会寻找这些已经排序的运行并将它们合并在一起，以避免在对整个列表进行排序时进行额外的工作。

对于短列表，Timsort 会回退到插入排序，因为对于少量元素，插入排序的性能往往优于合并排序。在管理递归调用和将列表重新合并在一起方面，它不像合并排序那样有开销。

结论

好了，就是这样。《算法考古学》第一期 Timsort 专题就此结束。对于那些喜欢 Cliff Notes 的朋友来说：

• Timsort 是一种自适应算法，这意味着它根据情况使用两种不同的子算法。
• Timsort 使用合并排序对列表进行排序，除非当前排序列表的长度小于特定数字 N。在 Python 中，N 为 64。
• Timsort 是 Python、Java 和 NodeJS 中的默认排序算法。

对于那些想要了解更多信息的人，我建议阅读 Tim Peters 关于该算法的原始笔记。

敬请期待更多类似的帖子！我正在创作一些有趣的东西。;)