快速排序演算法深度解析：分區策略、遞歸實現與鏈表優化

快速排序：分治法經典，STL 默認排序引擎

快速排序平均 O(n log n)，原地排序、緩存友好，廣泛用於標準庫實現。本文從分區核心講起，覆蓋陣列版與鏈表版實現。

核心思想：分區

選取一個 基準值，將陣列劃分為「≤ 基準」與「≥ 基準」兩部分，基準值最終位置即為其排序後位置。遞歸處理左右子陣列即完成排序。

陣列版分區實現（雙向掃描法）

int partition(int arr[], int low, int high) {
    int i = low, j = high;
    int pivot = arr[low];  // 選首元素為基準

    while (i < j) {
        while (i < j && arr[j] >= pivot) --j;  // 從右找 < pivot
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) ++i;  // 從左找 > pivot
        arr[j] = arr[i];
    }
    arr[i] = pivot;  // 基準歸位
    return i;        // 返回基準最終位置
}

時間 O(n)，空間 O(1)。基準選擇影響性能：固定首元素遇有序陣列退化 O(n²)；工程上常用「三數取中」或隨機選擇。

快速排序主函數

void quick_sort(int arr[], int low, int high) {
    if (low >= high) return;
    int mid = partition(arr, low, high);
    quick_sort(arr, low, mid - 1);
    quick_sort(arr, mid + 1, high);
}

// 調用入口
quick_sort(arr, 0, n - 1);

合併版（分區+排序一體）

void quick_sort(int arr[], int low, int high) {
    if (low >= high) return;
    int i = low, j = high, pivot = arr[low];
    while (i < j) {
        while (i < j && arr[j] >= pivot) --j;
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) ++i;
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    quick_sort(arr, low, i - 1);
    quick_sort(arr, i + 1, high);
}

單鏈表快速排序：指標交換避免數據搬移

鏈表無法隨機訪問，但分區時只需調整指標，無需移動節點數據。以首節點為基準，維護 mid 指向「≤ 基準」區域尾部：

typedef struct ListNode { int val; struct ListNode *next; } ListNode;

void qsort(ListNode *head, ListNode *end) {
    if (head == end || head == NULL) return;
    ListNode *mid = head, *p;
    for (p = head->next; p != end; p = p->next) {
        if (p->val > head->val) continue;  // 屬於右區，跳過
        mid = mid->next;
        swap(&p->val, &mid->val);          // 僅交換值，或調整指標
    }
    swap(&head->val, &mid->val);           // 基準歸位
    qsort(head, mid);
    qsort(mid->next, end);
}

// 調用：qsort(head, NULL);

優勢：無需額外空間，指標操作天然適合鏈表結構。

性能與優化總結

C++ STL std::sort 通常採用 Introsort：快排 + 堆排遞歸深度限制 + 小陣列插入排序，保證最壞 O(n log n)。