由Collections.sort()引发的归并排序问题

将分为三步来进行分析

  • 找出归并排序方法
  • 分析源码
  • 附上网上找的时序图

一、找出Collections.sort()实际排序的方法

// 1.这里是入口,还有一个重载方法传入一个比较器,用作比较,可以暂时忽略
public static <T extends Comparable<? super T>> void sort(List<T> list) {
        // 进入第二步
        list.sort(null);
}

// 2.list.sort() 可以看到底层用的其实是Arrays.sort()
// 这里需要注意的是,Arrays.sort()是个重载方法,当参数是基本数据类型和Object时,所用到的排序是不一样的,可以分开看一下
@SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        // 进入第三步
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

// 3.没什么好说的,咱们研究的是Comparator为null的情况
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, null, 0, 0);
        }
}

// 4.第四步
public static void sort(Object[] a) {
        // 这个是一个环境变量,在jvm参数中配置的,jdk1.7之后默认是false
        // 但是我们这次研究的就是归并排序,所以直接点进去看就行了
        if (LegacyMergeSort.userRequested)
            // 归并排序
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

二、分析归并排序源码,看注释!!

// 请注意,这是一个递归方法,请按照递归方法的思路去理解
// src 是一个从dest  clone出来的数组,用来在递归中做排序的载体
private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        // 1.当长度小于7,直接插入排序比较快,所以直接使用插入排序即可
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        // 2.递归中到达这一步肯定是因为长度比较大
        // 所以归并排序在这里进行了二分,分别将前一半排序,后一半也排序
        // 如果前一半长度还是比7大,那就递归的时候继续分,直到比7小,递归才算结束
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // 3.这也是递归中的一步,因为经过上两行的递归,现在前半部分和后半部分都已经是有序的了,那么只要前半部分的最后一位,比后半部分的第一位还小,不就说明前后现在有序么,直接将src数组拷贝到dest即可(当然这里讨论的是默认升序的情况)
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // 4.在递归中,如果第三步不满足,那就要对前后两部分进行归并排序了
        // 怎么归并呢?以升序为例子
        // 归并排序其实就是对两个有序的数组,每次只比较两个的头部,哪个比较小,就把哪个取出来,然后再次比较两个数组的头部,知道两个数组的值都被取完,整个大数组就排好序了,下边几行代码就是做这个的
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
}

时序图

时序图

排序示例

四、既然说到了sort,下一章分析下TimeSort源码

链接

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。