Collections,sort()实现原理

查看源码可以发现Collections.sort的实现是Arrays.sort，而Arrays.sort的实现是ComparableTimSort.sort,然后才到sort方法和它的定义，查看排序的主体部分也可以发现一个binarySort的方法，这是排序方法的实现，是通过调用Object的CompareTo进行比较的。

每一步代码如下：

public class ListSort {
    public static void main(String[] args){
        List<String> list=new ArrayList<String>();
        list.add("ohjx");
        list.add("ghjg");
        list.add("hggh");
        Collections.sort(list);
        for (String listString:list){
            System.out.println(listString);
        }
    }
}

Arrays.sort：

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

ComparableTimSort.sort：

public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a);
}

sort：

static void sort(Object[] a) {
      sort(a, 0, a.length);
}

static void sort(Object[] a, int lo, int hi) {
    rangeCheck(a.length, lo, hi);
    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;
    }

binarySort：

private static void binarySort(Object[] a, int lo, int hi, int start) {
    assert lo <= start && start <= hi;
    if (start == lo)
        start++;
    for ( ; start < hi; start++) {
        @SuppressWarnings("unchecked")
        Comparable<Object> pivot = (Comparable) a[start];

        // Set left (and right) to the index where a[start] (pivot) belongs
        int left = lo;
        int right = start;
        assert left <= right;
        /*
         * Invariants:
         *   pivot >= all in [lo, left).
         *   pivot <  all in [right, start).
         */
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (pivot.compareTo(a[mid]) < 0)
                right = mid;
            else
                left = mid + 1;
        }
        assert left == right;

        /*
         * The invariants still hold: pivot >= all in [lo, left) and
         * pivot < all in [left, start), so pivot belongs at left.  Note
         * that if there are elements equal to pivot, left points to the
         * first slot after them -- that's why this sort is stable.
         * Slide elements over to make room for pivot.
         */
        int n = start - left;  // The number of elements to move
        // Switch is just an optimization for arraycopy in default case
        switch (n) {
            case 2:  a[left + 2] = a[left + 1];
            case 1:  a[left + 1] = a[left];
                     break;
            default: System.arraycopy(a, left, a, left + 1, n);
        }
        a[left] = pivot;
    }
}

这就是层层调用的代码（按顺序）

Collections.sort方法如果只有一个参数，那么默认采用自然排序的方法对指定的列表（参数）进行排序，也可以传入两个参数，一个是待排序的列表，另一个就是指定的排序规则。两个方法的定义如下：

今天的文章Collections,sort()实现原理分享到此就结束了，感谢您的阅读。