Java的List.sort()排序方法源码理解

排序的入口List.sort()按照常识List是一个接口照理说sort()是不会实现的。JDK8新增了default关键字来修饰接口里的方法将方法标识为默认方法对应的实现default void sort(Comparator? super E c) { Object[] a this.toArray(); Arrays.sort(a, (Comparator) c); ListIteratorE i this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } }借用了Arrays.sort()的方法那么Arrays.sort()又是怎么实现的呢二、第一层实现Arrays.sort()public static T void sort(T[] a, Comparator? super T c) { if (c null) { sort(a); } else { if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else TimSort.sort(a, 0, a.length, c, null, 0, 0); } }这里可以看到一个判断分支if (LegacyMergeSort.userRequested)如果为true使用归并排序否则使用TimSort。userRequested的值是用下面的代码取得的允许用户通过参数手动选择是否使用归并排序userRequested java.security.AccessController.doPrivileged(new sun.security.action.GetBooleanAction(java.util.Arrays.useLegacyMergeSort)).booleanValue();我们先看看归并排序的实现。注意这段代码上方有段注释未来的发行版中会被移除也就意味着后续不会再使用归并排序了。private static T void legacyMergeSort(T[] a, Comparator? super T c) { T[] aux a.clone(); if (cnull) mergeSort(aux, a, 0, a.length, 0); else mergeSort(aux, a, 0, a.length, 0, c); }这两个mergeSort的区别只在于是否使用传入的Comparator。如果不使用则使用Object.equals()的默认比较方式来进行排序。下面先深入看一下mergeSort的实现。三、第二层实现之mergeSort归并排序的思想是将数组拆分成两部分分别对这两部分进行递归的归并排序。排序完成后同时用两个迭代器/指针遍历两个数组依次将其中最符合要求的从小到大排序就是最小的从大到小排序就是最大的放入新数组中。如果一个数组的元素放完了就把另一个数组剩余所有元素按已有顺序全部放入新数组中。3.1 为什么选择归并排序在众多的常见比较排序算法中在以空间换时间的策略下归并排序有着最好的平均性能并且是稳定的。这句话怎么理解呢比较排序即通过比较来决定元素的顺序。常见的比较排序包括插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序。空间换时间是指归并排序需要额外的临时数组空间复杂度为O(n)最好的平均性能也是O(nlogn)不会像快速排序在最差情况下的O(n^)稳定的是指排序后相同大小的元素前后顺序不会改变。平均性能为O(nlogn)的堆排序和快速排序都是不稳定的。各种常见排序算法的比较和原理本文就不展开讲了网络上连篇累牍非常多有兴趣可以自行了解。3.2 归并排序源码解读private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) { int length high - low; // Insertion sort on smallest arrays if (length INSERTIONSORT_THRESHOLD) { for (int ilow; ihigh; i) for (int ji; jlow ((Comparable) dest[j-1]).compareTo(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); mergeSort(dest, src, mid, high, -off); // 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 (((Comparable)src[mid-1]).compareTo(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 ((Comparable)src[p]).compareTo(src[q])0) dest[i] src[p]; else dest[i] src[q]; } }这个算法分两部分当数组长度INSERTIONSORT_THRESHOLD(源码中是7)时直接使用插入排序用一部分时间复杂度上升换取一部分空间复杂度的下降。对于归并排序的递归部分off表示偏移量这个参数只有在数组内部分元素排序时才是一个非0值整个数组排序时是0可以不关心。high表示传入的是数组长度因此数组最后一个元素的下标是(high-1)。low则是第一个元素的下标。计算中值使用了位操作。当长度为大于1的奇数时均分的两个子数组由于舍去了小数值前一个数组的元素比后一个少一个。对于归并排序的归并部分如果前一个数组的最后一个元素比后一个数组的第一个元素(大/小)直接合并这里的System.arraycopy是native方法。归并的遍历简化了写法没有先做下标的运算再调用System.arraycopy而是直接两个数组一起遍历。可以看出此处for循环中的if是合并了很多场景写成的。四、第二层实现之TimSort4.1 背景看完归并排序的实现才是重头TimSort。以下摘自JDK注释A stable, adaptive, iterative mergesort that requires far fewer than nlg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space.简单概括一下TimSort是稳定、自适应、迭代的归并排序在部分有序的数组上比较次数远少于nlogn在随机数组上的表现和传统的归并排序一样。TimSort的理论最初在1993年由Peter Mcllroy提出由Tim Peters于2002年在Python中应用后续逐步成为了包括Java、Swift、谷歌浏览器的默认排序方法。Tim Peters 本人对 TimSort 原理的介绍见http://svn.python.org/projects/python/trunk/Objects/listsort.txt4.2 基本概念不打算在这里介绍过多的概念造成阅读代码时的困难先知道一些核心的概念就行了。run —— 可以直观地翻译为一趟跑步的距离、旅程、航程等代表了一部分已经有序的子数组。这里不打算自己造概念以下仍称为run。galloping mode —— 可以译为加速模式同样不翻译。4.3 算法框架先不纠结具体细节看一下TimSort的整体框架。注意在Arrays.sort()调用处的入参是TimSort.sort(a, 0, a.length, c, null, 0, 0)其中a是待排序数组T[] a,c是比较器Comparator? super T c。static T void sort(T[] a, int lo, int hi, Comparator? super T c, T[] work, int workBase, int workLen) { assert c ! null a ! null lo 0 lo hi hi a.length; // (1)第一部分 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, c); binarySort(a, lo, hi, lo initRunLen, c); return; } //(2) /** * 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. */ TimSortT ts new TimSort(a, c, work, workBase, workLen); int minRun minRunLength(nRemaining); do { // Identify next run int runLen countRunAndMakeAscending(a, lo, hi, c); // 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, c); 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; }先看最开头的部分(1)。如果待排序部分nRemaining过小(为0或1)直接返回结果很好理解。如果nRemainingMIN_MERGE(MIN_MERGE被设置为32)则使用一个“微型”的TimSort也即二分插入排序的变体。这个二分插入排序内部不做任何合并。这一步的解读参考后文5.1节这里暂时跳过只需要知道countRunAndMakeAscending方法的目的是计算待排序部分__从起始位置起保持升序或降序的最长的run的长度initRunLen__。接着看第(2)部分。这部分先创建了一个TimSort对象对象内有什么先不管继续看框架部分。int minRun minRunLength(nRemaining)是一个纯粹对数值计算方法目的是计算出将数组需要划分成多少个run这时的run的长度使用minRun表示并且需要让nRemaining/minRun最接近一个2的幂实际上nRemaining/k严格小于2的幂。这种情况下的分组的个数接近2的幂更利于合并。具体的计算方法minRunLength()不在这节展开请参考后文5.2节。计算出要拆分的run的个数minRun后进入循环循环中包括计算数组中从lo开始最长连续递增的序列长度如果长度不满一个minRun强制将从lo开始的数组扩展到minRun长度或在排序中可以处理的最大长度nRemaining。将当前处理的run压栈pushRun并视情况mergemergeCollapse并将lo下标前移未排序个数nRemaining减去本次的runLen循环直到nRemaining0。循环完成时做一次强制merge——mergeForceCollapse更具体的实现接下来需要研究一下TimSort这个类使用的三个类方法pushRun、mergeCollapse、mergeForceCollapse。4.4 TimSort类的实例化TimSort类只会在调用TimSort.sort()方法时实例化一次并且这个构造方法是private的。借助这个对象实例保存一些处理中数据。4.4.1 成员变量简单翻译了一下注释。如果看不懂可以先不纠结继续看后续的排序方法来理解。/** * 最小的待合并的run长度的阈值 */ private static final int MIN_MERGE 32; /** * 待排序的数组 */ private final T[] a; /** * 比较器 */ private final Comparator? super T c; /** * galloping mode 的初始阈值。连续取胜达到该次数后切换到 gallop */ private static final int MIN_GALLOP 7; /** * 当前进入 galloping mode 的阈值随数据特征动态调整 */ private int minGallop MIN_GALLOP; /** * 初始化用于存放临时排序数据的数组长度最大值 */ private static final int INITIAL_TMP_STORAGE_LENGTH 256; /** * 用于归并的临时数组 */ private T[] tmp; private int tmpBase; // base of tmp array slice private int tmpLen; // length of tmp array slice /** * 待归并的run的栈。第i个run下标从base[i]开始长度是len[i]。 * 满足runBase[i] runLen[i] runBase[i 1] * */ private int stackSize 0; // Number of pending runs on stack private final int[] runBase; private final int[] runLen;4.4.2 构造方法排序时创建的参数是worknull的因此不会走下面的分支。构造方法初始化了用于存放临时数据的数组以及用来存放待排序栈的run的起始下标和长度。private TimSort(T[] a, Comparator? super T c, T[] work, int workBase, int workLen) { this.a a; this.c c; // Allocate temp storage (which may be increased later if necessary) int len a.length; int tlen (len 2 * INITIAL_TMP_STORAGE_LENGTH) ? len 1 : INITIAL_TMP_STORAGE_LENGTH; if (work null || workLen tlen || workBase tlen work.length) { SuppressWarnings({unchecked, UnnecessaryLocalVariable}) T[] newArray (T[])java.lang.reflect.Array.newInstance