【演算法】快速排序及優化
- 2020 年 3 月 28 日
- 筆記
一、荷蘭國旗問題
在講快速排序前，我們先來看看荷蘭國旗問題。題目如下：
給定一個數組arr，和一個數num，請把 小於num的數放在數組的左邊， 等於num的數放在數組的中間， 大於num的數放在數組的 右邊。 要求額外空間複雜度O(1)，時間複雜度O(N)， 例如： 對於數組3,5,4,5,8,1,9，以5進行分割 輸出：3 4 1 5 5 9 8
其實，這就是快排的partition過程，通過三個指針，index，less，more進行的，初始less=左邊界-1，more=右邊界+1，說明一開始不存在less域和more域： 1）若arr[index] < num，less域增加，即less++，然後index和less位置的數交換後，index++繼續指向下一個數 2）若arr[index] > num，more域增加，即more++，然後index和more的數交換後，繼續判斷交換後arr[index]和num的關係 3）若arr[index] == num，index++繼續指向下一個數，不坐任何處理 4）重複以上過程，直至index==more
大致過程圖：
程式碼實現
public static int[] partition(int[] arr, int l, int r, int num) { int less = l - 1; int more = r + 1; int index = l; // 循環至index到more相等 while (index < more) { if (arr[index] < num) { // 擴大less域 swap(arr, ++less, index++); }else if (arr[index] > num){ // 擴大more域，且交換後，繼續判斷當前index的數和num的關係 swap(arr, --more, index); }else { index++; } } int[] result = {less + 1, more - 1}; // 返回相等區間開始和結束的索引值 return result; } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
二、經典快速排序
快排其實是冒泡排序的改進，其演算法思路如下： 1）在數組中選取一個數作為基準元素 2）分區，把小於基準的數放左邊，大於基準的數放右邊 3）遞歸，對左右兩個分區重複以上步驟
在網上找了一張圖，如下所示（侵刪）：
實現程式碼
public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int l, int r) { if (l >= r) { return; } int p = partition(arr, l, r); quickSort(arr, l, p - 1); quickSort(arr, p + 1, r); } public static int partition(int[] arr, int l, int r) { // 取左邊第一個數為基準 int pivot = arr[l]; int i = l; int j = r; while(i != j) { // 從右邊找第一個小於基準的數 while(arr[j] >= pivot && i < j) { j--; } // 從左邊找第一個大於基準的數 while(arr[i] <= pivot && i < j) { i++; } if (i < j) { swap(arr, i, j); } } // 將基準歸位 swap(arr, l, j); // 返回基準的位置 return j; }
三、改進的快速排序
回顧經典的快速排序，可以優化的地方有兩個：
1）基準的選取，若每次取數組的第一個作為基準，則可能出現基準是數組中最小的數，造成了多餘的計算。因此，基準的選取可以進行隨機選擇 2）分區返回的邊界，回顧荷蘭國旗問題，分區時，可以發現基準可以是中間一片區域，而不是一個數，因此，分區時，返回的不在是基準的位置，而是基準的左邊界和右邊界，那麼下次劃分子問題時，就可以減少交換的次數了。
程式碼實現
public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // quickSort2(arr, 0, arr.length - 1); quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int l, int r) { if (l < r) { // 從l~r中選一個數，放在r作為基準 swap(arr, l + (int) (Math.random() * (r - l + 1)), r); int[] p = partition(arr, l, r); quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); } } // 分割 public static int[] partition(int[] arr, int l, int r) { int less = l - 1; int more = r; int index = l; // 循環至index到more相等 while (index < more) { if (arr[index] < arr[r]) { // 擴大less域 swap(arr, ++less, index++); }else if (arr[index] > arr[r]){ // 擴大more域，且交換後，繼續判斷當前index的數和num的關係 swap(arr, --more, index); }else { index++; } } // 將基準歸位，基準取的是最右邊的數 swap(arr, more, r); int[] result = {less + 1, more}; // 返回相等區間開始和結束的索引值 return result; }
