2017-10-16

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

　　Collections.sort方法底层调用的是Arrays.sort方法。底层实现都是TimeSort实现的。TimSort算法就是找到已经排好序数据的子序列，然后对剩余部分排序(使用了插入排序算法)，然后合并起来.

Collections.sort方法底层

1 2	List<String> list = Arrays.asList("1", "3", "2", "6"); Collections.sort(list);

进入源码发现，实际上调用的就是list的sort方法。

// Collections.java
public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}
// List.java
@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);
    }
}