Collections.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]); } }跟蹤Arrays.sort
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested) legacyMergeSort(a); else ComparableTimSort.sort(a); }LegacyMergeSort.userRequested指的啥呢？
static final class LegacyMergeSort { PRivate static final boolean userRequested = java.security.accessController.doPrivileged( new sun.security.action.GetBooleanAction( "java.util.Arrays.useLegacyMergeSort")).booleanValue(); }這是一個boolean值。說白了就是，如果用戶指定歸并排序那就歸并排序，否則就是ComparableTimSort。歸并排序比較常見，就不講了。貼一下ComparableTimSort
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) {//***********************************如果長度小于MIN_MERGE（32），那就用二分排序算法 int initRunLen = countRunAndMakeAscending(a, lo, hi); binarySort(a, lo, hi, lo + initRunLen); return; } /** * March over the array once, left to right, finding natural runs, * extending short natural runs to minRun elements, and merging runs * to maintain stack invariant. */ ComparableTimSort ts = new ComparableTimSort(a); int minRun = minRunLength(nRemaining); do { // Identify next run int runLen = countRunAndMakeAscending(a, lo, hi); // If run is short, extend to min(minRun, nRemaining) if (runLen < minRun) { //如果拐點小于minRun，就對整個minRun二分排序 int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen); runLen = force; } // Push run onto pending-run stack, and maybe merge ts.pushRun(lo, runLen);//**********************這里的runLen>=minRun ts.mergeCollapse();//*************調用mergeAt // Advance to find next run lo += runLen; nRemaining -= runLen; } while (nRemaining != 0); // Merge all remaining runs to complete sort assert lo == hi; ts.mergeForceCollapse();//*************也會調用mergeAt assert ts.stackSize == 1; } //minRunLength------一直取二分之一，直到小于MIN_MERGE（32） // n=奇數，return (n-1)/2+1。n=偶數，return n/2 private static int minRunLength(int n) { assert n >= 0; int r = 0; // Becomes 1 if any 1 bits are shifted off while (n >= MIN_MERGE) { r |= (n & 1); n >>= 1; } return n + r; } //countRunAndMakeAscending // 全是升序，那就返回high // 全是降序，那就返回high，并且要翻轉 // 先升后降，返回最高點 // 先降后升，返回最低點，并且之前的翻轉 // 說白了就是返回拐點 private static int countRunAndMakeAscending(Object[] a, int lo, int hi) { assert lo < hi; int runHi = lo + 1; if (runHi == hi) return 1; // Find end of run, and reverse range if descending if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0) runHi++; reverseRange(a, lo, runHi); } else { // Ascending while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0) runHi++; } return runHi - lo; } // ********************理解gallopRight和gallopLeft private void mergeAt(int i) { int base1 = runBase[i]; int len1 = runLen[i]; int base2 = runBase[i + 1]; int len2 = runLen[i + 1]; /* * Record the length of the combined runs; if i is the 3rd-last * run now, also slide over the last run (which isn't involved * in this merge). The current run (i+1) goes away in any case. */ runLen[i] = len1 + len2; if (i == stackSize - 3) { runBase[i + 1] = runBase[i + 2]; runLen[i + 1] = runLen[i + 2]; } stackSize--; /* * Find where the first element of run2 goes in run1. Prior elements * in run1 can be ignored (because they're already in place). */ int k = gallopRight((Comparable<Object>) a[base2], a, base1, len1, 0); assert k >= 0; base1 += k; len1 -= k; if (len1 == 0) return; /* * Find where the last element of run1 goes in run2. Subsequent elements * in run2 can be ignored (because they're already in place). */ len2 = gallopLeft((Comparable<Object>) a[base1 + len1 - 1], a, base2, len2, len2 - 1); assert len2 >= 0; if (len2 == 0) return; // Merge remaining runs, using tmp array with min(len1, len2) elements if (len1 <= len2) mergeLo(base1, len1, base2, len2); else mergeHi(base1, len1, base2, len2); }算法思想如下： 1.構造minRun，值等于長度的一直除以2，直到小于MIN_MERGE 2.（這一步會無限循環） （1）尋找第一個拐點，記為index。如果index小于minRun，那就對整個minRun數據二分排序。 （2）將起始位置和拐點位置push進去，然后對當前的各區塊進行merge。 由于要合并的兩個 run 是已經排序的，所以合并的時候，有會特別的技巧。 假設兩個 run 是 run1,run2 ，先用 gallopRight在 run1里使用 binarySearch 查找run2 首元素 的位置k, 那么 run1 中 k 前面的元素就是合并后最小的那些元素。然后，在run2 中查找run1 尾元素 的位置 len2 ，那么run2 中 len2 后面的那些元素就是合并后最大的那些元素。最后，根據len1 與len2 大小，調用mergeLo或者 mergeHi 將剩余元素合并。
新聞熱點
疑難解答
