List中的Sort

基本用法

实现了List接口的容器，通过以下方法对其中的元素进行排序

default void sort(Comparator<? super E> c)

需要传入一个实现了Comparator接口的比较器c，通过比较器来规定两个实例的大小关系，如果c为null的话，则需要容器中的元素实现comparable接口，进而可以直接进行排序

原理讲解

文档讲解如下：

This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

该排序方式是一种稳定的、适应性的、迭代式的归并排序，平均时间复杂度为nlg(n)，最优时间复杂度能达到n。这种排序的临时存储空间最多需要存储n/2个对象引用。

可知，List的默认排序方式是一种改进的归并排序，

源码分析

1. ArrayList中的sort(Comparator<? super E> c)

可以看到，在传入比较器c后，首先调用以下方法：

    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

重点关注Arrays.sort((E[]) elementData, 0, size，c)：

其中第一个参数elementData来源于List中的元素转化成的Object数组，在这里强转为实际元素类型的数组传入该方法；第二个参数“fromIndex”是List容器元素起始下标；第三个参数“toIndex”是List的size，也就是元素的终止下标；第四个参数就是比较器Comparator

另外还启用modCount执行fail-fast机制来监控并发情况，如果在进行完排序操作后发现数组已经被修改（即modCount的值被刷新），则报错；操作完成后modeCount加1

2. Arrays.sort

参数传入Arrays后调用以下方法：

    public static <T> void sort(T[] a, int fromIndex, int toIndex,
                                Comparator<? super T> c) {
        if (c == null) {
            sort(a, fromIndex, toIndex);
        } else {
            rangeCheck(a.length, fromIndex, toIndex);
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, fromIndex, toIndex, c);
            else
                TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
        }
    }

• 若Comparator为空，则直接调用sort(a, fromIndex, toIndex)这个重载
• 若Comparator不为空，则首先执行rangeCheck：

    private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        }
        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(toIndex);
        }
    }

可以看到，如果arrayLength、fromIndex、toIndex这三个参数不符合规范（即起始下标和终止下标没包含在数组大小范围内）的话，则会报错

• 执行完rangeCheck后，需要对LegacyMergeSort.userRequested进行判断，这个判断是确认是否再用JDK1.6之前的经典算法（默认不采用，可修改JVM参数来强行采用这种算法），经典算法是legacyMergeSort（经典归并排序），新算法是TimSort（这种算法是改编自Tim Peter为Python设计的排序算法，相对传统归并排序算法，）

if (LegacyMergeSort.userRequested)
    legacyMergeSort(a, fromIndex, toIndex, c);
else
    TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);

3.经典算法legacyMergeSort（传统归并排序）

    /** To be removed in a future release. */
    private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
                                            Comparator<? super T> c) {
        T[] aux = copyOfRange(a, fromIndex, toIndex);
        if (c==null)
            mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
        else
            mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
    }

（可以看到，该算法未来版本将被移除）

• 首先将需要排序的数组拷贝为aux数组（将下标fromIndex到下标toIndex的子片段复制一份，其中复制后的数组取不到toIndex）
• 若比较器c为空，则调用不包含比较器的排序算法，否则调用使用比较器的排序算法
• 关注第二个排序算法：

    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low, int high, int off,
                                  Comparator c) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off, c);
        mergeSort(dest, src, mid, high, -off, c);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (c.compare(src[mid-1], src[mid]) <= 0) {
           System.arraycopy(src, low, dest, destLow, length);
           return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

• 第一个参数src是复制后的新数组aux；第二个参数dest是原数组a；第三个参数low是数组起始位置fromIndex；第四个参数high是数组终止位置toIndex；第五个参数是-fromIndex，本例子中是0；第六个参数是比较器c
• 首先计算length，为终止位置 - 起始位置
• 然后，当length分割到某个阈值（采用简单插入算法的数组长度）后，进行最小单位的插入排序，将分割后的序列有序化
• 剩下的就是传统归并排序的递归分割方法（详情请看归并排序笔记）

4.Timsort

以后再看吧。。。