技术分享:这可能最快的稳定排序算法

知道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会跟踪栈上最新的三个项，这些项必须遵循以下规则：

1. A > B + C
2. 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有两个方面做得非常好：

• 对存在内部结构的数组排序有非常好的性能
• 能够保持稳定的排序

在以前，为了实现稳定的排序，必须将列表中的项映射成整数，并将其作为元组数组进行排序。

代码

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

代码并不完整，与Python中的sorted()也不一样。这只是一个简化版的Timsort，我主要用它来演示Timsort算法。如果你想查看Timsort的原始源代码，请点击
https://github.com/python/cpython/blob/master/Objects/listobject.c。Timsort算法的正式版本是用C语言实现的，而不是Python。

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

list.sort()

或者：

sorted(list)

如果你想掌握Timsort算法，我强烈建议你自己试着实现它！

原文：
https://skerritt.blog/timsort-the-fastest-sorting-algorithm-youve-never-heard-of/