程式師世界 >> 編程語言 >> JAVA編程 >> JAVA綜合教程 >> 快速排序(附Java實現和分析)

快速排序(附Java實現和分析)

編輯：JAVA綜合教程

快速排序(附Java實現和分析)

總結一下快速排序，如有錯誤或者不足，歡迎交流討論。

1、快速排序的思路

快速排序和歸並排序的思路很相似，都是采取的分治思想。快速排序通過選擇一個元素，該元素稱為樞軸元素或切分元素，然後將它放到一個合適的位置上，使得它前面的元素不大於它，它後面的元素不小於它，然後將樞軸元素為分界點，兩邊的數組也采取類似的方法，即選取樞軸元素，使得前面的元素不大於它，後面的不小於它，重復進行下去，直到數組裡面只有一個元素（遞歸退出條件）。

2、partition函數

從上述的描述來看，快速排序是需要遞歸的，遞歸地選取樞軸元素進行切分。所以，快速排序的實現重點是切分（partition）函數，即如何實現對於某一切分元素，使得它前面的元素不大於它，後面的不小於它。

3.1 partition函數實現之一

《Algorithm Fourth Edition》上的思路：對於某一樞軸元素，從第一元素開始往後掃描，找到第一個大於它的元素，然後從最後一個元素往前掃描，找到第一個小於它的元素，交換兩個元素。要注意掃描不能出現數組訪問越界，且掃描開始位置不能相交。

package c2Sorting;
/**
 * 快速排序的第一種partition實現
 * @author 小鍋巴
 * @date 2016年4月2日上午10:03:53
 * http://blog.csdn.net/xiaoguobaf
 */
public class QuickSort_1 {
    public static void sort(int[] a){//驅動程序
        sort(a, 0, a.length-1);
    }
    private static void sort(int[] a, int lo, int hi){
        if(lo >= hi)//遞歸退出判斷條件
            return;
        int p = partition(a, lo, hi);//對於某一元素，其本身不必參與遞歸了，因為其所在的位置已經滿足前面的不大於，後面的不小於
        sort(a, lo, p-1);
        sort(a, p+1, hi);
    }
    private static int partition(int[] a, int lo, int hi){
        int left = lo;//左pointer，供掃描用
        int right = hi+1;//右pointer，供掃描用，加1是為了方便掃描的推進，
        int pivot = a[lo];

        while(true){
            while(a[++left] <= pivot)//從lo開始，找到大於pivot的元素，在訪問數組時使用前++更安全，後++可能會發生越界
                if(left == hi)//防止越界
                    break;
            while(a[--right] >= pivot )//從hi開始，找到小於pivot的元素
                if(right == lo)//防止越界
                    break;
            if(left >= right)//左右掃描相交，迭代結束判斷條件，相等的時候說明就是和pivot相等的元素
                break;
            swap(a, left, right);//交換pivot前面大於pivot的元素和pivot後面小於pivot的元素，
            //從這裡可以看出快速排序不穩定，因為兩者之間存在和此時的left或者right相等的元素時，原有的順序就被破壞了
        }
        swap(a, lo, right);//將樞軸元素放到合適的位置
//pivot未交換到合適的位置之前，其他位置的元素都滿足掃描條件了(兩個while裡面為真)，然後再進行一次掃描，掃描條件均為假了，right<=left，right所在位置的元素是不大於pivot的
        return right;//返回切分元素的位置
    }
    private static void swap(int[] a, int i, int j){
        //對於待排序數組中無重復元素時，可以使用異或操作來實現，但是如果有重復的，那麼就不可以，重復的元素會被置為0
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    //單元測試
    public static void main(String[] args) {
        int[] a = {3,4,1,9,3,2,1,6,8,4,7,5};
        sort(a);
        for (int i = 0; i < a.length; i++) 
            System.out.print(" "+a[i]+" ");
    }
}
/**
 * 輸出： 1  1  2  3  3  4  4  5  6  7  8  9 
 * 
 */

3.2 partition函數實現之二

選擇第一個元素為樞軸元素，使用index為當前掃描元素的pointer，storIndex表示樞軸元素後面最後一個小於樞軸元素的pointer，從樞軸元素後面的第一個元素開始從左往右掃描，若當前掃描的元素比樞軸元素小，則交換index與++storIndex的元素（即第一個不小於樞軸元素的元素），進行一趟掃描後，將樞軸元素與storIndex的元素相交換，以將樞軸元素放到合適的位置。
點擊這裡選擇QUICK即可查看動態執行情況。

package c2Sorting;
/**
 * 快速排序的第二種partition實現
 * @author 小鍋巴
 * @date 2016年4月2日下午4:24:47
 * http://blog.csdn.net/xiaoguobaf
 */
public class QuickSort_2 {
    public static void sort(int[] a){
        sort(a, 0, a.length-1);
    }
    private static void sort(int[] a, int lo, int hi){
        if(lo >= hi)
            return;
        int p = partition(a, lo, hi);
        sort(a, lo, p-1);
        sort(a, p+1, hi);
    }
    private static int partition(int[] a, int lo, int hi){
        //我在實現這個partition函數時，感覺訪問數組時使用後++很不安全，搞不好會出現棧溢出、空指針異常
        int index=lo;//當前掃描元素的pointer
        int storIndex = lo;//最後一個小於樞軸元素的pointer
        while(++index <= hi)
            if(a[index] < a[lo])
                swap(a,index,++storIndex);//交換當前元素與第一個不小於樞軸元素的元素
        swap(a,lo,storIndex);//將樞軸元素放到合適的位置
        return storIndex;//返回樞軸元素的位置，即索引
    }
    private static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    //單元測試
    public static void main(String[] args) {
        int[] a = {3,4,1,9,3,2,1,6,8,4,7,5};
        sort(a);
        for (int i = 0; i < a.length; i++) 
            System.out.print(" "+a[i]+" ");
    }
}
/**
輸出：
 1  1  2  3  3  4  4  5  6  7  8  9 
 */

3.3 partition函數實現之三

先將樞軸元素臨時保存起來，從右往左掃描，找到第一個小於樞軸元素的元素，將其放到樞軸元素的位置，然後從左往右掃描，找到第一個大於樞軸元素的元素，將它放到之前第一個小於樞軸元素的位置。

package c2Sorting;
/**
 * 快速排序的第三種partition實現
 * @author 小鍋巴
 * @date 2016年4月2日上午11:39:05
 * http://blog.csdn.net/xiaoguobaf
 */
public class QuickSort_3 {
    public static void sort(int[] a){
        sort(a, 0, a.length-1);
    }
    private static void sort(int[] a, int lo, int hi){
        if(lo >= hi)
            return;
        int p = partition(a, lo, hi);
        sort(a, lo, p-1);
        sort(a, p+1, hi);
    }
    private static int partition(int[] a, int lo, int hi){
        int pivot = a[lo];
        while(lo < hi){
            while(lo < hi && a[hi] >= pivot)
                hi--;
            a[lo] = a[hi];//將從右到左第一小於pivot的元素放到切分元素的位置
            while(lo < hi && a[lo] <= pivot)
                lo++;
            a[hi] = a[lo];//將上一步的位置填充為從左到右第一個大於pivot的元素，此時的lo位置的元素已經不是pivot了
        }
        a[lo] = pivot;//退出時，lo=hi了，此位置即是切分元素應該插入的正確位置
        return lo;
    }

    //單元測試
    public static void main(String[] args) {
        int[] a = {3,4,1,9,3,2,1,6,8,4,7,5};
        sort(a);
        for (int i = 0; i < a.length; i++) 
            System.out.print(" "+a[i]+" ");
    }
}
/**
 輸出：
 1  1  2  3  3  4  4  5  6  7  8  9 
 */

對比三種實現，第二種最不好，相比第一種實現方式，同樣一趟排序，平均情況下其交換次數第二種要比第一種至少多一倍；對比第一種和第三種實現方式，第三種訪問數組的次數要少些，因為第一種采取的是交換，第一種很好理解，實現起來也容易，第三種代碼緊湊些，理解稍微難那麼點。

4、快速排序的改進

4.1 改進樞軸元素的選取

最好情況下，樞軸元素應該是所有元素的平均值，即中值，這樣就更接近歸並排序的切分情況。但是前面的三種partition實現都是選取的第一個元素為樞軸元素，並不能有這個保證，采取三數中值法（三取樣切分），比較lo，mid，hi的大小，選取中間的一個作為樞軸元素。

//三取樣切分
    private static int threeMedium(int[] a, int lo, int mid, int hi){
        return ( a[lo]

其實還可以5取樣切分，那樣會更接近中數，但是過於繁瑣。

`4.2 切換到插入排序`

對於小規模數組，插入排序夠用了，用快速排序多次切分訪問數組的次數將比插入排序多些，還不如用插入排序，故數組規模較小時，切換到插入排序。

最後附上改進後的快速排序Java實現

package c2Sorting;
/**
 * 改進的快速排序
 * @author 小鍋巴
 * @date 2016年4月6日下午10:38:53
 * http://blog.csdn.net/xiaoguobaf
 */
public class QuickSort {
    private static final int CUTOFF = 10;//若數組大小不超過CUTOFF，則切換到插入排序

    public static void sort(int[] a){
        sort(a, 0, a.length-1);
    }   
    private static void sort(int[] a, int lo, int hi){
        if(lo+CUTOFF >= hi){//切換到插入排序，調用插入排序後直接返回
            insertionSort(a);
            return;
        }
        if(lo >= hi)
            return;

        //將三取樣的中數和lo交換
        int m = threeMedium(a, lo, lo+(hi-lo)/2, hi);
        swap(a, m, lo);

        int p = partiton(a, lo, hi);
        sort(a, lo, p-1);
        sort(a, p+1, hi);
    }
    private static int partiton(int[] a, int lo, int hi){
        int pivot = a[lo];
        while(lo < hi){
            while(lo < hi && a[hi] >= pivot)
                hi--;
            a[lo] = a[hi];
            while(lo < hi && a[lo] <= pivot)
                lo++;
            a[hi] = a[lo];
        }
        a[lo] = pivot;
        return lo;
    }
    //三取樣切分
    private static int threeMedium(int[] a, int lo, int mid, int hi){
        return ( a[lo] 0 && a[j] < a[j-1];j--)
                swap(a, j, j-1);
    }
    //單元測試
    public static void main(String[] args) {
        int[] a = {3,4,1,9,3,2,1,6,8,4,7,5};
        sort(a);
        for (int i = 0; i < a.length; i++) 
            System.out.print(" "+a[i]+" ");
    }
}
/**
輸出： 1  1  2  3  3  4  4  5  6  7  8  9 
 */

`5、快速排序的分析`

`5.1 時間復雜度`

快速排序和歸並排序一樣，都使用了遞歸，故可以借助遞歸公式來分析。對於一個未采取插入排序轉換和三取樣切分的快速排序，其運行時間等於兩個子數列排序的時間加上在切分上花費的時間，因為掃描，顯然切分花費的時間與數組規模正相關，故得到地推公式： T(N)= T(i)+T(N-i-1)+cN N為數組規模，i為切分後其中較小一部分的元素個數，c為某一常數

（1）最壞情況樞軸元素始終是最小元素，此時i始終為0，T(0)=T(1)=1，與問題規模無關，在一個地推公式中可以忽略掉，故得到：T(N)=T(N-1)+cN，反復使用該公式，直到N為2，然後累加。（2）最好情況最好情況下，樞軸元素是中數，為簡化分析，假設兩個子數組大小均為原數組的一半，分析和歸並排序類似。（3）平均情況<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxoMyBpZD0="52-空間復雜度">5.2 空間復雜度

在最好情況和平均情況下，sort遞歸的次數是log2N次，partition返回的樞軸元素的位置的局部變量所占用得空間就是log2N次，partition函數裡面的局部變量也是與log2N成正比，即空間復雜度是O(log2N)；在最壞情況下，sort遞歸次數是N^2，此時的空間復雜度將是O(N^2)，但是這樣的概率很小，經過三取樣後就減小了，如果排序前打亂數組，那麼這種情況出現的概率可以忽略不計，證明請參考《Algorithms Fourth Edition》。所以快速排序的空間復雜度為O(log2N)