前言
我们在上篇文章 排序算法(五)-双调排序 介绍了双调排序,今天我们来看一下另一种排序算法 —— TimSort。
TimSort是Tim Peters发明的一种混合排序,最早是Python语言的内置排序算法。
关于Python内置的TimSort描述可以查看该 文档。
关于TimSort的理论基础,可以查看该篇论文 Optimistic Sorting and Information Theoretic Complexity,这篇论文论证了插入排序和归并排序合并后效率提高的可能性,即TimSort的理论基础。
Java自Java 7 后加入TimSort,其实现参考了Python版本的实现,我们可以在JDK源码的util包下找到它,java.util.TimSort
,这个class不是public的,我们无法直接调用,只能够通过Java提供的sort方法等间接调用它。
为什么引入了TimSort呢?我们慢慢来看下吧。
正文
TimSort的排序原理
说到排序算法,我们就先来了解下排序算法的基本原理,这样有助于我们更快理解算法本身。
TimSort作为一种混合排序算法,其内部使用了插入排序(准确的说是二分插入排序)和归并排序。
根据我们之前说到的,归并排序是一种时间复杂度很平均(O(n * log n) 排序算法,其缺点一个是如果两个序列长度相差较大(一个长序列和一个短序列归并),排序效率无法体现;另一个是当数组长度很小时,归并的效率也不是很高且浪费空间。
对于插入排序,虽然时间复杂度为(O(n^2)),但是较小数据量下,其表现也不错,在一部分数据已经排序的情况下,其表现要更好,而使用插入排序的变种二分插入排序,虽不能减少移动次数,但减少了比较次数。
说到这里,我们再说TimSort基于的一个简单事实:数组中的数据都是部分有序(升序或降序)的。
什么意思呢? 比如 数组[9,8,5,7,3,9,1,3,4,6,0,5,3],可以看到里面部分数据[9,8,5],[1,3,4,6]等等有序。
这对插入排序是十分友好的。
Timsort排序算法可以概括成如下几步:
- 把待排数组划分成一个个run,当然run不能太短,长度最小阈值为minRun;
- run的划分规则:从数组最小下标low开始,寻找连续有序部分(连续逆序也算,寻找的时候会把这段顺序反过来),如果这段有序部分长度小于minRun,就用二分插入排序补充到minRun;
将run入栈,当栈顶的run的长度不满足下列约束条件中任意一个时,
1
2runLen[n-1] > runLen[n] + runLen[n+1]
runLen[n] > runLen[n+1]则利用归并排序将其中最短的2个run合并成一个新run;
- 最后会有一次强制合并合并所有栈内剩余所有run,最终栈空,生成有序数组。
TimSort算法的原理可以用下图大致表示:
这儿我们设minRun = 4.
如上图可以清晰的看到TimSort的排序过程。
TimSort源码分析
下面我们来分析下TimSort的源码。
它的主要入口为sort方法,sort方法参数说明如下:
T[] a : 表示待排序数组;
int lo:排序的起始位置,如果排整个数组传0即可;
int hi:排序的终止位置,排整个数组传数组长度n即可;
Comparator<? super T> c:数据的比较规则;
T[] work: 合并所需的临时存储空间设置,一般不需要我们设置,会有默认值,传null即可;
int workBase :合并所需的临时存储空间分片基数值,一般不需要我们设置,会有默认值,传0即可;
int workLen:合并所需的临时存储空间默认长度,一般不需要我们设置,会有默认值,传0即可。
可以看到传入的排序位置lo和hi,如果长度小于2,直接返回,如果小于32,就做mini-TimSort,迷你TimSort就相当于上面图中说的部分有序的二分插入排序。
再来看下下面部分。
TimSort先计算出该数组的minRun,然后开始处理数据,拿到有序长度,判断是否小于minRun,小于的话就用插入排序补齐,然后入栈,看看是否需要进行归并排序,移动位置到下一个run,重复上述过程,最后在进行一次归并排序,得到有序数据。
二分插入排序法的源码如下:
1 | private static <T> void binarySort(T[] a, int lo, int hi, int start,Comparator<? super T> c) { |
计算有序部分长度(如果逆序有序就把数据处理成正序)的源码如下:
1 | private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,Comparator<? super T> c) { |
获取该数组的minRun的相关代码如下:
1 | private static int minRunLength(int n) { |
可以看到如果入参n小于MIN_MERGE(32)时,会直接返回n,因为太小了;如果n恰好是2的幂,则返回MIN_MERGE/2;否则返回一个int k, MIN_MERGE/2 <= k <= MIN_MERGE,使n/k接近但小于2的幂次值。
关于这样设计的基本原理,可以查看Tim在Python上关于它的描述文档 listsort.txt。
检测并合并不符合条件的栈元素的相关代码如下:
1 | private void mergeCollapse() { |
我们可以看到它的合并条件,如上面提到的。
关于它的合并方法mergeAt
,内容较多,在这儿就不展示了。
最后强制合并栈元素的代码如下:
1 | private void mergeForceCollapse() { |
该方法最终会将栈内元素合并为1个,即run[0],即有序数组。
初始化栈空间及归并缓存空间代码如下:
1 | private TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen) { |
Java版本TimSort曾经的Bug
在JDK1.7时候,TimSort曾经有一个bug,会引发数组下标越界异常。
PS:这个Bug已经被fix了。
bug详情可参考如下链接 JDK-8011944 : Sort fails with ArrayIndexOutOfBoundsException。
关于这篇bug的发现验证解决可参考这篇pdf,OpenJDK’s java.utils.Collection.sort() is broken:The good, the bad and the worst case?。
我们这儿简单说下这个bug吧。
上面我们看到TimSort栈内元素合并的条件,它的目的在于尽量保证两个要进行归并排序的数组长度大致相同。
所以栈内所有run应该满足如下条件:
1 | 2 <= i <= StackSize-1 |
我们看mergeCollapse
方法也能验证这一点。
大多数情况下我们检查栈顶的3个元素就能满足约束条件,但是一些特殊情况下就不行了,比如下面的这个栈:
1 | 120, 80, 25, 20, 30 |
根据源码,因为25 < 20 + 30,25 < 30,所以将25和20两个run进行合并,此时栈内的情况变为
1 | 120, 80, 45, 30 |
由于80 > 45 + 30,45 > 30,满足约束条件,此时归并就终止了。但是注意栈里的其他run,120 < 80 + 45,这是不满足约束条件的,而由于我们只判断了栈顶的run,因此在这里就留下了“隐患”。
大多数情况下,这并不是什么问题,因为TimSort最终可以通过最后的强制归并将数据排序合并。
但是Bug发现者构造了一个非常精致的Array,成功的让Timsort算法抛出java.lang.ArrayIndexOutOfBoundsException,代码如下:
1 | public class BreakTimSort { |
PS:这段代码我们现在测试是没有问题的,因为这个bug已经被Fix了,如果想复现这个bug,可以下载 JDK - 1.7.0_07 版本。
这个bug出现的原因是TimSort初始化时会申请栈空间,如下:
1 | int stackLen = (len < 120 ? 5 : |
在JDK - 1.7.0_07版本它是这样的:
1 | int stackLen = (len < 120 ? 5 : |
可以看到有几个数字不一样,是的,不要小看这几个“魔法”数字。
这几个数字怎么来呢? 我们栈归并的条件上面有提到,它其实就是函数 F(n) < F(n-1) + F(n-2) +1,我们设F(n) = F(n-1) + F(n-2) +1,这个函数是不是很熟悉,在 SmoothSort里我们有提到过,不过我们这里的起始是0,第一个元素是minRun。
我们设minRun为16(上面的minRunLength
方法,可以看到minRun最小值为MIN_MERGE/2 = 16),如下程序:
PS:minRun越小,数组长度固定的情况下,分的份数就越多,理论需要的栈数量也越多。栈数量要多,少的话可能出现数组下标越界问题。
1 | private static void getNum(){ |
如下输出:
1 | 5--->119 |
当为40的时候已经超出了int最大值。
上述数据是在理想情况下,即 F(n) = F(n-1) + F(n-2) +1,但是实际上会有不满足的情况,这时候需要的栈大小就应该大一些,因而就出现了我们上述所说的异常。
关于实际需要的栈大小,上面PDF中给出了,可以直接查看,如下:
array size | 64 | 128 | 160 | 65536 | 131072 | 67108864 | 1073741824 |
---|---|---|---|---|---|---|---|
required stack size | 3 | 4 | 5 | 21 | 23 | 41 | 49 |
runLen.length | 5 | 10 | 10 | 19 (24) | 40 | 40 | 40 |
可以看到JDK1.8中长度已经变为了5,10,24,49,相当于修复了这个bug。
上述PDF中还给出了一种出现无法合并的栈的情况的解决方法:
1 | private void mergeCollapse() { |
相当于增加了 n-1 > 0 && runLen[n-2] <= runLen[n] + runLen[n-1]
这部分,把栈顶的第4个元素也加入了判断。
但是Java社区JDK1.8中并未采用这段代码,还是原来的3层栈元素判断,只是变更了栈的长度作为解决办法,原因不详。
以上就是TimSort曾经出现的bug。
测试TimSort
我们将TimSort源码中的泛型去掉,排序数组改为int[],测试下TimSort的性能。
1 | public class TimSort { |
有如下结果,排序1亿数据耗时在17s左右。
1 | TimSort排序开始: |
TimSort的时间复杂度如下:
- 时间复杂度(最好):O(n)
- 时间复杂度(平均):O(n * log n)
- 时间复杂度(最差):O(n * log n)
TimSort的空间复杂度:O(n)
TimSort是一种稳定排序算法。
TimSort之所以能成为Java的内置排序算法之一,除了其优秀的性能,另一点就在于它的稳定性了。
我们可以对大量随机数据进行测试,虽然TimSort和快排(或者其变种)具有相同的时间复杂度【平均 O(n * log n)】,但实际数据显示快排还是要快一些的。
但是快排的缺点是它的不稳定性,比如100个人按名字进行排序,有两个叫张三的,张三(1)无序下是在张三(2)之前的,快排完后可能他们的顺序就变化了,这在某些情况下可能会有问题。
我们来看下TimSort排序动图:
图中可以清晰的看到TimSort的排序过程。
其他
在util包下除了TimSort,我们还可以看到一个类 ComparableTimSort,它是针对未实现 Comparator 接口的数据的排序版本,如Object[]。
我们对于一个int[] a,调用数组的 Arrays.sort(a)
,会使用TimSort吗?
答案是否定的,对于一些基本数据类型数组,两个相同的数的前后顺序不会造成任何影响,所以Arrays.sort(a)
里使用了另一种更快速的排序算法DualPivotQuicksort。
我们有时间再看一下DualPivotQuicksort这个排序。
总结
本篇文章通过对TimSort的分析,了解了TimSort的工作运行原理,对Java内置的排序算法有了更深的了解。
后面我们将看下Java的sort接口实现,看看Java内部是如何进一步优化排序,提高效率的。
参考
- JDK1.8
java.util.TimSort
、java.util.ComparableTimSort
源码 - JDK1.7
java.util.TimSort
源码 - Python TimSort listsort.txt
- OpenJDK’s java.utils.Collection.sort() is broken:The good, the bad and the worst case?
源码地址
上述文中涉及到的代码可见于我的 GitHub