ALL is Well！

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

快速排序的程序的一般過程可簡單描述為：
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() {
        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]);
        }
    }
}