快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按次

方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。最壞情況的時間復(fù)雜度為O(n2)，最好情況時間復(fù)雜度為O(nlog2n)。

假設(shè)要排序的數(shù)組是A[1]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過

程稱為一躺快速排序。一趟快速排序的算法是：
1）設(shè)置兩個變量I、J，排序開始的時候I：=0，J：=N-1；
2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[0]；
3）從J開始向前搜索，找到第一個小于X的值，兩者交換，同時設(shè)置I：=I+1;
4）從I開始向后搜索，找到第一個大于X的值，兩者交換，同時設(shè)置J：=J-1;
5）、重復(fù)第3、4步，直到I=J；

例如：待排序的數(shù)組nums的值分別是：
int[] nums = { 4, 1, 5, 3, 2};

排序的過程是：
第1趟：
2,1,5,3,4, (lo,hi) = (1,4)
2,1,5,3,4, (lo,hi) = (2,4)
2,1,4,3,5, (lo,hi) = (2,3)
2,1,3,4,5, (lo,hi) = (3,3)
此時，數(shù)組分成2部分：{2,1,3},4,{5}
第2趟對{2,1,3}排序：過程同第1趟
第3趟對{5}排序：過程同第1趟

以下是java代碼實現(xiàn)快速排序的過程：


public class Quicksort {
    public static void main(String[] args) {
        int[] nums = { 4, 1, 5, 3, 2};
        // 應(yīng)用快速排序方法
        quickSort(nums, 0, nums.length - 1);
        // 顯示排序后的數(shù)組
        for (int i = 0; i < nums.length; ++i) {
            System.out.print(nums[i] + ",");
        }
    }

    /** 快速排序方法 */
    public static void quickSort(int[] a, int lo0, int hi0) {
        int lo = lo0;
        int hi = hi0;
        if (lo >= hi)
            return;
        // 確定指針方向的邏輯變量
        boolean transfer = true;
        while (lo != hi) {
            if (a[lo] > a[hi]) {
                // 交換數(shù)字
                int temp = a[lo];
                a[lo] = a[hi];
                a[hi] = temp;
                // 決定下標(biāo)移動，還是上標(biāo)移動
                transfer = (transfer == true) ? false : true;
            }
            // 將指針向前或者向后移動
            if (transfer)
                hi--;
            else
                lo++;

            // 顯示每一次指針移動的數(shù)組數(shù)字的變化
            for (int i = 0; i < a.length; ++i) {
                System.out.print(a[i] + ",");
            }
            System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")");
            System.out.println("");

        }
        // 將數(shù)組分開兩半，確定每個數(shù)字的正確位置
        lo--;
        hi++;
        quickSort(a, lo0, lo);
        quickSort(a, hi, hi0);
    }
}