排序之快速排序(下)

前言

　　路漫漫其修遠兮，吾将上下而求索！

　　github：https://github.com/youzhibing

　　碼雲(gitee)：https://gitee.com/youzhibing

　　快排上是可以進行優化的，那麼可以進行哪些優化了，是不是和你想的一樣了？ 我們往下看

優化樞紐值的選取

　　如果我們選取的pivotKey是處于整個序列的中間位置，那麼我們可以将整個序列分成小數集合和大數集合了。但注意，我剛才說的是“如果……是中間”， 那麼假如我們選取的pivotkey不是中間數如何呢？比如我們用到的數組{9,1,5,8,3,7,4,6,2}，由代碼“pivotkey=arr[low];”知道，我們應該選取9作為第一個樞軸pivotKey。此時，經過一輪 “pivot=partition(arr,1,9);”轉換後，它隻是更換了9與2的位置，并且傳回9給pivot，整個系列并沒有實質性的變化。

　　就是說，代碼“pivotkey=arr[low];”變成了一個潛在的性能瓶頸。排序速度的快慢取決于arr[low]的關鍵字處在整個序列 的位置，arr[low]太小或者太大，都會影響性能(比如第一例子中的5就是一個中間數，而第二例子的9就是一個相對整個序列過大的數)。因為在現實中， 待排序的系列極有可能是基本有序的，此時，總是固定選取第一個關鍵字（其實無論是固定選取哪一個位置的關鍵字）作為首個樞軸就變成了極為不合理的作法。

        改進辦法，有人提出，應該随機獲得一個low與high之間的數rnd，讓它的關鍵字arr[rnd]與arr[low]交換，此時就不容易出現這樣的情況。這被稱為随機選取樞軸法。應該說，這在某種程度上，解決了對于基本有序的序列快速排序時的性能瓶頸。不過，随機就有些撞大運的感覺，萬一沒撞成功，随機到了依然是很小或很大的關鍵字怎麼辦呢？

　　再改進，于是就有了三數取中（median-of-three）法。即取三個關鍵字先進行排序，将中間數作為樞軸，一般是取左端、右端和中間三個數，

也可以随機選取。這樣至少這個中間數一定不會是最小或者最大的數，從機率來說，取三個數均為最小或最大數的可能性是微乎其微的，是以中間數位于較為中間的

值的可能性就大大提高了。由于整個序列是無序狀态，随機選取三個數和從左中右端取三個數其實是一回事，而且随機數生成器本身還會帶來時間上的開銷，是以随機生成不予考慮。

　　我們來看看取左端、右端和中間三個數的實作代碼，我們來看看新的partition方法。

/**
     * 尋找樞紐值的下标，并傳回
     *     交換arr[low...high]中的元素，移動樞紐值到正确的位置
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static int partition(int[] arr, int low, int high) {
        //從第一、中間、最後三個元素中選取第二大的
        int m = low + (high-low)/2;
        if (arr[low] > arr[high]){
            swap(arr,low,high);        /* 交換左端與右端資料，保證左端較小 */
        }
        if (arr[m] > arr[high]){
            swap(arr,high,m);        /* 交換中間與右端資料，保證中間較小 */
        }
        if (arr[m] > arr[low]){
            swap(arr,m,low);        /* 交換中間與左端資料，保證左端較小 */
        }
        
        int pivotValue = arr[low];                        // 選取arr[low]當作樞紐值
        // 從兩端向中間掃描，使樞紐值移動到正确的位置
        while(low < high){
            while(low<high && arr[high]>=pivotValue){
                high --;
            }
            swap(arr,low,high);                         // 将比樞紐值小的記錄交換到低端
            while(low<high && arr[low]<=pivotValue){
                low ++;
            }
            swap(arr,low,high);                            // 将比樞紐值大的記錄交換到高端
        }
        return low;
    }      

　　這樣就保障樞紐值就有一定的合理性了，當然，如果數列特别大的話，可以進行九數取中（median-of-nine），它是先從數組中分三次取樣，每次取三個數，三個樣品各取出中數，然後從這三個中數當中再取出一個中數作為樞軸。

優化不必要的交換

　　直接上代碼

/**
     * 尋找樞紐值的下标，并傳回
     *     交換arr[low...high]中的元素，移動樞紐值到正确的位置
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static int partition(int[] arr, int low, int high) {
        //從第一、中間、最後三個元素中選取第二大的
        int m = low + (high-low)/2;
        if (arr[low] > arr[high]){
            swap(arr,low,high);        /* 交換左端與右端資料，保證左端較小 */
        }
        if (arr[m] > arr[high]){
            swap(arr,high,m);        /* 交換中間與右端資料，保證中間較小 */
        }
        if (arr[m] > arr[low]){
            swap(arr,m,low);        /* 交換中間與左端資料，保證左端較小 */
        }
        
        int pivotValue = arr[low];                        // 選取arr[low]當作樞紐值
        // 從兩端向中間掃描，使樞紐值移動到正确的位置
        while(low < high){
            while(low<high && arr[high]>=pivotValue){
                high --;
            }
            arr[low] = arr[high];                         // 将比樞紐值小的記錄交換到低端
            while(low<high && arr[low]<=pivotValue){
                low ++;
            }
            arr[high]=arr[low];                            // 将比樞紐值大的記錄交換到高端
        }
        arr[low] = pivotValue;
        return low;
    }      

優化小序列時的排序方案

　　如果數組非常小，其實快速排序反而不如直接插入排序來得更好（直接插入是簡單排序中性能最好）。其原因在于快速排序用到了遞歸操作，在大量資料排序時，這點性能影響相對于它的整體算法優勢而言是可以忽略的，但如果數組隻有幾個記錄需要排序時，用快速排序效率反而更低，需要改進下qSort方法。

/**
     * 對序列arr中的子序列arr[low..high]作快速排序
     * @param arr
     * @param low
     * @param high
     */
    private static void qSort(int[] arr, int low, int high) {
        int pivotKey;
        if(high-low > 7){
            // 找到樞紐值的位置，此時arr[low,pivotKey-1]都小于(大于)arr[pivotKey],arr[pivotKey+1...high]都大于(小于)arr[pivotKey]
            pivotKey = partition(arr,low,high);
            qSort(arr,low,pivotKey-1);                    // 對arr[low...pivotKey-1]進行快速排序
            qSort(arr,pivotKey+1,high);                    // 對arr[pivotKey+1...high]進行快速排序
        } else {
            strainghtInsertSort(arr,low,high);
        }
    }
    /**
     * 對序列arr[low...high]a進行直接插入排序
     * @param arr
     * @param low
     * @param high
     */
    private static void strainghtInsertSort(int[] arr, int low, int high) {
        for(int i=low+1; i<=high; i++){                            // 将arr[i]插入到有序清單
            for(int j=i-1; j>=0&&arr[j]>arr[j+1]; j--){            // arr[low...j]是有序清單
                swap(arr,j,j+1);
            }
        }
    }      

　　等等，還可以進行其他方面的優化的，更多的優化就交給各位了!