快速排序算法原理與C語言實現詳解

算法核心思想

快速排序是對冒泡排序的改進，採用分治法：

1. 選取一個基準值（通常為首元素）
2. 一趟排序將數據分為兩部分：左側全部 ≤ 基準值，右側全部 ≥ 基準值
3. 遞歸對左右兩部分繼續快速排序
4. 直到子序列長度 ≤ 1，整個序列有序

平均時間複雜度 O(n log n)，最壞 O(n²)（已有序序列），空間複雜度 O(log n)（遞歸棧）。

單趟分區過程詳解

設置兩個指針 i（左）和 j（右）：

1. i=0, j=n-1，基準值 x = a[0]
2. 從右向左掃描 j--，找到第一個 a[j] < x，交換 a[i] 和 a[j]
3. 從左向右掃描 i++，找到第一個 a[i] > x，交換 a[i] 和 a[j]
4. 重複 2-3 直到 i == j，將基準值放入最終位置

優化版C語言實現

#include <stdio.h>
#include <stdlib.h>

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;  // 遞歸終止條件
    
    int pivot = arr[left];  // 基準值
    int i = left, j = right;
    
    while (i < j) {
        // 從右向左找小於基準值的元素
        while (i < j && arr[j] >= pivot) j--;
        if (i < j) arr[i++] = arr[j];  // 移至左側，i右移
        
        // 從左向右找大於基準值的元素
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) arr[j--] = arr[i];  // 移至右側，j左移
    }
    
    arr[i] = pivot;  // 基準值歸位
    quickSort(arr, left, i - 1);   // 遞歸排序左半部
    quickSort(arr, i + 1, right);  // 遞歸排序右半部
}

int main() {
    int arr[] = {2, 4, 9, 3, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, n - 1);
    
    printf("排序結果：");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

代碼關鍵點解析

• 原地排序：無需額外數組空間，通過元素交換/覆蓋實現
• 雙向掃描：i從左、j從右向中間收斂，減少比較次數
• 基準值歸位：循環結束時 i==j 即為基準值最終位置
• 遞歸邊界：left >= right 時返回，處理空/單元素子數組

性能優化建議

1. 三數取中法：選取首、中、尾三元素中位數作為基準，避免有序序列退化為 O(n²)
2. 小數組插入排序：子數組長度 < 10 時改用插入排序，減少遞歸開銷
3. 尾遞歸優化：對較大分區遞歸、較小分區迭代，限制棧深度
4. 隨機化基準：隨機選取基準值，期望時間複雜度穩定在 O(n log n)

參考資源

• CSDN經典講解：快速排序詳細圖解
• 《算法導論》第7章：快速排序數學分析

總結

快速排序是面試、競賽、工程中最常用的內部排序算法。掌握其分區邏輯、遞歸結構、邊界條件是核心。實際工程中推薦使用標準庫qsort（C）或std::sort（C++），它們綜合了快速排序、堆排序、插入排序優點（Introsort），性能穩健可靠。