Collections.sort 集合排序底层实现

// 用法一：

List<String> list = new ArrayList<String>();

Collections.sort(list);

源码：

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

// Arrays.java

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

// ComparableTimSort.java

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; }

/** * 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) { 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); ts.mergeCollapse();

// Advance to find next run lo += runLen; nRemaining -= runLen; } while (nRemaining != 0);

// Merge all remaining runs to complete sort assert lo == hi; ts.mergeForceCollapse(); assert ts.stackSize == 1; }

// 用法二：

Collections.sort(excelData, new Comparator<List<String>>() {

@Override public int compare(List<String> o1, List<String> o2) { if (StringUtils.equals(o1.get(0), o2.get(0))) return -1; else return 1; } });