ALL is Well！

本文為原創(chuàng)，歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處BlogJava。
快速排序的算法思想：
快速排序采用了分治的策略，將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。用遞歸方法解決子問題，然后將這些子問題的解組合為原問題的解。

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

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

假設(shè)我們要寫一個程序?qū)σ延袛?shù)組進(jìn)行排序，簡單起見，設(shè)定待排序數(shù)組為 int[] array = { 4, 2, 1, 7, 5, 3, 8, 6 }。對其用快速排序算法進(jìn)行排序，過程描述如下：
1.根據(jù)已有待排序數(shù)組，取得pivot，我在這里取得pivot的策略就是 取 數(shù)組的第一個數(shù)，這里即為 4。
   tmp = 4；

待排序數(shù)組：黃色底色表示pivot。



2.從后向前移動high，找到第一個小于tmp的數(shù)，則將該數(shù)移動到low的位置。



3.從前向后移動low，找到第一個大于tmp（4）的數(shù)，將其移動到high的位置。


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




  根據(jù)新的pivot進(jìn)行遞歸調(diào)用，將原待排序數(shù)組 分解為兩塊，index區(qū)間分別為0～2，4～7，即以下兩個子數(shù)組
  (并未新建數(shù)組，只是只關(guān)注這個區(qū)間的數(shù)據(jù)，對其進(jìn)行排序，也就是將問題分解為兩個小的子問題，但問題很類似。)
 

這兩個數(shù)組的排序過程這里就不畫了，一樣的過程。

下面來看看實現(xiàn)的代碼，與剛剛的過程描述是符合的：

package com.bz.sort.algorithm;

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

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

    /** *//**
     * 快速排序。
     * @param arr 待排序數(shù)組
     * @param left 關(guān)注的區(qū)間
     * @param right 關(guān)注的區(qū)間
     */
    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為中心將原數(shù)組分解成兩塊，遞歸排序
        sort(arr, left, pivot - 1);
        sort(arr, pivot + 1, right);
    }

    /** *//**
     * 排序并返回新的pivot
     * @param arr 待排序數(shù)組
     * @param left 區(qū)間
     * @param right 區(qū)間
     * @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) {
            // 從后向前遍歷數(shù)組，找到第一個小于arr[pivot]的數(shù)
            while (low < high && tmp < arr[high]) {
                high--;
            }
            arr[low] = arr[high];

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

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

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

測試代碼如下：

package com.bz.sort.algorithm;

import org.junit.Test;

import junit.framework.Assert;

public class QuickSortTest {
    @Test
    public void testSort() {
        int[] array = { 4, 2, 1, 7, 5, 3, 8, 6 };
        QuickSort qs = new QuickSort();
        qs.sort(array);
        for (int i = 0; i < array.length - 1; i++) {
            Assert.assertTrue(array[i] <= array[i + 1]);
        }
    }
}