对于编程算法，很多读者可能是在学校最先了解冒泡排序，但是你真的了解Python内置排序算法list.sort()的原理吗？它使用一种快速、稳定的排序算法Timsort，时间复杂度为O(nlogn)，该算法的目标是处理大规模的真实数据。Timsort是一种对真实数据非常高效的排序算法。TimPeters于2001年为Python编程语言创建了Timsort。Timsort首先分析它正在排序的列表，然后根据该分析选择合理的解决方案。自发明以来，Timsort一直是Python、Java、Android平台和GNUOctave的默认排序算法。来源：http://bigocheatsheet.com/Timsort的排序时间与Mergesort相似，并且比大多数其他排序算法更快。Timsort其实借鉴了插入排序和归并排序的方法，其具体过程后面会详细介绍。Peters设计Timsort是为了利用现实世界数据集中存在的大量有序元素，称为“自然运行”。总而言之，Timsort会先遍历所有数据，找到数据中排序好的分区，每个分区可以称为一个run，最后将这些run按照规则合并为一个。少于64个元素的数组如果排序后的数组少于64个元素，Timsort将执行插入排序。插入排序是对小列表最有效的简单排序，它在大列表上慢，但在小列表上快。插入排序的思路是这样的：一个一个的看元素通过在正确的位置插入元素来构建一个排序的列表在例子中，我们将从左到右开始排序，其中粗体数字表示新排序的子数组。在对原始数组的每个元素进行排序时，它将排序后的子数组从右到左进行比较，并将它们插入到适当的位置。用动画来说明插入排序：自然有序块：run如果列表大于64个元素，Timsort算法首先遍历列表找到“严格”的升序或降序部分（Run）。如果一个分数递减，Timsort将反转该分数。因此，如果run递减，它看起来像这样（run以粗体显示）：如果没有，它看起来像这样：minrun的大小根据数组大小而定。Timsort算法选择它，以便随机数组中的大部分运行成为minruns。当run的长度N等于或略小于2的倍数时，合并2个数组效率更高。Timsort选择minruns以确保minruns等于或略小于2的倍数。该算法选择的minrun范围为32~64。除以minrun时，使原数组的长度等于或略小于2的倍数。如果run长度小于minrun，计算minrun减去run长度。我们可以把run(minrun-run)以外的新元素放在run后面，进行插入排序，创建一个新的run，其长度与minrun相同。如果minrun为63，run的长度为33，则可以获取63-33=30个新元素。然后这30个新元素作为新元素放在run的最后，所以run的第34个元素run[33]有30个子元素。***只需对接下来的30个元素执行插入排序即可创建长度为63的新运行。完成此部分后，您现在应该在列表中具有一系列已排序的运行。MergeTimsort现在需要进行mergesort来mergeruns，需要保证mergesort时的稳定性和平衡性。为了稳定，两个等值的元素不应该交换，这样不仅可以保持它们在列表中的原始位置，而且可以使算法更快。当Timsort搜索运行时，它们被添加到堆栈中。一个简单的堆栈看起来像这样：想象一堆盘子。你不能从底部拿一个盘子，你必须从顶部拿它，堆叠也是如此。Timsort在合并不同的运行时试图平衡两个相互冲突的要求。一方面，我们希望尽可能延迟合并，以便利用以后可能出现的模式。但我们更愿意尽快合并，以利用我们刚刚发现的仍然在内存层次结构中较高的运行。我们也不能延迟合并“太多”，因为它会记住未合并的运行会消耗内存，而堆栈的大小是固定的。为了达成妥协，Timsort跟踪堆栈中最接近的三个项目，并为这些堆栈项目创建两个必须保持为真的规则：A>B+CB>C，其中A、B和C是最接近的三个项目在堆栈上。项目。用TimPeters自己的话来说：一个好的折衷方案是在堆栈条目上维护两个不变量，其中A、B和C是三个最右边未合并片段的长度。通常，很难将不同长度的相邻游程合并在一起。更难的是需要保持稳定。为了解决这个问题，Timsort设置了临时内存。它将两个运行中较小的一个（同时调用runA和runB）放在这个临时内存中。GALLOPING（飞行模式）当Timsort合并A和B时，它注意到一次运行连续多次“获胜”。如果运行A的值完全小于运行B，则运行A将返回其原始位置。合并这两个运行将需要大量工作，并且不会取得任何成果。通常，数据会有一些预设的内部结构。Timsort假设如果runA中的值大部分低于runB中的值，那么A中的值很可能小于B中的值。Timsort随后将进入gallop模式。Timsort不是检查A[0]和B[0]，而是二进制搜索B[0]在A[0]中的合理位置。这样，Timsort就可以将A的整个部分移动到位。Timsort然后在B中搜索A[0]的适当位置。然后Timsort会立即将整个B移动到位。Timsort检查B[0]（值为5）并使用二进制搜索找到它在A中的正确位置。现在B[0]在A列表的末尾，Timsort检查是否有A[0]（这是B的正确位置上的1)，因此我们正在查看1的位置。这个数字在B的前面，现在我们知道B在A的后面，A在B的前面。如果B[0]的位置非常靠近A的前面（反之亦然），那么这个操作就不需要了.Timsort也会注意到这一点，并通过增加连续A或B的数量来提高奔跑模式的门槛。如果有意义，Timsort可以更轻松地重新进入疾驰模式。简而言之，Timsort做了两件非常好的事情：具有预设内部结构的数组具有良好的性能能够保持稳定排序在此之前，为了实现稳定排序，列表中的项目必须被压缩为整数，并且将其排序为元组数组。代码下方的源代码是基于我与NandaJavarma的合作。源代码不完整，也不类似于Python的官方sort()源代码。这只是我实现的一个简化的Timsort，可以对Timsort有一个整体的把握。此外，Python中内置的Timsort算法正式用C实现，因此您可以获得更好的性能。Timsort原始源码：https://github.com/python/cpython/blob/master/Objects/listobject.c。#basedoffofthiscodehttps://gist.github.com/nandajavarma/a3a6b62f34e74ec4c31674934327bbd3#BrandonSkerritt#https://skerritt.techdefbinary_search(the_array,item,start,end):ifstart==end:ifthe_array[start]>item:returnstartelse:returnstart+1ifstart>end:returnstartmid=round((start+end)/2)ifthe_array[mid]
