今天有人問我java裡面的sort 方法 到底是什麼什麼排序方法。剛開始我也很蒙 一直在用卻說不出所以然來。所以我今天就看下原始碼

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

legacyMergeSort演算法

	private static void legacyMergeSort(Object[] a) {		//定義心的陣列，作為排序後的物件        Object[] aux = a.clone();        mergeSort(aux, a, 0, a.length, 0);    }	private static void mergeSort(Object[] src,                                  Object[] dest,                                  int low,                                  int high,                                  int off) {        int length = high - low;        // 陣列大小如果小於7，則使用插入排序        if (length < INSERTIONSORT_THRESHOLD) {            for (int i=low; i<high; i++)                for (int j=i; j>low &&                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)                    swap(dest, j, j-1);            return;        }        // 利用分治思想，進行拆分，遞迴呼叫插入排序        int destLow  = low;        int destHigh = high;        low  += off;        high += off;        int mid = (low + high) >>> 1;        mergeSort(dest, src, low, mid, -off);        mergeSort(dest, src, mid, high, -off);        // 合併相鄰兩個已排好的部分，若左邊最大的  小於  右邊最小的，        // 說明陣列已經排好順序，直接複製        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {            System.arraycopy(src, low, dest, destLow, length);            return;        }        // 進行歸併排序，        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)                dest[i] = src[p++];            else                dest[i] = src[q++];        }    }

總結

平均時間複雜度：O(nlogn) 最佳時間複雜度：O(n) 最差時間複雜度：O(nlogn) 空間複雜度：O(n) 排序方式：In-place 穩定性：穩定

上面的程式碼的最佳化核心部分就是

// 改進歸併排序在歸併時先判斷前段序列的最大值與後段序列最小值的關係再確定是否進行復制比較。	//如果前段序列的最大值小於等於後段序列最小值，則說明序列可以直接形成一段有序序列不需要再歸併，	//反之則需要。所以在序列本身有序的情況下時間複雜度可以降至O(n)    if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {        System.arraycopy(src, low, dest, destLow, length);        return;    }

歸併排序演算法中，歸併最後到底都是相鄰元素之間的比較交換，並不會發生相同元素的相對位置發生變化，故是穩定性演算法。

然而在新的jdk 版本中這個排序幾乎不在用了

    public static void sort(Object[] a) {        // 只有老的JDK 版本這個值預設值 才會生效        if (LegacyMergeSort.userRequested)            legacyMergeSort(a);        else            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);    }

所以現在基本用的都是ComparableTimSort.sort 關於這個演算法 我會在下篇文章中詳細講解。