這個 quick_sort 函數是一個實現快速排序（Quicksort）算法的遞歸函數。快速排序是一種高效的排序算法，通常用于對大規模數據集進行排序。以下是對該函數的詳細解釋：

函數簽名

void quick_sort(int q[], int l, int r)

• q[]：要排序的數組。
• l：數組的左邊界索引。
• r：數組的右邊界索引。

基本思想

快速排序的基本思想是通過選擇一個"基準"元素，將數組劃分為兩個子數組，使得左子數組中的所有元素都小于基準元素，右子數組中的所有元素都大于基準元素。然后遞歸地對兩個子數組進行排序。

函數具體步驟

1. 終止條件：

   if (l >= r) return;
   

   如果左邊界大于或等于右邊界，說明子數組的長度為0或1，此時已經是有序的，直接返回。

2. 初始化指針和基準元素：

   int i = l - 1, j = r + 1, x = q[l + r >> 1];
   

   • i 和 j 分別初始化為左邊界的前一個位置和右邊界的后一個位置。
   • x 是基準元素，通常選擇中間位置的元素（這里使用 (l + r) >> 1 計算中間位置并作為基準）。

3. 劃分過程：

   while (i < j)
   {do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);
   }
   

   • i 向右移動，直到找到一個不小于基準元素的元素。
   • j 向左移動，直到找到一個不大于基準元素的元素。
   • 如果 i 小于 j，則交換 q[i] 和 q[j]。

4. 遞歸調用：

   quick_sort(q, l, j), quick_sort(q, j + 1, r);
   

   • 對左子數組 q[l..j] 進行遞歸排序。
   • 對右子數組 q[j + 1..r] 進行遞歸排序。

代碼解釋

void quick_sort(int q[], int l, int r)
{if (l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

• if (l >= r) return;：遞歸終止條件。如果子數組長度為0或1，直接返回。
• int i = l - 1, j = r + 1, x = q[l + r >> 1];：初始化左右指針和基準元素。
• while (i < j)：進入劃分循環。
  • do i ++ ; while (q[i] < x);：i 向右移動，直到找到一個不小于 x 的元素。
  • do j -- ; while (q[j] > x);：j 向左移動，直到找到一個不大于 x 的元素。
  • if (i < j) swap(q[i], q[j]);：如果 i 小于 j，交換 q[i] 和 q[j]。
• quick_sort(q, l, j), quick_sort(q, j + 1, r);：遞歸排序左、右子數組。

示例

假設輸入數組為 [3, 6, 8, 10, 1, 2, 1]，調用 quick_sort(q, 0, 6)：

1. 初始基準元素為中間值 8，通過劃分將數組變為 [3, 6, 1, 1, 2, 8, 10]，8 左邊是小于 8 的元素，右邊是大于 8 的元素。
2. 遞歸對左子數組 [3, 6, 1, 1, 2] 和右子數組 [10] 進行排序。
3. 最終得到排序后的數組 [1, 1, 2, 3, 6, 8, 10]。

快速排序是一種高效的排序算法，平均時間復雜度為 O(n log n)，但在最壞情況下（如輸入已經有序時）時間復雜度為 O(n^2)。通過合理選擇基準元素，可以在很大程度上避免最壞情況。

測試代碼

#include <iostream>
#include <algorithm>
using namespace std;void quick_sort(int q[], int l, int r)
{if (l >= r)return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){doi++;while (q[i] < x);doj--;while (q[j] > x);if (i < j)swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j + 1, r);
}int main()
{int q[] = {3, 6, 2, 1, 7, 4, 5};quick_sort(q, 0, 6);for (int i = 0; i < 7; i++)cout << q[i] << ' ';return 0;
}