您当前的位置：中国科技产业网 > 资讯

这可能是你听说过最快的稳定排序算法

2019-10-22 21:42:50 阅读：7114 作者：责任编辑NO。许安怡0216

作者丨Brandon Skerritt

译者丨阿拉丁

策划丨蔡芳芳

知道 Java 和 Python 的默许排序算法是什么吗？这个算法叫作 Timsort，由 Tim Peters 与 2001 年创立，是一种安稳高效的面向实在数据的排序算法。

Timsort 是一种面向实在数据的高效排序算法，它不是在学术实验室中创立出来的。2001 年，Tim Peters 为 Python 创立了 Timsort 算法。Timsort 算法首要对排序数据进行剖析，然后依据剖析成果来挑选排序方法。

在该算法呈现之后，就一向被作为 Python、Java、Android 渠道和 GNU Octave 的默许排序算法。

Timsort 的时刻复杂度是 O(n log n)。关于时刻复杂度，可以参阅下图。

Timsort 的排序时刻与归并排序相同。实际上，Timsort 运用了刺进排序和归并排序，你很快就会看到。

Timsort 运用了存在于大多数实在数据会集的已排序元素，这些已排序的元素被称为“natural runs”。算法会遍历要排序的数据，将元素收集到 run 中，一起将这些 run 兼并在一起。

元素个数少于 64 的数组

假如数组的元素个数少于 64，Timsort 将履行刺进排序。

刺进排序是一种对小数据集最为有用的排序算法。它在排序较大的数据集时速度很慢，但在排序较小的数据集时速度很快。刺进排序的思维如下：

逐一检查元素；

在正确的方位刺进正确的元素，以此来构建排好序的列表。

在这个示例中，咱们将新排序的元素刺进到一个新的子数组中，从数组的头部开端。

刺进排序的 GIF 动画演示：

关于 run

假如列表的元素个数大于 64，Timsort 会先遍历列表，查找严厉递加或递减的部分。假如这个部分是递减的，就回转这个部分。

所以，假如 run 是递减的，它看起来像这样（其间 run 运用粗体表明）:

假如不是递减的，它看起来是这样的：

minrun 依据数组的巨细来确认。当 run 的数量等于或略小于 2 的幂时，兼并 2 个数组的功率会更高。为了保证功率，Timsort 挑选的 minrun 一般等于或小于 2 的幂。

minrun 的取值规模为 32 到 64。原始数组的长度除以 minrun 依然等于或略小于 2 的幂。

假如 run 的长度小于 minrun，就用 minrun 减去这个 run 的长度，得出一个数字，然后针对这个数字长度的元素履行刺进排序，以此来创立新的 run。

所以，假如 minrun 是 63，run 的长度是 33，那么便是 63-33=30，也便是对 run[33] 前的 30 个元素履行刺进排序来创立新的 run。

在这部分完结之后，咱们就有了一系列排好序的 run。

兼并

接下来，Timsort 会履行归并排序，将 run 兼并在一起。Timsort 在履行兼并排序时会保证安稳性和均衡性。

为了保证安稳性，咱们不需求交流两个持平的数字。这样不只可以坚持它们在列表中的原始方位不动，并且会让算法更快。咱们很快就会解说兼并的均衡性问题。

在遇到一个 run 时，Timsort 将它添加到栈中。一个简略的栈看起来像这样：

你可以幻想面前有一叠盘子，但你不能从底部拿盘子，有必要从顶部拿。栈也是这个原理。

Timsort 在兼并 run 时会测验平衡两个彼此对立的需求。一方面，咱们期望尽可能多地推延兼并，以便找出可能会呈现的形式，但也更期望尽快地进行兼并，以便运用刚刚发现的 run。但咱们不能推迟兼并“太久”，由于咱们需求记住未兼并的 run，而这样做会耗费更多的内存。

为了取得这种平衡，Timsort 会盯梢栈上最新的三个项，这些项有必要遵从以下规矩：

A > B + C

B > C

其间 A、B 和 C 是栈上最新的三个项。

一般，兼并不同长度的相邻的 run 是很困难的，而更困难的是咱们有必要保证安稳性。为了处理这个问题，Timsort 会留出暂时内存，将较小的 run 放到暂时内存中。

“奔跑”形式

Timsort 在兼并 run A 和 run B 时会发现其间一个 run 接连屡次“取胜”。假如 run A 的数字都比 run B 的数字小，那么 run A 的数字最后会待在本来的方位上。兼并这两个 run 需求做很多的作业，但并没有发生任何成果。

排序的数据一般会有一些预先存在的内部结构。Timsort 假定假如 run A 的多个值小于 run B 的值，那么很可能 A 的值都小于 B 的值。

在示例中，run A 和 run B 有必要严厉递加或递减。

Timsort 将进入奔跑（gallop）形式。Timsort 不检查 A[0] 和 B[0] 之间的彼此关系，而是进行二分查找，以便找出 B[0] 在 A[0] 中的方位。这样，Timsort 就可以将 A 的整个部分移动到适宜的方位。然后，Timsort 在 B 中查找 A[0] 的方位，再将 B 的整个部分移动到恰当的方位。

让咱们来看看它是怎么运转的。Timsort 检查 B[0]（即 5），并运用二分查找找出它在 A 中的方位。

可以看到，B[0] 在 A 的尾部。然后，Timsort 检查 A[0]（即 1）在 B 中的方位。可以看到，数字 1 在 B 的最初。咱们现在知道 B 在 A 的尾部，A 在 B 的最初。

事实证明，假如 B[0] 的方位十分挨近 A 的最初，那这么做就不值得，反之亦然。假如是这种状况，它就会快速退出奔跑形式。此外，Timsort 会把这个记下来，并经过添加接连 A 或接连 B 的数量来进步进入奔跑形式的门槛。假如进入奔跑形式是值得的，Timsort 会让从头进入奔跑形式变得简单些。

总的来说，Timsort 有两个方面做得十分好：

对存在内部结构的数组排序有十分好的功能

可以坚持安稳的排序

在曾经，为了完成安稳的排序，有必要将列表中的项映射成整数，并将其作为元组数组进行排序。

代码

假如你对代码不感兴趣，请越过这一部分。

Timsort 的原始源代码：

https://github.com/python/cpython/blob/master/Objects/listobject.c 。

Python 现已内置了 Timsort 算法，要运用 Timsort，只需这样写：