排序演算法 | 快速排序

快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），簡稱快排，一種排序演算法，最早由東尼·霍爾提出。在平均狀況下，排序n個項目要O(n log n)（大O符號）次比較。在最壞狀況下則需要 O(n²)次比較，但這種狀況並不常見。事實上，快速排序 Θ(n log n)通常明顯比其他演算法更快，因為它的內部迴圈（inner loop）可以在大部分的架構上很有效率地達成。

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的2個子序列，然後遞迴地排序兩個子序列。

步驟為：

挑選基準值：從數列中挑出一個元素，稱為「基準」（pivot），
分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（與基準值相等的數可以到任何一邊）。在這個分割結束之後，對基準值的排序就已經完成，
遞迴排序子序列：遞迴地將小於基準值元素的子序列和大於基準值元素的子序列排序。

遞迴到最底部的判斷條件是數列的大小是零或一，此時該數列顯然已經有序。

選取基準值有數種具體方法，此選取方法對排序的時間效能有決定性影響。

使用快速排序法對一列數字進行排序的過程：

原地（In-place）分割版本的快速排序：

實作範例(Java)

public static void quickSort(int[] arr, int left, int right) {
    int l = left; // 左下標
    int r = right; // 右下標
    int pivot = arr[(left + right) / 2]; // 找到中間的值
    // 將比pivot小的值放在其左邊，比pivot大的值放在其右邊
    while (l < r) {
        // 在pivot左邊尋找，直至找到大於等於pivot的值才退出
        while (arr[l] < pivot) {
            l += 1; // 將l右移一位
        }
        // 在pivot右邊尋找，直至找到小於等於pivot的值才退出
        while (arr[r] > pivot) {
            r -= 1; // 將r左移一位
        }
        if (l >= r) {
            // 左右下標重合，尋找完畢，退出循環
            break;
        }
        // 交換元素
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;

        //倘若發現值相等的情況，則沒有比較的必要，直接移動下標即可

        // 如果交換完後，發現arr[l]==pivot，此時應將r左移一位
        if (arr[l] == pivot) {
            r -= 1;
        }
        // 如果交換完後，發現arr[r]==pivot，此時應將l右移一位
        if (arr[r] == pivot) {
            l += 1;
        }
    }
    // 如果l==r，要把這兩個下標錯開，否則會出現無限遞歸，導致棧溢出的情況
    if (l == r) {
        l += 1;
        r -= 1;
    }
    // 向左遞歸
    if (left < r) {
        quickSort(arr, left, r);
    }
    // 向右遞歸
    if (right > l) {
        quickSort(arr, l, right);
    }
}

public static void main(String[] args) {
    int[] arr = {
        3,
        44,
        38,
        5,
        47,
        15,
        36,
        26,
        27,
        2,
        46,
        4,
        19,
        50,
        48
    };
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}

結果：

1	[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

快速排序的實現原理很簡單，就是將原數組分成兩部分，然後以中間值為標準，比它小的就放其左邊，比它大的就放其右邊，然後在左右兩邊又以相同的方式繼續排序。
所以在代碼實現過程中，首先要創建兩個移動的變量，一個從最左邊開始往右移動，一個從最右邊開始往左移動，通過這兩個變量來遍歷左右兩部分的元素。當發現左邊有大於中間數的元素，右邊有小於中間數的元素，此時就進行交換。當兩個變量重合也就是相等的時候遍歷結束，然後左右兩部分作遞歸處理。