Arrays.sort 实现原理和 Collections.sort 实现原理

starlin 1,062 2018-09-19

本文若无特殊说明,JDK版本为1.8

使用

两者作用都是用于排序

原理

这里先插一句Collections和Collection的区别:

  • java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。
  • java.util.Collections 是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全等操作。

事实上 Collections.sort()方法底层就是调用的Arrays.sort(),所以这里就合并一起说下,先看源码,如下:

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);
    }
}

看看Arrays.sort()方法

public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        // 归并排序
        legacyMergeSort(a);
    else
        // Timsort排序
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

ComparableTimSort.sort()方法:

    static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
        assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi);
            binarySort(a, lo, hi, lo + initRunLen);
            return;
        }

        /**
         * March over the array once, left to right, finding natural runs,
         * extending short natural runs to minRun elements, and merging runs
         * to maintain stack invariant.
         */
        ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            int runLen = countRunAndMakeAscending(a, lo, hi);

            // If run is short, extend to min(minRun, nRemaining)
            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen);
                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;
    }

其实底层实现最终还是调用TimSort
Timsort排序算法是结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法

Timsort的核心过程:

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

对TimSort的底层就不详细介绍了,有兴趣的可以搜下相关文章
另外还提下,Java 8 引入了并行排序算法(直接使用 parallelSort 方法),有兴趣的可以去了解下

End,感谢阅读


# java集合