Timsort-您从未听说过的最快的排序算法

Timsort：针对现实世界构建的非常快速的O（n log n）稳定排序算法-并非在学术界构建。

单击此处查看更新的文章：

Timsort是一种排序算法，对于实际数据非常有效，并且不是在学术实验室中创建的。 提姆·彼得斯（Tim Peters）于2001年为Python编程语言创建了提姆（Timsort）。提姆（Timsort）首先分析要尝试排序的列表，然后根据对列表的分析选择一种方法。

自从发明了该算法以来，它已被用作Python， Java ， Android平台和GNU Octave中的默认排序算法。

Timsort的大O表示法是O（n log n）。 要了解Big O表示法，请阅读此内容 。

Timsort的排序时间与Mergesort相同，这比您可能知道的大多数其他排序要快。 正如您很快就会看到的，Timsort实际上利用了插入排序和合并排序。

Peters将Timsort设计为使用大多数现实世界数据集中存在的已排序元素。 它称这些已经排序的元素为“自然运行”。 它遍历数据，将元素收集到运行中，同时将这些运行合并为一个。

数组中的元素少于64个

如果我们要排序的数组中少于64个元素，Timsort将执行插入排序。

插入排序是一种简单的排序，对小列表最有效。 对于较大的列表，它相当慢，而对于较小的列表，它非常快。 插入排序的概念如下：

• 一一看待元素
• 通过将元素插入正确的位置来建立排序列表

这是一个跟踪表，显示插入排序将如何对列表进行排序[34，10，64，51，32，21]

在这种情况下，我们将新排序的元素插入到新的子数组中，该子数组从数组的开头开始。

这是显示插入排序的gif：

有关跑步的更多信息

如果列表大于64个元素，则算法将首先通过列表查找严格增加或减少的零件。 如果该部分正在减少，它将反转该部分。

因此，如果运行减少，则将如下所示（运行以粗体显示）：

如果不减少，它将看起来像这样：

最小行程是根据数组的大小确定的大小。 该算法选择它，以便随机数组中的大多数游程的长度为minrun或变为最小游程。 当运行次数等于或小于2的幂时，合并2个阵列会更有效。 Timsort选择minrun来尝试通过确保minrun等于或小于2的幂来确保这种效率。

该算法从32到64（含）范围内选择minrun。 它选择minrun，以使原始数组的长度除以minrun等于或小于2的幂。

如果运行的长度小于minrun，则可以从minrun计算该运行的长度。 使用此新编号，您可以在运行之前捕获许多项目，并执行插入排序以创建新的运行。

因此，如果minrun为63且运行长度为33，则执行63–33 =30。然后从运行结束之前获取30个元素，因此这是来自run [33]的30个项目，然后执行插入排序以创建新的运行。

这部分完成之后，我们现在应该在列表中有一堆排序的运行。

合并中

Timsort现在执行mergesort将运行合并在一起。 但是，Timsort确保在合并排序时保持稳定性和合并平衡。

为了保持稳定性，我们不应交换2个相等值的数字。 这样不仅可以将其原始位置保留在列表中，还可以使算法更快。 我们将在短期内讨论合并余额。

当Timsort找到运行时，它将它们添加到堆栈中。 一个简单的堆栈如下所示：

想象一堆盘子。 您不能从底部取板，因此必须从顶部取板。 堆栈也是如此。

在运行mergesort时，Timsort试图平衡两个相互竞争的需求。 一方面，我们希望尽可能长地延迟合并，以利用以后可能出现的模式。 但是我们甚至希望尽快合并，以利用刚刚发现的运行在内存层次结构中仍然很高的运行。 我们也不能延迟“太长”的合并，因为它会消耗内存以记住仍未合并的运行，并且堆栈具有固定的大小。

为了确保我们能够妥协，Timsort会跟踪堆栈中最近的三个项目，并创建两个必须满足这些条件的定律：

1. A> B + C

2. B> C

其中A，B和C是堆栈中最近的三个项目。

用蒂姆·彼得斯本人的话说：

事实证明，这是一个很好的折衷方案，在堆栈条目上保留了两个不变式，其中A，B和C是三个最严格的尚未合并切片的长度

通常，很难将不同长度的相邻行合并到位。 更难的是，我们必须保持稳定。 为了解决这个问题，Timsort保留了临时内存。 它将两个运行中较小的（调用运行A和B）都放入该临时内存中。

疾驰

Timsort将A和B合并时，它注意到一次运行已连续多次“获胜”。 如果事实证明运行A的数量完全少于运行B的数量，则运行A最终会回到其原始位置。 合并这两个运行将涉及大量工作，但一无所获。

数据通常会具有一些预先存在的内部结构。 Timsort假设，如果运行A的很多值都低于运行B的值，那么A可能会继续具有比B小的值。

然后，Timsort将进入舞动模式。 Timsort不会对A [0]和B [0]进行相互检查，而是对a [0]中b [0]的适当位置执行二进制搜索。 这样，Timsort可以将A的整个部分移到适当的位置。 然后，Timsort搜索B中A [0]的适当位置。然后，Timsort将立即移动B罐的整个部分并将其放置到位。

让我们看看实际情况。 Timsort检查B [0]（为5），并使用二进制搜索在A中寻找正确的位置。

好吧，B [0]属于A列表的后面。现在，Timsort在B的正确位置检查A [0]（即1）。因此，我们正在寻找数字1的去向。 此数字位于B的开头。我们现在知道B属于A的结尾，而A属于B的开头。

事实证明，如果B [0]的适当位置非常接近A的开头（反之亦然），则此操作不值得。 因此，如果不赚钱，疾驰模式会迅速退出。 此外，Timsort注意到了这一点，并通过增加进入所需的连续仅A或仅B获胜次数，使以后更难以进入驰op模式。 如果疾驰模式得到回报，Timsort使得重新输入变得更加容易。

简而言之，Timsort的两件事情做得非常好：

• 具有预先存在的内部结构的阵列性能出色
• 能够保持稳定的排序

以前，为了实现稳定的排序，您必须使用整数压缩列表中的项目，然后将其作为元组数组进行排序。

码

如果您对代码不感兴趣，请随时跳过此部分。 本节下面有更多信息。

下面的源代码基于我和Nanda Javarma的工作。 源代码不完整，也不类似于Python的官方sorted（）源代码。 这只是我为了使人对Timsort的总体感觉而愚蠢的Timsort。 如果您想全面了解Timsort的原始源代码，请在此处查看 。 Timsort是用C而不是Python正式实现的。

Timsort实际上是直接内置在Python中的，因此此代码仅用作解释器。 要使用Timsort，只需编写：

list.sort()

要么

sorted(list)

如果您想掌握Timsort的工作原理并对此有所了解，我强烈建议您尝试自己实现它！

本文基于蒂姆·彼得斯（Tim Peters）对蒂姆索尔（Timsort）的原始介绍，可在此处找到。

你喜欢这篇文章吗？ 在社交媒体上与我联系，讨论与计算机科学相关的所有事物????

推特 | Instagram的 | 领英

不要忘记单击“拍手”按钮以表示感谢！

我写这篇文章没有得到报酬。 如果您想支持我，请随时给我买咖啡或低于????的东西。

From: https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399