分治法:選取基準 → 分區 → 遞迴排序左右子陣列
| 策略 | 基準選擇 | 優點 | 缺點 |
|---|---|---|---|
| Lomuto | 最後一個元素 | 簡單易懂 | 重複元素多時效能差、需兩次交換 |
| Hoare | 第一個元素 | 交換次數少、雙指針 | 實作稍複雜、需額外處理基準位置 |
| 三向切分 | 隨機/中位數 | 大量重複元素極快 O(n) | 程式碼較長 |
| 隨機化基準 | 隨機索引 | 期望 O(n log n)、避免最壞 | 需隨機數生成 |
public class QuickSort {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1); // 左半部
quickSort(arr, pivotIndex + 1, high); // 右半部
}
}
/**
* Lomuto 分區:基準為 arr[high]
* 回傳基準最終位置
*/
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1; // 小於基準區域的右邊界
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
// 將基準放到正確位置 (i+1)
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
private static int partitionHoare(int[] arr, int low, int high) {
int pivot = arr[low]; // 選第一個
int i = low - 1;
int j = high + 1;
while (true) {
// 從左找 >= pivot
do { i++; } while (arr[i] < pivot);
// 從右找 <= pivot
do { j--; } while (arr[j] > pivot);
if (i >= j) return j; // 交會點
swap(arr, i, j);
}
}
// 遞迴呼叫調整:quickSort(arr, low, p) 和 quickSort(arr, p+1, high)
// 注意:Hoare 回傳的 j 不一定是基準最終位置
private static final Random RAND = new Random();
private static int partitionRandomized(int[] arr, int low, int high) {
// 隨機選擇基準並交換到 high
int randomIdx = low + RAND.nextInt(high - low + 1);
swap(arr, randomIdx, high);
return partition(arr, low, high); // 再用標準 Lomuto
}
/**
* Dijkstra 三向切分
* 回傳 [lt, gt] 範圍為等於基準的區間
*/
private static void quickSort3Way(int[] arr, int low, int high) {
if (low >= high) return;
int pivot = arr[low];
int lt = low; // arr[low..lt-1] < pivot
int gt = high; // arr[gt+1..high] > pivot
int i = low + 1; // arr[lt..i-1] == pivot
while (i <= gt) {
int cmp = Integer.compare(arr[i], pivot);
if (cmp < 0) swap(arr, lt++, i++);
else if (cmp > 0) swap(arr, i, gt--);
else i++;
}
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
}
public static void quickSortIterative(int[] arr) {
if (arr == null || arr.length < 2) return;
// 手動堆疊模擬遞迴
Deque stack = new ArrayDeque<>();
stack.push(new int[]{0, arr.length - 1});
while (!stack.isEmpty()) {
int[] range = stack.pop();
int low = range[0], high = range[1];
if (low < high) {
int p = partitionRandomized(arr, low, high);
// 先壓入較大分區,再壓入較小分區 → 堆疊深度 O(log n)
if (p - 1 - low > high - (p + 1)) {
stack.push(new int[]{low, p - 1});
stack.push(new int[]{p + 1, high});
} else {
stack.push(new int[]{p + 1, high});
stack.push(new int[]{low, p - 1});
}
}
}
}
public class ArrayUtils {
public static void print(int[] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) System.out.print(", ");
}
System.out.println("]");
}
public static boolean isSorted(int[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i-1] > arr[i]) return false;
}
return true;
}
public static int[] randomArray(int n, int bound) {
Random r = new Random();
return r.ints(n, 0, bound).toArray();
}
}
// 測試
public class Test {
public static void main(String[] args) {
int[] arr = ArrayUtils.randomArray(20, 100);
System.out.println("原始:"); ArrayUtils.print(arr);
QuickSort.sort(arr);
System.out.println("排序後:"); ArrayUtils.print(arr);
System.out.println("驗證: " + ArrayUtils.isSorted(arr));
// 效能測試
int[] big = ArrayUtils.randomArray(1_000_000, 1_000_000);
long start = System.nanoTime();
QuickSort.sort(big);
System.out.printf("100萬筆耗時: %.2f 秒%n", (System.nanoTime() - start) / 1e9);
}
}
// 陣列排序
Arrays.sort(arr); // 基本型別:Dual-Pivot Quicksort (Java 7+)
Arrays.parallelSort(arr); // 多執行緒並行排序 (Java 8+)
// List 排序
Collections.sort(list); // TimSort (合併排序變體),穩定
list.sort(Comparator.naturalOrder()); // Java 8+
// 效能:Arrays.sort 經過高度優化,實務上優於手寫 QuickSort
Arrays.sort() / Collections.sort()Arrays.parallelSort()Collections.sort() (TimSort 穩定)