Hexo

点滴积累 豁达处之

0%

TimeSort 排序

Posted on Edited on In
JavaCore

Timsort是结合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在现实中有很好的效率,现在Java SE7和Android也采用Timsort算法对数组排序。

1 TimeSort核心算法

TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退，将输入按其升序和降序特点进行了分区。排序的输入的单位不是一个个单独的数字，而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列，每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run，这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。

综上述过程，Timsort算法的过程包括

  • 如果数组长度小于某个值，直接用二分插入排序算法
  • 找到各个run，并入栈
  • 按规则合并run

2 run 分析

1 run的最小长度

现实中的大多数据通常是有部分已经排好序的，Timsort利用了这一特点。Timsort排序的输入的单位不是一个个单独的数字，而是一个个的分区。其中每一个分区叫一个“run“（图1）。针对这个 run 序列，每次拿一个 run 出来进行归并。每次归并会将两个 run 合并成一个 run。

JavaCore_timeSort01

2 优化run的长度

优化run的长度是指当run的长度小于minrun时，为了使这样的run的长度达到minrun的长度，会从数组中选择合适的元素插入run中。这样做使大部分的run的长度达到均衡，有助于后面run的合并操作。

3 合并run

合并run的原则是 run合并的技术要保证有最高的效率。当Timsort算法找到一个run时，会将该run在数组中的起始位置和run的长度放入栈中，然后根据先前放入栈中的run决定是否该合并run。Timsort不会合并在栈中不连续的run

Timsort会合并在栈中2个连续的run。X、Y、Z代表栈最上方的3个run的长度（图2），当同时不满足下面2个条件是，X、Y这两个run会被合并，直到同时满足下面2个条件，则合并结束：

(1) X>Y+Z

(2) Y>Z

例如：如果X<Y+Z，那么X+Y合并为一个新的run，然后入栈。重复上述步骤，直到同时满足上述2个条件。当合并结束后，Timsort会继续找下一run，然后找到以后入栈，重复上述步骤，及每次run入栈都会检查是否需要合并2个run。

JavaCore_timeSort02

简单的合并算法是用简单插入算法，依次从左到右或从右到左比较，然后合并2个run。为了提高效率，Timsort用二分插入算法（binary merge sort）。先用二分查找算法/折半查找算法（binary search）找到插入的位置，然后在插入。

例如，我们要将A和B这2个run 合并，且A是较小的run。因为A和B已经分别是排好序的，二分查找会找到B的第一个元素在A中何处插入（图4）。同样，A的最后一个元素找到在B的何处插入，找到以后，B在这个元素之后的元素就不需要比较了（图5）。这种查找可能在随机数中效率不会很高，但是在其他情况下有很高的效率。

JavaCore_timeSort03

3 性能

JSE 7对对象进行排序，没有采用快速排序，是因为快速排序是不稳定的，而Timsort是稳定的。

大体是说，Timsort是稳定的算法，当待排序的数组中已经有排序好的数，它的时间复杂度会小于n logn。与其他合并排序一样，Timesrot是稳定的排序算法，最坏时间复杂度是O（n log n）。在最坏情况下，Timsort算法需要的临时空间是n/2，在最好情况下，它只需要一个很小的临时存储空间

4 记排序引发的异常

1 代码片段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public static void main(String[] args) {
        List<String> list = initList2();
        list = sortImportErrorList1(list);
        list.stream().forEach(item -> System.out.println(item));
    }

    public static List<String> sortImportErrorList1(List<String> error) {
        return  error.stream().sorted((item1, item2) -> {
            if(item1.length() > 10 && 0 == item1.indexOf("凭证编号") &&
                    item2.length() > 10 && 0 == item2.indexOf("凭证编号")){
                int item1End = item1.indexOf("号",4);
                int item2End = item2.indexOf("号",4);
                if(item1End > 0 && item2End > 0){
                    if(Integer.valueOf(item2.substring(4, item2End)) > Integer.valueOf(item1.substring(4, item1End))  ){
                        return -1;
                    }
                    if(Integer.valueOf(item2.substring(4, item2End)) == Integer.valueOf(item1.substring(4, item1End))  ){
                        return 0;
                    }
                    if(Integer.valueOf(item2.substring(4, item2End)) < Integer.valueOf(item1.substring(4, item1End))  ){
                        return 1;
                    }
                }
            }
            return 0;
        }).collect(Collectors.toList());
    }

public static List<String>  initList2(){
        List<String> list = new ArrayList<>();
        list.add("凭证编号1号qqqqqqqqq");list.add("凭证编号1号qqqqqqqqqqqq");
        list.add("凭证编号2号qqqqqqqqqq"); list.add("凭证编号2号qqqqqqqqq");
        list.add("凭证编号2号qqqqqqqqq"); list.add("凭证编号3号qqqqqqqqqq");
        list.add("凭证编号3号qqqqqqqqq"); list.add("凭证编号3号qqqqqqqqqqqq");
        list.add("凭证编号4号qqqqqqqqqq"); list.add("凭证编号4号qqqqqqqqq");
        list.add("凭证编号4号qqqqqqqqq"); list.add("凭证编号5qqqqqqqqqq");
        list.add("凭证编号5qqqqqqqqq");  list.add("凭证编号5qqqqqqqqqqqq");
        list.add("凭证编号6号qqqqqqqqqq");  list.add("凭证编号6号qqqqqqqqq");
        list.add("凭证编号6号qqqqqqqqq");  list.add("凭证编号7号qqqqqqqqqq");
        list.add("凭证编号7号qqqqqqqqq");  list.add("凭证编号7号qqqqqqqqqqqq");
        list.add("凭证编号8号"); list.add("凭证编号3号"); list.add("凭证编号2号");
        list.add("凭证编号2号");  list.add("凭证编号2号");  list.add("凭证编号8号");
        list.add("凭证编号8号qqqqqqqqq");  list.add("凭证编号9号"); list.add("凭证编号9号");
        list.add("凭证编号9号");  list.add("凭证编号3号"); list.add("凭证编号2号");
        list.add("凭证编号2号"); list.add("凭证编号2号");
    	list.add("凭证编号10号qqqqqqqqqq");  list.add("凭证编号10号qqqqqqqqqq");
        list.add("凭证编号10号qqqqqqqqqq");  list.add("凭证编号11号qqqqqqqqqqqq");
        list.add("凭证编号11号qqqqqqqqqqqq");  list.add("凭证编号11号qqqqqqqqqqqq");
        list.add("凭证编号10号qqqqqqqqqq"); list.add("凭证编号10号qqqqqqqqqq");
        list.add("凭证编号10号qqqqqqqqqq"); list.add("凭证编号9号qqqqqqqqqq");
        list.add("凭证编号9号"); list.add("凭证编号9号");
        list.add("凭证编号8号qqqqqqqqqq"); list.add("凭证编号3号");
        list.add("凭证编号2号"); list.add("凭证编号2号");  list.add("凭证编号2号");
        list.add("凭证编号8号"); list.add("凭证编号8号");
        list.add("凭证编号7号");  list.add("凭证编号7号qqqqqqqqq");
        list.add("凭证编号7号qqqqqqqqqqqq");  list.add("凭证编号1号qqqqqqqqq");
        list.add("凭证编号6号qqqqqqqqqq"); list.add("凭证编号6号qqqqqqqqq");
        list.add("凭证编号6号qqqqqqqqq");  list.add("凭证编号5号qqqqqqqqqq");
        list.add("凭证编号5号qqqqqqqqq");   list.add("凭证编号5号qqqqqqqqqqqq");
        list.add("凭证编号4qqqqqqqqqq");   list.add("凭证编号4qqqqqqqqq");
        list.add("凭证编号4qqqqqqqqq");   list.add("凭证编号3号qqqqqqqqqq");
        list.add("凭证编号3号qqqqqqqqq"); list.add("凭证编号3号");
        list.add("凭证编号2号"); list.add("凭证编号2号"); list.add("凭证编号2号");
        list.add("凭证编号1号qqqqqqqqqqqq");  list.add("凭证编号1号qqqqqqqqqqqq");
        list.add("凭证编号1号qqqqqqqqqqqq");
        return list;
    }

2 报错内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.util.TimSort.mergeHi(TimSort.java:899)
	at java.util.TimSort.mergeAt(TimSort.java:516)
	at java.util.TimSort.mergeForceCollapse(TimSort.java:457)
	at java.util.TimSort.sort(TimSort.java:254)
	at java.util.Arrays.sort(Arrays.java:1512)
	at java.util.stream.SortedOps$SizedRefSortingSink.end(SortedOps.java:348)
	at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:482)
	at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471)
	at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708)
	at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
	at java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:499)
	at TestTimeSort.sortImportErrorList1(TestTimeSort.java:43)
	at TestTimeSort.main(TestTimeSort.java:16)

3 解决方法

sort排序中重写的方法一定要满足:可逆比较。

4 bug引发详情

TimeSort函数中的归并操作

JavaCore_timeSort04

合并方法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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);
    
 		......
 
        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);
        }
    }

这段代码合并代码步骤

  • 分配临时片段，用于合并
  • 计数count整段合并

注：这里当len1=0抛出异常：Comparison method violates its general contract!，这是在整段合并时，识别到run1有片段应该合并到run2起始位置；但是在合并之前有过判断run1中小于run2第一个元素的片段已经不在合并范围内了，那么合并的run1不可能有片段还在run2的起始值之前（可以看合并的图示更好理解）。所以大家在重写compare方法时需要考虑周全。

java sort排序源码分析