萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

Java 快速排序完整實作:分治法、分區邏輯、遞迴與迭代版本、效能分析

快速排序核心思想

分治法:選取基準 → 分區 → 遞迴排序左右子陣列

  • 平均時間複雜度:O(n log n)
  • 最壞:O(n²) (已排序陣列 + 固定基準)
  • 空間複雜度:O(log n) 遞迴堆疊 (原地排序)
  • 不穩定排序

分區策略比較

策略基準選擇優點缺點
Lomuto最後一個元素簡單易懂重複元素多時效能差、需兩次交換
Hoare第一個元素交換次數少、雙指針實作稍複雜、需額外處理基準位置
三向切分隨機/中位數大量重複元素極快 O(n)程式碼較長
隨機化基準隨機索引期望 O(n log n)、避免最壞需隨機數生成

Lomuto 分區完整實作 (教學標準)

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;
  }
}

Hoare 分區實作 (效能較好)

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);
  }
}

Java 內建排序比較

// 陣列排序
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

總結建議

  1. 學習/面試:掌握 Lomuto/Hoare 分區、隨機化、三向切分、迭代版
  2. 生產環境:直接使用 Arrays.sort() / Collections.sort()
  3. 大量重複鍵值:三向切分或 Java 內建 Dual-Pivot 已優化
  4. 平行處理:大陣列用 Arrays.parallelSort()
  5. 穩定性需求:用 Collections.sort() (TimSort 穩定)
copyright © 萬盛學電腦網 all rights reserved