Collections,sort()实现原理

　

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

相关阅读

【python基础】sort函数

1. 基本用法 1）仅对于list类型的数据 a.sort() 按升序 a.sort(reverse = True) 按降序 2）对于所有可排序类型的数据 sorted(a, reve

Arrays.sort()

之前做笔试有个排序的问题，可以将字符串转换成字符数组再进行排序，之后用toString()方法在转为字符串，但当时没有想到，特此记录下来。

Spring AOP的实现原理（二）

**二、AOP的设计与实现 1、JVM的动态代理特性** 在Spring AOP实现中， 使用的核心技术时动态代理，而这种动态代理实

collections.sort()默认排序规则

默认按ASCII码排序，一位一位的比较，应该排了3次第一次比较第一位全部是a，所以顺序没变第二次第二位排序[a0, a1, a12, a11, a10, a2,

JAVA的Collections类中shuffle的用法

就是随机打乱原来的顺序，和洗牌一样。如：// ShuffleTest.java import java.util.*; public class ShuffleTest { public stat