排序算法 | 快速排序算法原理及實作和優化（二）

接上文《資料結構和算法 | 快速排序算法原理及實作和優化（一）》，我們來講講快速排序的五種優化方案。

1、優化選取基準點

三數取中法：先找出三個關鍵字，然後排序，取中間的關鍵字（至少不會是兩個極端）。在代碼示例中我們選取相應區間的開始元素、中間元素和末尾元素。

按照所選取的基準點的順序可以構造一顆順序二叉樹。二叉樹的深度就是遞歸的深度。二叉樹的平衡性越好，算法的性能越好。

2、優化不必要的交換

将交換改為指派。

3、優化小數組時的排序方案

大資料排序時對快速排序算法性能的影響很小。但是，隻有幾個資料要排序時有效率更高的排序算法。例如，直接插入排序。直接插入排序是簡單排序中性能最好的。

4、優化遞歸操作

遞歸對于算法的效率有着很大的影響。快速排序算法有兩次遞歸操作，對我們來說太奢侈了，我們應該減少遞歸的調用，就可以最大程度的提高性能。我們可以利用

尾遞歸

。

什麼是尾遞歸呢？如果一個函數中遞歸形式的調用出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。

當編譯器檢測到一個函數調用是尾遞歸的時候，它就覆寫目前的活躍記錄而不是在棧中去建立一個新的。編譯器可以做到這點，因為遞歸調用是目前活躍期内最後一條待執行的語句，于是當這個調用傳回時棧幀中并沒有其他事情可做，是以也就沒有儲存棧幀的必要了。通過覆寫目前的棧幀而不是在其上重新添加一個，這樣所使用的棧空間就大大縮減了，這使得實際的運作玫率會變得更高。

是以，隻要有可能我就需要将遞歸函數寫成尾遞歸的形式。

5、發揮尾遞歸的優勢：處理小部分的的遞歸

對資料規模較小的部分遞歸，對資料規模較大的部分通過尾遞歸的調用分小。盡量把棧的空間利用起來。

具體優化代碼

public class QuickSort01 {

    public static int MAX_LENGTH_INSERT_SORT = 3;

    public static void main(String[] args) {
        int[] array = {5, 9, 1, 9, 5, 3, 7, 6, 1}; // 待排序數組
        sort(array, 0, array.length - 1);
        print(array);
    }

    /**
     * 快速排序
     *
     * @param array 待排序的數組
     * @param low   數組的起始位址
     * @param high  數組的結束位址
     */
    public static void sort(int array[], int low, int high) {
        // 直到兩個下标相遇，程式結束
        // ------------優化點3：小規模排序使用直接插入排序------------
        if (high - low > MAX_LENGTH_INSERT_SORT) {
            // ------------優化點4：改為尾遞歸------------
            while (low < high) {
                // 查找 k 的位置
                int k = partition(array, low, high);
                // ------------優化點5：處理小部分的的遞歸------------
                if (k - low < high - k) {
                    sort(array, low, k - 1);
                    low = k + 1;
                } else {
                    sort(array, k + 1, high);
                    high = k - 1;
                }
            }
        } else {
            insertSort(array, low, high);
        }
    }

    /**
     * 快速排序，分割的過程
     *
     * @param array 待排序的數組
     * @param low   數組的起始位址
     * @param high  數組的結束位址
     * @return k 值
     */
    public static int partition(int array[], int low, int high) {

        // ------------優化點1：優化選取基準點------------
        selectPoint(array, low, high);

        // 基準點
        int point = array[low];
        // 直到兩個下标相遇，程式結束
        while (low < high) {
            // high 向左移動，直至遇到比point值小的記錄，停止移動
            while (low < high && array[high] >= point) {
                high--;
            }
            // ------------優化點2：将交換改為指派------------
            array[low] = array[high];

            //low 向右移動，直至遇到比point值大的記錄，停止移動
            while (low < high && array[low] <= point) {
                low++;
            }
            // ------------優化點2：将交換改為指派------------
            array[high] = array[low];
        }

        // ------------優化點2：别忘記将 point 填回去------------
        array[low] = point;

        return low;
    }

    /**
     * 優化選取基準點：選取相應區間的開始元素、中間元素和末尾元素。将值大小處在中間的元素放到low位置。
     * @param array 待排序的數組
     * @param low  數組區間的開始位置
     * @param high 數組區間的結束位置
     */
    public static void selectPoint(int[] array, int low, int high) {
        int mid = low + (high - low)/2;
        if (array[low] > array[high]) {
            swap(array, low, high);
        }
        if (array[mid] > array[high]) {
            swap(array, mid, high);
        }
        // 經過前面兩步，最大值已經在 high 位置
        // 下一步将值大小處在中間的元素放到low位置
        if (array[mid] > array[low]) {
            swap(array, mid, low);
        }
    }

    public static void insertSort(int array[], int low, int high) {
        // 注意：low是數組區間的開始，high是數組區間的結束
        // 循環待排序的部分的數列
        // 第一個資料（下标為low的資料）由于插入排序剛開始，有序表中沒有任何記錄，可以直接添加到有序表中
        for (int i = low + 1; i < high + 1; i++) {
            int temp = array[i];
            int j = i;
            // 如果前面的元素小于temp，則向後移
            for (; j > low && array[j - 1] > temp; j--) {
                array[j] = array[j - 1];
            }
            // 前一個元素（array[j - 1]）和後一個元素（array[j]）是相同的
            // 在下一輪時，當array[j - 1]小于或等于temp時，将temp插入array[j]（即上一輪的array[j - 1]）
            array[j] = temp;
        }
    }

    /**
     * 交換數組中兩個元素的位置
     */
    public static void swap(int array[], int low, int high) {
        int temp = array[low];
        array[low] = array[high];
        array[high] = temp;
    }

    /**
     * 列印數組
     */
    public static void print(int array[]) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "   ");
        }
        System.out.println();
    }
}
           

5 1 3 5 9 6