快速排序的思想

任取一個元素作為樞軸，然后想辦法把這個區間劃分為兩部分，小于等于樞軸的放左邊，大于等于樞軸的放右邊

然后遞歸處理左右區間，直到空或只剩一個

具體動畫演示詳見?

?Lomuto 分區方案（單邊掃描法）

public static void quickSort(int[] nums){subSort(nums, 0, nums.length-1);
}private static void subSort(int[] nums, int low, int high){if(low < high){int pos = partition(nums, low, high);subSort(nums, low, pos-1);subSort(nums, pos+1, high);}
}private static int partition(int[] nums, int low, int high){int pivot = nums[high];int i = low-1;for(int j=low; j<high; j++){if(nums[j] <= pivot){i++;int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}// 將pivot放到正確的位置int temp = nums[i + 1];nums[i + 1] = nums[high];nums[high] = temp;return i+1;
}

進一步優化上述代碼

優化點：小數組時改用插入排序

當待排序數組較小的時候，快速排序的遞歸開銷會比插入排序更大

public static void quickSort(int[] nums){subSort(nums, 0, nums.length-1);}private static void subSort(int[] nums, int low, int high) {if (low < high) {// 小數組改用插入排序（閾值可調整，通常 10~20）if (high - low < 10) {insertionSort(nums, low, high);return;}int pos = partition(nums, low, high);subSort(nums, low, pos - 1);subSort(nums, pos + 1, high);}}private static void insertionSort(int[] nums, int low, int high) {for (int i = low + 1; i <= high; i++) {int key = nums[i];int j = i - 1;while (j >= low && nums[j] > key) {nums[j + 1] = nums[j];j--;}nums[j + 1] = key;}}private static int partition(int[] nums, int low, int high){int pivot = nums[high];int i = low-1;for(int j=low; j<high; j++){if(nums[j] <= pivot){i++;int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}// 將pivot放到正確的位置int temp = nums[i + 1];nums[i + 1] = nums[high];nums[high] = temp;return i+1;}

優化點：三數取中法選擇pivot避免最壞情況

如果pivot選擇最左或最右，在已排序或接近排序的數組上會導致最壞的情況O（）

public static void quickSort(int[] nums){subSort(nums, 0, nums.length-1);}private static void subSort(int[] nums, int low, int high) {if (low < high) {// 小數組改用插入排序（閾值可調整，通常 10~20）if (high - low < 10) {insertionSort(nums, low, high);return;}int pos = partition(nums, low, high);subSort(nums, low, pos - 1);subSort(nums, pos + 1, high);}}private static void insertionSort(int[] nums, int low, int high) {for (int i = low + 1; i <= high; i++) {int key = nums[i];int j = i - 1;while (j >= low && nums[j] > key) {nums[j + 1] = nums[j];j--;}nums[j + 1] = key;}}private static int partition(int[] nums, int low, int high){// 三數取中法選擇 pivotint mid = low + (high - low) / 2;if (nums[low] > nums[mid]) swap(nums, low, mid);if (nums[low] > nums[high]) swap(nums, low, high);if (nums[mid] > nums[high]) swap(nums, mid, high);// 將中位數放到 nums[high]swap(nums, mid, high);int pivot = nums[high];int i = low-1;for(int j=low; j<high; j++){if(nums[j] <= pivot){i++;swap(nums, i, j);}}// 將pivot放到正確的位置swap(nums, i + 1, high);return i+1;}private static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

優化點：尾遞歸優化避免棧溢出

public static void quickSort(int[] nums){subSort(nums, 0, nums.length-1);}private static void subSort(int[] nums, int low, int high) {// 小數組改用插入排序if (high - low < 10) {insertionSort(nums, low, high);return;}// 尾遞歸優化while (low < high) {int pos = partition(nums, low, high);if (pos - low < high - pos) {subSort(nums, low, pos - 1);low = pos + 1;} else {subSort(nums, pos + 1, high);high = pos - 1;}}}private static void insertionSort(int[] nums, int low, int high) {for (int i = low + 1; i <= high; i++) {int key = nums[i];int j = i - 1;while (j >= low && nums[j] > key) {nums[j + 1] = nums[j];j--;}nums[j + 1] = key;}}private static int partition(int[] nums, int low, int high){// 三數取中法選擇 pivotint mid = low + (high - low) / 2;if (nums[low] > nums[mid]) swap(nums, low, mid);if (nums[low] > nums[high]) swap(nums, low, high);if (nums[mid] > nums[high]) swap(nums, mid, high);// 將中位數放到 nums[high]swap(nums, mid, high);int pivot = nums[high];int i = low-1;for(int j=low; j<high; j++){if(nums[j] <= pivot){i++;swap(nums, i, j);}}// 將pivot放到正確的位置swap(nums, i + 1, high);return i+1;}private static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

優化點：雙軸快排

java的Arrays.sort對小數組用插入排序，對大數組用雙軸快排（比單軸更快）

雙軸快排的基本思路：

1. 選取兩個 pivot：

• • pivot1 = nums[left]（較小的 pivot）
  • pivot2 = nums[right]（較大的 pivot）
  • 確保 pivot1 ≤ pivot2（否則交換）

1. 分區：

• • [left, i)：< pivot1
  • [i, k)：≥ pivot1 && ≤ pivot2
  • [k, j]：未處理區間
  • (j, right]：> pivot2

1. 遞歸處理三個子數組：

• • [left, i-1]（小于 pivot1 的部分）
  • [i, j]（介于 pivot1 和 pivot2 之間的部分）
  • [j+1, right]（大于 pivot2 的部分）

public static void quickSort(int[] nums){dualPivotQuickSort(nums, 0, nums.length-1);}private static void dualPivotQuickSort(int[] nums, int left, int right) {if (left >= right) return;// 確保 pivot1 ≤ pivot2if (nums[left] > nums[right]) {swap(nums, left, right);}int pivot1 = nums[left];int pivot2 = nums[right];int i = left + 1;  // [left+1, i) 存儲 < pivot1 的元素int k = left + 1;  // [i, k) 存儲 ≥ pivot1 && ≤ pivot2 的元素int j = right - 1; // (j, right-1] 存儲 > pivot2 的元素while (k <= j) {if (nums[k] < pivot1) {swap(nums, i, k);i++;k++;} else if (nums[k] <= pivot2) {k++;} else {swap(nums, k, j);j--;}}// 將 pivot1 和 pivot2 放到正確位置swap(nums, left, i - 1);swap(nums, right, j + 1);// 遞歸處理三個子數組dualPivotQuickSort(nums, left, i - 2);   // < pivot1dualPivotQuickSort(nums, i, j);          // pivot1 ≤ x ≤ pivot2dualPivotQuickSort(nums, j + 2, right);  // > pivot2}private static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}