天天看點
傳回

快速排序

文章目錄

    • @[toc]

#算法思想

通過一趟快速排序将待排序的記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的記錄的關鍵字小，則可分别對這兩部分記錄繼續進行排序，達到整個記錄有序。

實作快速排序算法的核心是partition函數，這個函數的主要目的先選取當中的一個關鍵字（稱為樞軸），然後盡可能将他放在一個位置，使得它左邊的值都比它小，右邊的值比它大。

#實作

快速排序算法實作

public class QuickSort3 {

    public void quickSort(int[] a){
        qSort(a,0,a.length - 1);
        //列印輸出
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    private void qSort(int[] a, int low, int high) {
        int pivot = 0;
        if(low < high){
            //将數組a一分為二
            pivot = partition(a,low,high);
            //對第一部分進行遞歸排序
            qSort(a,low,pivot);
            //對第二部分進行遞歸排序
            qSort(a,pivot + 1,high);
        }
    }

    private int partition(int[] a, int low, int high) {
        //用第一個元素作為樞軸記錄
        int pivotkey = a[low];
        while(low < high){
            //将比樞軸記錄小的交換到低端
            while(low < high && a[high] >= pivotkey){
                high--;
            }
            swap(a,low,high);
            //将比樞軸記錄大的交換到高端
            while(low < high && a[low] <= pivotkey){
                low++;
            }
            swap(a,low,high);
        }
        //傳回樞軸所在的位置
        return low;
    }

    private void swap(int[] a, int low, int high) {
        int temp = a[low];
        a[low] = a[high];
        a[high] = temp;
    }

    public static void main(String[] args) {
        new QuickSort3().quickSort(new int[]{50,10,90,30,70,40,80,60,20});
    }
}

快速排序算法的最優時間複雜度是O(nlogn)，在如下的情況下是最優的：對于一組具有n個關鍵字的記錄，partition函數每次都劃分得很均勻，也就是每次調用partition函數之後，比樞軸小的關鍵字和比樞軸大的關鍵字的數量基本相等。這樣下次調用partition函數的時候所用的時間是上次調用partition函數的兩倍加上比較元素的時間，是以這是最優的情況。

在最壞的情況指的就是每次調用partition函數，隻得到一個比上一次劃分少一個記錄的子序列（因為隻要調用partition函數，必須至少會有一次關鍵字的交換）。由于隻減少了一個關鍵字，是以後面還需要進行n-1次（總共有n個關鍵字）遞歸調用partition函數。是以到最後總共需要比較的次數是∑n−1i=1=n−1+n−2+…+1=n(n−1)2，是以最終的時間複雜度是O(n2)。

在平均的情況下，樞軸的關鍵字應該在k位置(1≤k≤n)。是以最優情況下的時間複雜度是O(nlogn)。

那麼快速排序算法的空間複雜度又是如何呢？最優和平均情況下空間複雜度都是O(logn)，在最壞情況就是n−1次調用，是以空間複雜度是O(n)。

#快速排序算法的優化

##優化一：優化樞軸的選取位置

可以發現我們上面的算法中，樞軸的選取是在第一個位置的，這種選取樞軸位置的最大弊端就是很可能在調用partition函數的時候，隻更換了兩個元素的位置，而其他位置的元素并沒有發生變化，這就是上面分析中提到的最壞的情況，發現導緻這種情況的根源在于選取的樞軸的大小要麼太大要麼太小（因為太大或者太小，high或low的值隻能減小一個位置或者增加一個位置），那麼優化的思路就是讓樞軸既不會太大又不會太小。是以可以采用三數取中法：這種方法就是取三個關鍵字先進行排序，将中間的數作為樞軸，一般是取左端、右端和中間的三個數。這樣排序之後就能基本保證樞軸既不會太大又不會太小。是以我們隻需要修改partition函數如下：

private int partition2(int[] a, int low, int high) {
        //用第一個元素作為樞軸記錄
        int pivotkey = 0;
        //計算數組中間的下标
        int m = low + (high - low)/2;
        if(a[low] > a[high]){
            swap(a, low, high);
        }
        if(a[m] > a[high]){
            swap(a, m, high);
        }
        if(a[low] > a[m]){
            swap(a, low, m);
        }
        pivotkey = a[low];
        while(low < high){
            //将比樞軸記錄小的交換到低端
            while(low < high && a[high] >= pivotkey){
                high--;
            }
            swap(a,low,high);
            //将比樞軸記錄大的交換到高端
            while(low < high && a[low] <= pivotkey){
                low++;
            }
            swap(a,low,high);
        }
        //傳回樞軸所在的位置
        return low;
    }

##優化二：優化不必要的交換

經過上面的優化，我們選取樞軸關鍵字基本是适中大小的，分析樞軸的位置變化過程，從最後一個位置到第一個位置，再到中間那個位置。其實樞軸的目标就是中間那個位置，是以在樞軸到達中間位置的很多交換其實是不必要的。基于這個思路可以繼續優化partition函數如下：

private int partition3(int[] a, int low, int high) {
        //用第一個元素作為樞軸記錄
        int pivotkey = 0;
        //計算數組中間的下标
        int m = low + (high - low)/2;
        if(a[low] > a[high]){
            swap(a, low, high);
        }
        if(a[m] > a[high]){
            swap(a, m, high);
        }
        if(a[low] > a[m]){
            swap(a, low, m);
        }
        pivotkey = a[low];
        //把樞軸元素備份到一個臨時變量中
        int temp = pivotkey;
        while(low < high){
            //将比樞軸記錄小的交換到低端
            while(low < high && a[high] >= pivotkey){
                high--;
            }
            //采用替換而不是交換的方式操作
            a[low] = a[high];
            //将比樞軸記錄大的交換到高端
            while(low < high && a[low] <= pivotkey){
                low++;
            }
            //采用替換而不是交換的方式操作
            a[high] = a[low];
        }
        //将樞軸的值替換回給a[low]
        a[low] = temp;
        //傳回樞軸所在的位置
        return low;
    }

##優化三：優化資料量較小時的排序

在資料量較小的時候使用簡單排序算法反而更簡單，更高效，正如排序數組{2,1,3}的時候，使用簡單排序算法比如直接插入排序隻要兩次比較久搞定了，使用快速排序的話還要劃分，明顯效率低一些。是以我們可以對partition函數進行小數組的優化，有資料認為當數組的長度不大于7的時候算是小數組，也有認為是50，這個其實不是最重要的，這個時候就使用直接插入排序算法就很好用。是以基于這個思路優化代碼如下：

private void qSort(int[] a, int low, int high) {
        int pivot = 0;
        if(low < high && (high - low) > MAX_LENGTH_SORT){
            //MAX_LENGTH_SORT暫且定為50
            //将數組a一分為二
            pivot = partition3(a,low,high);
            //對第一部分進行遞歸排序
            qSort(a,low,pivot);
            //對第二部分進行遞歸排序
            qSort(a,pivot + 1,high);
        }else{
            //小數組的時候使用直接插入排序
            insertSort(a);
        }
    }
           
private void qSort2(int[] a, int low, int high) {
        int pivot = 0;
        if(low < high && (high - low) > MAX_LENGTH_SORT){
            while(low < high){
                //将數組a一分為二
                pivot = partition3(a,low,high);
                //對第一部分進行遞歸排序
                qSort2(a,low,pivot);
                //對第二部分進行尾遞歸,這裡之是以可以将pivot+1賦給low，是因為一/次遞歸結束
                //之後，low的值就沒有用處了。下一次遞歸調用的執行的就是qSort(a,pivot + 1,high)
                low = pivot +1;
            }
        }else{
            //小數組的時候使用直接插入排序
            insertSort(a);
        }
    }
java java基礎 Java入門 Java進階 學習資料
上一篇: 快速排序
下一篇: 快速排序

繼續閱讀