首页 > 代码库 > TimSort排序算法及一个问题分析

TimSort排序算法及一个问题分析

TimSort排序算法及一个问题分析

  • 摘要

  • 排序算法简析

    • 代码入口

    • 排序算法

      • 获取两个有序数组A和B

      • 找到待归并区间

      • 准备操作

      • 归并操作

      • TimSort的优化归并操作

  • 问题解析

    • 问题解析

    • 问题原因

    • 解决方案

  • 参考


摘要

简单介绍了传统归并排序算法,以及Java API提供的TimSort优化后的归并排序算法。

并且分析了代码中出现的一个问题原因与解决方案。

敬请忽略文中的灵魂画风。


 

排序算法简析

代码入口

Collections.sort、List.sort、Arrays.sort方法是逐级调用的关系,最终的底层是Arrays.sort方法,其代码如下(这几个方法的javadoc都蔚然可观,大家不妨看一看):

public static <T> void sort(T[] a, Comparator<? super T> c) {

    if (c == null) {

        sort(a);

    else {

        if (LegacyMergeSort.userRequested)

            legacyMergeSort(a, c);

        else

            TimSort.sort(a, 0, a.length, c, null00);

    }

}

其中的legacyMergeSort(a,c)方法已经被标记废弃;使用的主要是TimSort.sort()方法。这个方法是一个优化版的归并排序。

 

排序算法

这里简单描述一下核心算法,略过一些细节。

这里的描述出自个人理解(看代码和网上搜到的综合理解),可能与实际情况有出入。欢迎指正。

 

获取两个有序数组A和B

传统的归并排序中,A和B都是从“一个元素”开始的;“一个元素”天然有序。TimSort会通过插入排序等方法,先构建一些小的有序数组,以提高一点性能。

另外,在TimSort中,A和B都是入参a[]中的一个片段。这样可以节省一些内存空间。

技术分享

 

 

找到待归并区间

从数组A中,找到A[n-1]<B[0] && A[n]>B[0],以及A[m]<B[length-1] && A[m+1]>B[length-1]。

此时,待归并区间就是A[n,m]和B。

技术分享


准备操作

在正式开始归并之前,会做一些准备操作。包括将非待归并区间的数据移动到合适的位置上;准备一个临时数组、初始化一些指针数据等。如下图。 

数组B被复制到了临时数组temp中。因为数组B的空间会被其他元素覆盖。

原数组A中最后一个元素“12”被放到了原数组B的最后一个位置上。因为这个元素比待归并区间所有元素都更大。

指针B1指向数组A‘的第一个元素;C1指向A‘的最后一个元素;B2指向B‘的第一个元素;C2指向B‘的最后一个元素。这四个指针是用来确定两个数组中待比较和待移动的数据范围的

指针D指向的位置,是下一个“已排序”元素的位置。也就是从A‘和B‘中找到的最大的元素,将会放到这个位置上。

技术分享


归并操作

归并操作相对比较简单。依次比较A‘[C1]和B‘[C2],将较大的数值移动到D的位置上,并将D和对应的C1/C2向左移动一位。重复执行此操作,直到C1<B1或者C2<B2,然后将另一数组中剩下的数据直接写入到数组中即可。

下图是示例数据从准备操作(左上角标记0)到四次排序(左上角标记依次从1到4)的归并步骤。

技术分享


TimSort的优化归并操作

TimSort在某些情况(触发条件待考)下,会对上述归并操作做一个优化。主要的优化点在于:不是一次一个元素的移动,而是尝试着一次移动多个元素。

下图是按优化后的逻辑,同样的示例数据从准备操作(左上角标记0)到完成排序的归并步骤。注意第一步和第二步每次都移动了两个元素。这里只用了5步就完成了归并;而优化前需要7步。

技术分享

 


 

问题解析

问题现象

代码中有一处排序逻辑,代码是这样的:

List<BatchData> batchList = batchs.stream()
    .sorted(new Comparator<BatchData>() {
        @Override
        public int compare(BatchData o1, BatchData o2) {
            if (o1.getClass().getSimpleName()
                .equals(o2.getClass().getSimpleName())) {
                return o1.getId() - o2.getId();
            }
            return o1 instanceof BatchData4Company ? 1 : -1;
        }
    }).collect(Collectors.toList());


这段代码在某些特殊情况下,会引发这个问题:

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)


 

问题原因

问题原因是,对某些数据来说,上述代码会导致compare(a,b)<0并且compare(b,a)<0,也就是a<b && b<a。当这类数据遇到某些特殊情况时,就会发生这个异常。

例如,我们假定:

  1. a<b && b<a,这是代码中出现的bug

  2. 假定输入数组a[] = {5,a,7,12,4,b,8,8},其中待归并的两个有序数组分别是{5,a,7,12}和{4,b,8,8}

  3. 假定b<7&&7>b。这样可以触发“特殊情况”,即:a和b在某一次归并操作后,会同时成为“是否移动元素”的临界条件。

这样,在“特殊情况”下,优化后的归并操作可能陷入死循环。用画图来表示是这样的。

获取两个有序数组A和B

首先,我们有两个有序数组A和B,如下图所示。

技术分享


找到待归并区间、做好准备操作 

这样,在划分完待归并区间后,得到的结果是这样的:

技术分享

 

第一次归并操作:C2落在了元素b上

然后,开始第一次归并操作。由于B‘[C2]>A‘[C1],我们需要从C2开始,在数组B‘中找到一个下标n,使得B‘[n]<A‘[C1]。找到之后,将B‘(n,C2]复制到D的位置上。复制完成后,将C2和D都向左移动若干个位置。

这里需要注意两点:首先,临界点的比较条件是B‘[n]<A‘[C1],这是有顺序的;其次,复制的条件是B‘(n,C2],这是个半包区间。

这样,第一轮归并完成后的结果是这样的:

技术分享

 

第二次归并操作:C1落在了元素a上

接下来做第二次归并操作。由于A‘[C1]>B‘[C2](这是先决条件里的第三点:b<7&&7>b),我们需要从C1开始,从A‘中找到一个下标m,使得A‘[m]<B‘[C2]。找到之后,将A‘(m,C1]复制到D的位置上。复制完成后,将C1和D都向左移动若干个位置。

这里需要注意比较的顺序性和区间半包性。

这一轮操作完,得到的结果是:

技术分享


第三、四步操作:出现空集、死循环

由于此时A‘[C1]<B‘[C2],我们需要重复第一次归并操作。先C2开始,在数组B‘中找到一个下标n,使得B‘[n]<A‘[C1]。但是,由于b<a(注意顺序),这一轮找到的n会等于C2。这就导致了需要复制到D中的元素集合B‘(n,C2]是一个空集——或者用伪代码来说,我们需要将一个长度为0的数组复制到D的位置上去。

然后,由于B‘[C2]<A‘[C1],我们需要重复第二次归并操作。但是很显然,由于a<b(同样注意顺序),我们又会得到一个空集。

 

如果不加干预,排序操作会在这里无限循环下去。TimSort中的干预方式就是当检测到空集时,抛出异常。 

 

解决方案

解决方案其实很简单,确保compare(a,b)操作中,如果a>b,那么b<a即可。

更严格点说,compareTo()或compare()操作,必须满足以下条件:

  1. (x op y)的结果必须与(y op x)的结果相反。即,如果a>b,那么b<a。

  2. 传递性。即,如果a>b, b>c,那么a>c。

  3. x=y时,(x op z) = ( y op z )

顺带一说,在重写Java api的时候,如果没有十足把握的话,可以将它委托给另一个Java基础类(如String、Integer等)的对应api实现上。例如冯庆的解决方案,本质上就是将compare(a,b)操作委托给了int来实现。


 

参考

  1. 维基百科:https://en.wikipedia.org/wiki/Timsort#Galloping_mode

  2. http://blog.csdn.net/yangzhongblog/article/details/8184707

  3. http://bindog.github.io/blog/2015/03/30/use-formal-method-to-find-the-bug-in-timsort-and-lunar-rover


本文出自 “编程的摩羯男” 博客,请务必保留此出处http://winters1224.blog.51cto.com/3021203/1914094

TimSort排序算法及一个问题分析