Java快排源码简单解读

今天下午的时候有同学跟我聊快排的效率，我试着讲一遍底层实现发现印象已经模糊了。
所以刚才上课摸鱼对sort源码重新看了一遍，写了一点注释，顺便分享给大家，有不对的地方望指正。
电脑电量原因，经典的归并实现部分没有写

java.util.Arrays.sort()调用的java.util.DualPivotQuickSort.sort()
所以这篇文章解释的是java.util.DualPivotQuickSort.sort()的实现

static void sort(int[] a, int left, int right,
                 int[] work, int workbase, int workLen) {
    // Use Quicksort on small arrays
    //小于47使用插入排序，47~286使用快排
    if (right - left < QUICKSORT_THRESHOLD) {
        sort(a, left, right, true);
        return;
    }
	
    //以下为大于286的排序
    
    //定义一个记录第i次运行起始位置的数组
    int[] run = new int[MAX_RUN_COUNT + 1];
    //count记录每一段降序，初始为第0段，第0段起始位置为left
    int count = 0; run[0] = left;

    // Check if the array is nearly sorted
    //从left~right的遍历
    for (int k = left; k < right; run[count] = k) {
        // Equal items in the beginning of the sequence
        //相同的元素直接跳过
        while (k < right && a[k] == a[k + 1])
            k++;
        if (k == right) break;  // Sequence finishes with equal items
        if (a[k] < a[k + 1]) { // ascending
            //如果升序，符合条件，跳过
            while (++k <= right && a[k - 1] <= a[k]);
        } else if (a[k] > a[k + 1]) { // descending
            //降序，不符合条件，向后找，找到连续降序的末位
            while (++k <= right && a[k - 1] >= a[k]);
            // Transform into an ascending sequence
            //将这一条降序序列进行翻转
            for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
            }
        }

        // Merge a transformed descending sequence followed by an
        // ascending sequence
        //将转换后的降序，与前面的升序连接
        //升序序列+转换后的降序序列，count向前找这段序列中出现降序的地方
        if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {
            count--;
        }

        
        
        if (++count == MAX_RUN_COUNT) {
            sort(a, left, right, true);
            return;
        }
    }

    // These invariants should hold true:
    //    run[0] = 0
    //    run[] = right + 1; (terminator)

    if (count == 0) {
        //如果没有降序，这是一个单调的，直接返回
        // A single equal run
        return;
    } else if (count == 1 && run[count] > right) {
        //如果有降序，但降序起始位置在范围之外
        // Either a single ascending or a transformed descending run.
        // Always check that a final run is a proper terminator, otherwise
        // we have an unterminated trailing run, to handle downstream.
        return;
    }
    right++;
    if (run[count] < right) {
        //极端情况：最后一次运行的位置不在终点
        //这可能是由于最后一段序列是相等序列，或者是有一个单元素在末尾
        //Fix方法：run[count+1]=right;
        
        // Corner case: the final run is not a terminator. This may happen
        // if a final run is an equals run, or there is a single-element run
        // at the end. Fix up by adding a proper terminator at the end.
        // Note that we terminate with (right + 1), incremented earlier.
        run[++count] = right;
    }

    // Determine alternation base for merge
    //odd确定合并的替代基础
    byte odd = 0;
    for (int n = 1; (n <<= 1) < count; odd ^= 1);

    //准备一个临时空间
    //排序过程中可用的额外空间为work中的[workbase,workbase+workLen]。如果work给定的空间不够用，就会新开辟足够的空间。
    //a为原数组，b为临时数组，与a交替使用
    // Use or create temporary array b for merging
    int[] b;                 // temp array; alternates with a
    int ao, bo;              // array offsets from 'left'
    int blen = right - left; // space needed for b
    if (work == null || workLen < blen || workbase + blen > work.length) {
        //创建新的临时空间
        work = new int[blen];
        workbase = 0;
    }
    if (odd == 0) {
        System.arraycopy(a, left, work, workbase, blen);
        b = a;
        bo = 0;
        a = work;
        ao = workbase - left;
    } else {
        b = work;
        ao = 0;
        bo = workbase - left;
    }

    //从这里开始归并排序，细节就不讲了，自行百度吧
    // Merging
    for (int last; count > 1; count = last) {
        for (int k = (last = 0) + 2; k <= count; k += 2) {
            int hi = run[k], mi = run[k - 1];
            for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                    b[i + bo] = a[p++ + ao];
                } else {
                    b[i + bo] = a[q++ + ao];
                }
            }
            run[++last] = hi;
        }
        if ((count & 1) != 0) {
            for (int i = right, lo = run[count - 1]; --i >= lo;
                 b[i + bo] = a[i + ao]
                );
            run[++last] = right;
        }
        int[] t = a; a = b; b = t;
        int o = ao; ao = bo; bo = o;
    }
}