Timsort排序算法

Java-Base 数据结构与算法

算法实现原理

TimSort原理：现实数据通常会有部分是已经排好序，TimSort正是利用这一点，将数组拆成多个部分已排序的分区，部分未排序分区重新排序，最后将多个分区合并并排序。

例如：array[] = [24,63,70,55,41,92,81,80]，排序步骤如下：
1. 拆分分区：[24,63], [70,55], [41,92], [81,80]
2. 重排分区：[24,63], [55,70], [41,92], [80,81]
3. 合并分区：[24,63,55,70], [41,92,80,81]
4. 重排分区：[24,55,63,70], [41,80,81,92]
5. 合并分区：[24,55,63,70,41,80,81,92]
6. 重排：[24,41,55,63,70,80,81,92]

Java Timsort实现原理

JDK1.8以后默认采用Timsort排序，实现如下：

List list = new ArrayList<Integer>();
...
Collections.sort(list, new Comparator<Integer>() {
    public int compare(Integer o1, Integer o2) {
        if (o2 > o1) {
            return 1;
        } else {
            return -1;
        }
    }
});

Java对于Timsort的实现与上述原理有区别。Java版首先会根据数组长度，采用Binarysort（折半插入排序法）对长度小于32（MIN_MERGE）直接进行排序返回结果；However，对于长度大于等于32的数组，先分区，再对单个分区进行采用Binarysort排序，最后合并分区并排序。

要点1：分区方法

假定数据长度为n，
If n < MIN_MERGE(32)，返回n
Else if n 是2的倍数，返回MIN_MERGE(32) / 2 = 16
Else 返回整数k，k取值范围MIN_MERGE(32) / 2 = 16 <= k <= MIN_MERGE(32)

例：
Array Length = 15 ; minRun = 15
Array Length = 50 ; minRun = 25
Array Length = 500 ; minRun = 32

要点2：分区排序方法：二分法插入排序：

1、 二分法插入排序Binarysort要求首先找出数组（此数组即分区）中从0位开始连续升序区块，及区块下一位元素pivot；

例：[1,3,5,7,9,4,8] 的起始连续升序区块是 [1,3,5,7,9]，区块长度为5，即runLen；pivot是4；

2、 通过二分法比较pivot与区分元素的升降序关系，计算pivot在区块中的位置；并插入到该位置，组成新的区块；

例：4在区块中[1,3,5,7,9]，先比较5 > 4，是降序；再比较3 < 4，是升序，确认位置，通过native方法System.arraycopy()插入到区块中；

3、 再计算新区块与新pivot的位置关系，直到完成排序。

4、 注意：以上升序的定义是Comparator.compare(右元素, 左元素) >= 0，反之为降序；非数值上的升降序。

Java Timsort源码分析

    static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                         T[] work, int workBase, int workLen) {
        assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // 长度为0或1数组无需排序
        // 数组长度小于32时，直接采用binarySort排序，无需合并
        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);
        // 获取分区长度
        int minRun = minRunLength(nRemaining);
        do {
            // 计算目标数组指定范围中，连续升序或连续降序的元素组run（最少3个元素），并返回run长度
            int runLen = countRunAndMakeAscending(a, lo, hi, c);
            // 若分区中连续升降序的元素组长度 等于 分区长度，则无需排序；反之binarySort重排
            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen, c);
                runLen = force;
            }
            // Push run onto pending-run stack, and maybe merge
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();
            // Advance to find next run
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);
        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }

获取分区长度--minRunLength()

If n < MIN_MERGE(32)，返回n（数据长度）
Else if n 是2的倍数，返回MIN_MERGE(32)/2=16
Else 返回整数k，k取值范围MIN_MERGE/2(16) <= k <= MIN_MERGE(32)，且such that n/k
is close to, but strictly less than, an exact power of 2.不知如何理解？

    private static int minRunLength(int n) {
        assert n >= 0;
        int r = 0;
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

二分法插入排序--binarySort()

/**
 * 折半插入排序
 * 排序结果为升序，Comparator.compare(右, 左) >= 0
 * 例如：假设目标数组a长度为10，数组头3位已经排好升序，所以
 * lo = 0
 * hi = 9 + 1
 * start = 3 （0 1 2位已排序，从第3位开始计算）
 * @param a 目标数组
 * @param lo 指定排序范围首个元素位置
 * @param hi 指定排序范围最后元素位置 + 1
 * @param start 从start位置开始计算排序，即lo到start部分不排序
 */
private static <T> void binarySort(T[] a, int lo, int hi, int start,
                                       Comparator<? super T> c) {}

详细参考：插入排序分析与Java实现

计算分区中连续升降序元素长度--countRunAndMakeAscending()

计算目标数组指定范围中，连续升序或连续降序的元素组run（最少3个元素），并返回run长度，若连续降序run，则重置其中元素为升序（即a[lo] <= a[lo + 1] <= a[lo + 2] <=...）；
注意：如果run为严格降序，即run中的前一元素大于后一元素（a[lo] > a[lo + 1] > a[lo + 2] > ...），可以元素翻转。严格降序为>，>=不是，如果在 >= 的情况下进行翻转这个算法就不再是stable。

    private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
                                                    Comparator<? super T> c) {
        assert lo < hi;
        int runHi = lo + 1;
        if (runHi == hi)
            return 1;
        // 计算连续升序或降序的最后一位元素位置（runHi），降序则通过`reverseRange()`翻转元素为升序
        // 首先比较第0与第2位
        if (c.compare(a[runHi++], a[lo]) < 0) { // 降序
            // 再从第1与第2位的比较开始，依次比较n与n + 1位，直到比较为非降序
            while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
                runHi++;
            // 翻转数组指定范围的元素，lo：位置，runHi：高位位置，即范围长度
            reverseRange(a, lo, runHi);
        } else {                              // 升序
            // 以上同理
            while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
                runHi++;
        }
        return runHi - lo;
    }

翻转数组指定范围的元素--reverseRange()

lo：起始位置，从0起始
hi：指定范围长度

    private static void reverseRange(Object[] a, int lo, int hi) {
        hi--;
        while (lo < hi) {
            Object t = a[lo];
            a[lo++] = a[hi];
            a[hi--] = t;
        }
    }

合并

    private void mergeLo(int base1, int len1, int base2, int len2) {
        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
        // Copy first run into temp array
        T[] a = this.a; // For performance
        T[] tmp = ensureCapacity(len1);
        int cursor1 = tmpBase; // Indexes into tmp array
        int cursor2 = base2;   // Indexes int a
        int dest = base1;      // Indexes int a
        System.arraycopy(a, base1, tmp, cursor1, len1);
        // Move first element of second run and deal with degenerate cases
        a[dest++] = a[cursor2++];
        if (--len2 == 0) {
            System.arraycopy(tmp, cursor1, a, dest, len1);
            return;
        }
        if (len1 == 1) {
            System.arraycopy(a, cursor2, a, dest, len2);
            a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
            return;
        }
        Comparator<? super T> c = this.c;  // Use local variable for performance
        int minGallop = this.minGallop;    //  "    "       "     "      "
    outer:
        while (true) {
            int count1 = 0; // run1操作次数
            int count2 = 0; // run2操作次数
            /*
             * 【逐一比对】
             * run1（tmp）与run2（a第2段）根据升序逐一比较，当compare()<0时，写入到目标数组a
             * 当连续采用run1或run2的元素次数达到（等于）7次（minGallop），则采用方法
             * 例如：run1 = [1,6,7...] ; run2 = [2,4,8...]
             * 结果：
             * a = [1]
             * a = [1,2]
             * a = [1,2,4]
             * a = [1,2,4,6]
             * ...类推
             */
            do {
                assert len1 > 1 && len2 > 0;
                if (c.compare(a[cursor2], tmp[cursor1]) < 0) {
                    a[dest++] = a[cursor2++];
                    count2++;
                    count1 = 0;
                    if (--len2 == 0)
                        break outer;
                } else {
                    a[dest++] = tmp[cursor1++];
                    count1++;
                    count2 = 0;
                    if (--len1 == 1)
                        break outer;
                }
            } while ((count1 | count2) < minGallop);
            /*
             * One run is winning so consistently that galloping may be a
             * huge win. So try that, and continue galloping until (if ever)
             * neither run appears to be winning consistently anymore.
             */
            do {
                assert len1 > 1 && len2 > 0;
                count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
                if (count1 != 0) {
                    System.arraycopy(tmp, cursor1, a, dest, count1);
                    dest += count1;
                    cursor1 += count1;
                    len1 -= count1;
                    if (len1 <= 1) // len1 == 1 || len1 == 0
                        break outer;
                }
                a[dest++] = a[cursor2++];
                if (--len2 == 0)
                    break outer;
                count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);
                if (count2 != 0) {
                    System.arraycopy(a, cursor2, a, dest, count2);
                    dest += count2;
                    cursor2 += count2;
                    len2 -= count2;
                    if (len2 == 0)
                        break outer;
                }
                a[dest++] = tmp[cursor1++];
                if (--len1 == 1)
                    break outer;
                minGallop--;
            } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
            if (minGallop < 0)
                minGallop = 0;
            minGallop += 2;  // Penalize for leaving gallop mode
        }  // End of "outer" loop
        this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field
        if (len1 == 1) {
            assert len2 > 0;
            System.arraycopy(a, cursor2, a, dest, len2);
            a[dest + len2] = tmp[cursor1]; //  Last elt of run 1 to end of merge
        } else if (len1 == 0) {
            throw new IllegalArgumentException(
                "Comparison method violates its general contract!");
        } else {
            assert len2 == 0;
            assert len1 > 1;
            System.arraycopy(tmp, cursor1, a, dest, len1);
        }
    }