看源碼時專門瞄了下排序算法，跟著學一下。JDK的排序是 插入排序、快排揉一起的，下面學下快速排序。在JDK中當待排序的元素個數(shù)小于 ** 286 ** 時使用快速排序，當待排序的元素個數(shù)小于 ** 47 ** 時使用插入排序。JDK源碼類：DualPivotQuicksort.java
本文地址：http://m.itdecent.cn/p/a7ceb2dc62ca

由于JDK的算法寫的怪怪的（個人感覺），所以不參照它的代碼，只參照它的思想。

對于快速排序，JDK先采用雙軸快排，即：取5個元素，按順序排好，然后取第二個和第四個元素作為軸開始排序。如果這五個元素恰好相等，則使用中間的元素作為軸開始快排（傳統(tǒng)的快排）

• 先來看下傳統(tǒng)的快排：單軸快排，軸的選擇有很多種，第一個元素，最后一個元素，中心位置元素，隨機位置元素，取首尾中3個元素中的中間值等，也可以參照JDK取5個元素的中值作為軸。此處以取首尾中3個元素中的中間值為例

public static void basicSort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    basicSort(array, 0, array.length - 1);
}

private static void basicSort(int[] array, int low, int high) {
    if (low >= high) {
        return;
    }
    // 這里通常判斷下待排序元素的個數(shù)，比如小于47個使用插入排序，以提高性能
    // .....

    // 單軸快排，核心在取軸這
    int position = basicPosition(array, low, high);
    basicSort(array, low, position - 1);
    basicSort(array, position + 1, high);
}

private static int basicPosition(int[] array, int low, int high) {
    // 初始化軸數(shù)據(jù)，獲取軸數(shù)據(jù)并放到數(shù)組第一個位置
    initPivotData(array, low, high);
    
    int pivotData = array[low];     // 軸數(shù)據(jù)
    int begin = low, end = high;
    while (begin < end) {
        while (array[begin] <= pivotData && begin < high) {
            begin++;
        }
        while (array[end] > pivotData && end >= low) {
            end--;
        }
        if (begin < end) {
            swap(array, begin, end);
        }
        printArray(array);
    }
    if (end != low) {
        swap(array, low, end);
        printArray(array);
    }
    return end;
}
// 這里將3各元素做升序排序，并將中值交換到數(shù)組第一個元素處
private static void initPivotData(int[] array, int low, int high) {
    int mid = low + (high - low) / 2;
    
    if (array[mid] > array[high]) {
        swap(array, mid, high);
    }
    if (array[low] > array[high]) {
        swap(array, low, high);
    }
    if (array[mid] > array[low]) {
        swap(array, mid, low);
    }
}

private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

• 下面看下JDK的雙軸快排，選兩個軸，排序方式，比軸1小的數(shù)據(jù)放到軸1左側(cè)，比軸2大的數(shù)據(jù)放到軸2右側(cè)，其余的數(shù)據(jù)在軸1和軸2之間

public static void dualPivotSort(int[] array) {
    dualPivotSort(array, 0, array.length-1);
}

// 參照JDK取軸的方法，該方法未使用
private static void initdualPivotData(int[] array, int low, int high) {
    int length = high - low + 1;    // 待排序元素的個數(shù)
    int seventh = (length >> 3) + (length >> 6) + 1;    // 7 等份
    
    // 取5個節(jié)點
    int e3 = (low + high) >>> 1; // The midpoint
    int e2 = e3 - seventh;
    int e1 = e2 - seventh;
    int e4 = e3 + seventh;
    int e5 = e4 + seventh;

    // 對這5各元素做插入排序，然后去e2和e4作為軸
}

private static void dualPivotSort(int[] array, int lowIndex, int highIndex) {

    if (highIndex <= lowIndex) return;
    
//        initdualPivotData(array, lowIndex, highIndex);
    
    int pivot1 = array[lowIndex];
    int pivot2 = array[highIndex];

    // 確保 pivot1 < pivot2
    if (pivot1 > pivot2) {
        swap(array, lowIndex, highIndex);
        pivot1 = array[lowIndex];
        pivot2 = array[highIndex];
    }
    else if (pivot1 == pivot2) {
        while (pivot1 == pivot2 && lowIndex < highIndex){
            lowIndex++;
            pivot1 = array[lowIndex];
        }
    }

    int i = lowIndex + 1;
    int lt = lowIndex + 1;
    int gt = highIndex - 1;

    while (i <= gt) {
        if (array[i] < pivot1) {
            // 小于軸1，則將數(shù)據(jù)交換到軸的左側(cè)
            swap(array, i++, lt++);
        }
        else if (pivot2 < array[i]) {
            // 大于軸2，則將數(shù)據(jù)交換到軸的右側(cè)
            swap(array, i, gt--);
        }
        else {
            i++; // 其他不處理，索引向后移動1
        }
    }

    /* 都交換之后
     * 將軸1交換到中間部分的左側(cè)；軸2交換到中間部分的右側(cè)
     * 這樣確保左側(cè)都小于軸1，右側(cè)都大于軸2
     */
    swap(array, lowIndex, --lt);
    swap(array, highIndex, ++gt);

    // 普通的快排，只需對軸兩側(cè)遞歸處理
    // 這里是雙軸快排，所以要對左側(cè)、中間、右側(cè)分別遞歸處理
    dualPivotSort(array, lowIndex, lt - 1);
    dualPivotSort (array, lt + 1, gt - 1);
    dualPivotSort(array, gt + 1, highIndex);
}

• 快速排序還有一種方式用的比較多，3路排序。該方案也是選一個軸，比軸小的數(shù)據(jù)在軸的左側(cè)，比軸大的數(shù)據(jù)在軸的右側(cè)，中間是與軸相等的數(shù)據(jù)。

public static void threeWaySort(int[] array) {
    threeWaySort(array, 0, array.length-1);
}

private static void threeWaySort(int[] array, int low, int high) {
    
    if (high <= low)
        return;

    // 初始化軸數(shù)據(jù)，獲取軸數(shù)據(jù)并放到數(shù)組第一個位置（使用第一種快排的方式獲?。?    initPivotData(array, low, high);
    
    int lt = low;   // 記錄最后一次發(fā)現(xiàn)低值的位置
    int gt = high;  // 記錄最后一次發(fā)現(xiàn)高值的位置
    int i = low + 1;// 用于從左側(cè)遍歷到右側(cè)

    int pivotIndex = low;
    int pivotValue = array[pivotIndex];

    while (i <= gt) {
        // 小于軸，交換到左側(cè)
        if (array[i] < pivotValue) {
            swap(array, i++, lt++);
        }
        // 大于軸，交換到右側(cè)
        else if (pivotValue < array[i]) {
            swap(array, i, gt--);
        }
        else {
            i++;    // 相等不做處理
        }
    }

    // 這里與單軸快排一樣
    threeWaySort(array, low, lt - 1);
    threeWaySort(array, gt + 1, high);
}