詳細描述 快速排序 的過程 附Java實現 – JAVA編程語言程序開發技術文章

ALL IS WELL


快速排序的算法思想:
快速排序采用瞭分治的策略,將原問題分解為若幹個規模更小但結構與原問題相似的子問題。用遞歸方法解決子問題,然後將這些子問題的解組合為原問題的解。

快速排序的程序的一般過程可簡單描述為:
1.用統一的方法取得 pivot(軸)。
2.根據pivot 對已有數組進行排序
    1) 將array[pivot]存儲在tmp變量中,作為比較基準。
    以low、high分別從前向後、從後向前遍歷數組
    2) 從後向前遍歷,找到第一個小於tmp的數,將其移動到low的位置。
    3) 從前向後遍歷,找到第一個大於tmp的數,將其移動到high的位置。
    4) 循環2、3步,直到兩指針重疊(即退出循環的條件是 low >= high),將tmp移動到low(此時low與high重合)的位置,並將low返回成為新的pivot。
    5) 根據4步返回的pivot,對已有數組進行劃分,0~pivot-1 和 pivot+1 ~ array.lenght,遞歸1~5步。直到調用退出。

相信對於以上理論大傢一定是耳熟能詳瞭,但理解起來還是比較抽象,下面我就用Excel畫圖簡單的描述一下 快速排序 的過程。

假設我們要寫一個程序對已有數組進行排序,簡單起見,設定待排序數組為 int[] array = { 4, 2, 1, 7, 5, 3, 8, 6 }。對其用快速排序算法進行排序,過程描述如下:
1.根據已有待排序數組,取得pivot,我在這裡取得pivot的策略就是 取 數組的第一個數,這裡即為 4。
   tmp = 4;

待排序數組:黃色底色表示pivot。



2.從後向前移動high,找到第一個小於tmp的數,則將該數移動到low的位置。



3.從前向後移動low,找到第一個大於tmp(4)的數,將其移動到high的位置。


4.然後再向前移動high,試圖找到第一個小於tmp(4)的數,但沒有找到,此時low與high重疊,將tmp的值放入low的位置,並將low作為pivot返回。




  根據新的pivot進行遞歸調用,將原待排序數組 分解為兩塊,index區間分別為0~2,4~7,即以下兩個子數組
  (並未新建數組,隻是隻關註這個區間的數據,對其進行排序,也就是將問題分解為兩個小的子問題,但問題很類似。)
 

這兩個數組的排序過程這裡就不畫瞭,一樣的過程。

下面來看看實現的代碼,與剛剛的過程描述是符合的:package com.bz.sort.algorithm;


public class QuickSort {
    /** *//**
     * 對外調用的方法入口。
     * @param array 待排序數組
     */
    public void sort(int[] array) {
        if (array == null || array.length < 0) {
            throw new RuntimeException(“待排序數組中無數據。”);
        }


        // 排序
        sort(array, 0, array.length – 1);
    }


    /** *//**
     * 快速排序。
     * @param arr 待排序數組
     * @param left 關註的區間
     * @param right 關註的區間
     */
    private void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 取得pivot位置,這裡的策略是取得最小的index,即返回left
        int pivot = findPivot(arr, left, right);
        // 排序並重新計算出pivot
        pivot = partion(arr, left, right, pivot);


        // 以pivot為中心將原數組分解成兩塊,遞歸排序
        sort(arr, left, pivot – 1);
        sort(arr, pivot + 1, right);
    }


    /** *//**
     * 排序並返回新的pivot
     * @param arr 待排序數組
     * @param left 區間
     * @param right 區間
     * @param pivot 軸
     * @return
     */
    private int partion(int[] arr, int left, int right, int pivot) {
        int tmp = arr[pivot];
        int low = left;
        int high = right;
        while (low < high) {
            // 從後向前遍歷數組,找到第一個小於arr[pivot]的數
            while (low < high && tmp < arr[high]) {
                high–;
            }
            arr[low] = arr[high];


            // 從前向後遍歷數組,找到第一個大於arr[pivot]的數
            while (low < high && tmp >= arr[low]) {
                low++;
            }
            arr[high] = arr[low];
        }


        // 此時low與high重合,將tmp的值移動到low的位置
        arr[low] = tmp;
        // 將low當作新的pivot返回
        return low;
    }


    /** *//**
     * 取得排序的軸
     * @param array
     * @return
     */
    protected int findPivot(int[] array, int left, int right) {
        if (array == null || array.length < 0) {
            throw new RuntimeException(“待排序數組中無數據。”);
        }
        // 選擇第一個元素為軸
        return left;
    }
}


 


測試代碼如下:



package com.bz.sort.algorithm;


import org.junit.Test;


import junit.framework.Assert;


public class QuickSortTest {
    @Test
    public void testSort() {

發佈留言