演算法精講：快速排序原理與 C++ 實現

快速排序是最常用的排序演算法，源自冒泡排序，以「快」著稱。最壞情況 O(n²)，平均 O(n log n)，是基於關鍵字比較的內部排序中速度最快者。

核心思想：分治法

1. 分解：在 R[low..high] 中任選一記錄為基準，將無序區劃分為左右兩子區間，左邊關鍵字 ≤ 基準 ≤ 右邊關鍵字，基準歸位。
2. 求解：遞歸對左右子區間快速排序。
3. 合併：因子區間有序，合併步驟為空操作。

白話演示

待排序列：2 2 4 9 3 6 7 1 5
選 2 為基準，雙指針 i、j 兩端掃描：
j 從右找 < 2 的元素（1），放入 i 位置；
i 從左找 > 2 的元素（4），放入 j 位置；
重複直到 i ≥ j，最後將基準填入。
首輪結果：[1] 2 [4 9 3 6 7 5]
遞歸處理左右子區間，最終有序。

C++ 實現代碼

void quickSort(int array[], int start, int end) {
  if (start < end) {
    int key = array[start];
    int low = start, high = end;
    while (low < high) {
      while (low < high && key < array[high]) high--;
      array[low] = array[high];
      while (low < high && key > array[low]) low++;
      array[high] = array[low];
    }
    array[low] = key;
    quickSort(array, start, low - 1);
    quickSort(array, low + 1, end);
  }
}

int main() {
  int array[] = {2, 4, 9, 3, 6, 7, 1, 5};
  quickSort(array, 0, 7);
  for (int i = 0; i < 8; i++) printf("%d\t", array[i]);
  return 0;
}

本文出自「驛落黃昏」博客，轉載請保留出處：https://yiluohuanghun.blog.51cto.com/3407300/1266266