面试题深入思考01-----Arrays.sort()与Collections.sort()

面试题深入思考01-----Arrays.sort()与Collections.sort()

1.Collections.sort();

Collections本质是关于集合的一种工具类。其中包含对集合的各种api，例如排序，反转，交换和复制等。其中sort方法提供两种入参形式：

public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
}

public static <T> void sort(List<T> list, Comparator<? super T> c) {
        list.sort(c);
}

而对于其调用的方法sort()来自List:

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()，注意，此时入参是存在Comparator的！

2.Arrays.sort()

由上文提到，sort方法是存在多种入参的，主要分为两大种：
第一种就是常用的传入普通的数组，以及带索引的参数为主：

 public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, 0, a.length);
    }

而第二种加入比较器来进行排序：

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

2.1 DualPivotQuicksort

相关参考

2.2 LegacyMergeSort与TimSort

而对于带有Comparator的sort，走的是LegacyMergeSort与TimSort两个排序方法，根据设置true和false来选择。
LegacyMergeSort()则为正常的归并排序,而Timsort是结合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在现实中有很好的效率。
相关参考

总结

本质上都是对Arrays.sort()的调用，因为入参设置的不同，包括传参的比较器，以及数组的大小设置，在内部采用不同的排序来提高效率。