Java里的人名算法-Timsort

Java圈里, 最讲究看源码.

源码这东西呢, 比如老生常谈的HashMap,动辄接口套接口,不够简洁. public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable, 看声明,都觉得一口气差点上不来.

然而,Java里也是有简洁,独立性比较强的代码的. 比如,List会用到的sort方法.就是用一个没有任何import,一共942行(含注释)的排序算法实现. 人称TimSort(java.uti.TimSort).

此类非public, 不可以直接使用,但自从引入java以来,已经基本上接管了当今所有需要列表排序的地方.

Arrays里的几个sort, 用的全都是TimSort.
List里面的默认sort,用的是Arrays.sort.
Collections里的sort,用的是List.sort.

这个TimSort已经是java里排序的事实标准, 最强王者了.

那, 我们平常听说的,都是什么冒泡,基排,快排,归并. 还有什么说法,基于比较的排序方法,下界都不可能会超过O(nlogn). 还有信息论证明. 这个TimSort有那么优秀么,他的下界是多少,上界又是多少?会比快排更快吗?

我们拿快排和TimSort做对比.

	timsort	quicksort
best	O(n)	O(nlog(n))
worse	O(nlog(n))	O(n^2)
avg	O(nlog(n))	O(nlog(n))

这个差异, 其实来自于代差.就像是西班牙vs阿兹特克.

快排是来自Tony Hoare1959年的发明.而,TimSort用到的技术来自1993年.第一次实现出来这个算法,让他大规模流行的,是2002年的Tim Peters 因此这个算法,也得名TimSort.

这是一个混合算法(hybrid sorting algorithm). 由归并 merge sort和插入 insert sort 派生而来. 博采众长, 身兼多家优点.

对输入内容的有序程度比较敏感. 会根据内容有序程度来进行优化. 这种特性,有时候也会称为,自适应.(扩展一下, MySQL在执行过程中, 针对B+树索引的热点,会自动建立Hash来加快查询.这种自tuning特性, 就是背称为自适应哈希索引.)

2002年, tim本人的版本是C. 提供了一个说明文件listsort.txt 能看的赶紧看,就不用看我瞎说了,下面是乱分析源码的部分.

算法相对于普通的排序,多了一部分内容,检测原始输入的有序程度.合理利用输入的有序部分来加快速度.

对于这样一个输入而言,他是基本有序的.
1,2,3,5,4,6,7,8,9

子序列1,2,3,5, 4,6,7,8,9都是有序的序列. 在这里有一个术语,叫做run,取run的名词意思 a series of sth,a run of sth.可以是一个非递减或者递减序列.(之所以不用递增和递减,是因为=的情况会影响排序稳定性)

算法基本原理就是循环下面过程

找到一个run,入栈
再找一个run, 入栈
合并栈内的run.

当所有数组已经检测完了,强制合并栈内的run.

听起来,非常简单.恭喜你, 已经会了TimSort算法了.

好吧,这只是概念性描述.然而实现起来非常有难度, 甚至还曾经在jdk里引入了一个bug. 那是另一个故事,这里就不讲了.

去掉注释以后,算法源码只有530行. 而且, 里面还包含了一个自己实现的辅助工具.

二分查找
插入排序
归并排序

去掉这三部分, 主体部分就这么多,还没我前面的废话长.

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                         T[] work, int workBase, int workLen) {
        int nRemaining  = hi - lo;
    /** 这几行,是作的边缘case处理,待排序队列太短的话不值得merge.可以先跳过.
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
            binarySort(a, lo, hi, lo + initRunLen, c);
            return;
        }
    **/
        TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
    // 这部分是计算run的最小值的,如果不限制这个, 退化太厉害.
        int minRun = minRunLength(nRemaining);
        do {
        /** 开始检测了, 要是没找到足够多的值,会尝试用插入排序扩充一点.
            int runLen = countRunAndMakeAscending(a, lo, hi, c);

            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen, c);
                runLen = force;
            }
        */
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();

            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);

        ts.mergeForceCollapse();
    }

上面的部分都是简单的部分,实现起来细节重重.因为我还没能真正掌握住,所以,这次写到这.

参考资料