交換排序演算法之快速排序

八種排序演算法可以按照如圖分類，本文主要介紹快速排序，

交換排序

所謂交換，就是序列中任意兩個元素進行比較，根據比較結果來交換各自在序列中的位置，以此達到排序的目的，

快速排序

快速排序的思想很簡單，就是先把待排序的陣列拆成左右兩個區間，左邊都比中間的基準數小，右邊都比基準數大，接著左右兩邊各自再做同樣的操作，完成后再拆分再繼續，一直到各區間只有一個數為止，

舉個例子，現在我要排序 4、9、5、1、2、6 這個陣列，一般取首位的 4 為基準數，第一次排序的結果是：

2、1、4、5、9、6

可能有人覺得奇怪，2 和 1 交換下位置也能滿足條件，為什么 2 在首位？這其實由實際的代碼實作來決定，并不影響之后的操作，

以 4 為分界點，對 2、1、4 和 5、9、6 各自排序，得到

1、2、4、5、9、6

不用管左邊的 1、2、4 了，將 5、9、6 拆成 5 和 9、6，再排序，至此結果為

1、2、4、5、6、9

為什么把快排劃到交換排序的范疇呢？因為元素的移動也是靠交換位置來實作的，

演算法實作

大體思路已經有了，接下來就是具體實作，

相信大家已經看出來了，演算法的實作需要用到遞回（拆磁區間之后再對每個區間作同樣的操作），所有關于演算法實作的闡述僅以一次排序為例，

基準數一般取陣列首位的數，而最侄訓準數是要放在中間位置的，我們使用一個臨時變數 stard 來保存選取的基準值，其余元素根據比較結果決定是否交換位置，

我們分別得到陣列的首元素和尾元素的下標，作為頭指標和尾指標，先尾指標開始，如果對應的數比基準值大，尾指標向前移動，直到遇到比基準值小的為止，此時將尾指標對應的數值賦給頭指標的位置，輪到頭指標，如果對應的數比基準值小，頭指標向后移動，直到遇到比基準值大的為止，此時頭指標對應的數值賦給尾指標的位置，再到尾指標，再到頭指標，直到頭尾指標重合為止，此時將 stard 的值賦給指標重合處下標，一趟排序完成，

用 Java 實作的快速排序如下

/**
 * 快速排序
 *
 * @param arr 待排序的整型陣列
 * @param start 起始下標
 * @param end 末尾下標
 */
public static void quicksort(int[] arr, int start, int end) {

    if (start < end) {
        // 把陣列中第 0 個數字作為基準數
        int stard = arr[start];
        //  記錄需要排序的下標
        int low = start;
        int high = end;
        // 回圈找到比基準數大的數和比基準數小的數
        while (low < high) {
            // 右邊的數字比基準數大
            while (low < high && arr[high] >= stard) {
                high--;
            }
            // 使用右邊的數替換左邊的數
            arr[low] = arr[high];
            // 左邊的數字比基準數小
            while (low < high && arr[low] <= stard) {
                low++;
            }
            // 使用左邊的數替換右邊的數
            arr[high] = arr[low];
        }
        // 把標準值賦給下標重合的位置
        arr[low] = stard;
        // 處理所有小的數字
        quicksort(arr, start, low);
        // 處理所有大的數字
        quicksort(arr, low + 1, end);
    }
}

我還在網上看到另一種實作方式，個人覺得第二種雖然更符合交換這一概念，但在交換次數和空間消耗上有一丟丟遜色，

/**
 * 快速排序
 *
 * @param arr 待排序的整型陣列
 * @param start 起始下標
 * @param end 末尾下標
 */
public static void quicksort(int[] arr, int start, int end) {

    if (start < end) {
        // 把陣列中第 0 個數字作為基準數
        int stard = arr[start];
        //  記錄需要排序的下標
        int low = start;
        int high = end;
        // 回圈找到比基準數大的數和比基準數小的數
        while (low < high) {
            // 右邊的數字比基準數大
            while (low < high && arr[high] >= stard) {
                high--;
            }
            // 左邊的數字比基準數小
            while (low < high && arr[low] <= stard) {
                low++;
            }
            // 相等繼續回圈
            if (low < high && arr[low] == arr[high]) {       
                low++;            
            } else {
               	// 左邊的數和右邊的數交換位置
                int temp = arr[low];                
                arr[low] = arr[high];                
                arr[high] = temp;            
            }  
        }
        // 處理所有小的數字
        quicksort(arr, start, low);
        // 處理所有大的數字
        quicksort(arr, low + 1, end);
    }
}

快速排序穩定性

快速排序是不穩定的演算法，只要舉出一個實體，即可說明它的不穩定性，所謂不穩定，即序列中如果存在多個相同的元素，經過排序后它們的順序位置發生變化，就是不穩定的，

假設在數列中存在 a[i]=a[j]，若在排序之前，a[i]在a[j]前面，并且排序之后，a[i] 仍然在 a[j] 前面，則這個排序演算法是穩定的，

快速排序性能

快速排序的一次劃分演算法從兩頭交替搜索，直到 low 和 high 重合，因此其時間復雜度是 O(n)，這里要注意時間復雜度的定義，常數是忽略不計的，可能第二次劃分只有原長度的一半，即 (1/2)*n，但還是認為是 O(n)，

整個快速排序演算法的時間復雜度與劃分的趟數有關，理想的情況是，每次劃分所選擇的中間數恰好將當前序列幾乎等分，第一次劃分變成兩個陣列，第二次劃分變成四個陣列，最后一定會變成 n 個陣列，劃分次數即是 log2n 次，便可得到長度為1的子表，這樣，整個演算法的最優時間復雜度為 O(nlog2n)，

最壞的情況是，每次所選的中間數是當前序列中的最大或最小元素，這使得每次劃分所得的子表中一個為空表，另一子表的長度為原表的長度減一，這樣，長度為 n 的資料表的快速排序需要經過 n 趟劃分，使得整個排序演算法的時間復雜度為 O(n2)，

快速排序的平均時間復雜度也是 O(nlogn)，

從空間性能上看，盡管快速排序需要的輔助空間也就是個常數級 O(1) ，但用到了遞回，每一次劃分都需要開辟一塊輔助空間，

因此最優的情況下空間復雜度為 O(log2n) ，最差的情況下空間復雜度為 O( n ) ，

標籤：其他

上一篇：0621. Task Scheduler (M)

下一篇：樹狀陣列1