快速排序 C++ 完整實現：從演算法原理到工程化代碼

演算法複雜度回顧

空間複雜度細說：每層遞迴佔用 O(1) 堆疊幀。最佳情況 (每次對半分割) 深度 log₂n → O(log n)；最壞情況 (每次只分離 1 個元素) 深度 n → O(n)。

核心演算法流程

QUICKSORT(A, p, r)
    if p < r then
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q-1)
        QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
    x = A[r]           // 基準值 (最後一個元素)
    i = p - 1
    for j = p to r-1
        if A[j] <= x
            i = i + 1
            swap A[i] <-> A[j]
    swap A[i+1] <-> A[r]
    return i + 1       // 基準最終位置

單趟分區過程圖解

陣列：`7 3 5 9 8 5 1 10 4 6`，基準 `x=6`

初始: [7, 3, 5, 9, 8, 5, 1, 10, 4, 6]
j=0: 7>6  無動作
j=1: 3≤6  i=0 swap A[0]↔A[1] → [3, 7, 5, 9, 8, 5, 1, 10, 4, 6]
j=2: 5≤6  i=1 swap A[1]↔A[2] → [3, 5, 7, 9, 8, 5, 1, 10, 4, 6]
j=3: 9>6  無動作
j=4: 8>6  無動作
j=5: 5≤6  i=2 swap A[2]↔A[5] → [3, 5, 5, 9, 8, 7, 1, 10, 4, 6]
j=6: 1≤6  i=3 swap A[3]↔A[6] → [3, 5, 5, 1, 8, 7, 9, 10, 4, 6]
j=7: 10>6 無動作
j=8: 4≤6  i=4 swap A[4]↔A[8] → [3, 5, 5, 1, 4, 7, 9, 10, 8, 6]
結束: swap A[5]↔A[9] → [3, 5, 5, 1, 4, 6, 9, 10, 8, 7]
返回 q=5，左側 ≤6，右側 >6

工程化 C++ 實現

類別架構設計

class BaseSort {
public:
    BaseSort() = default;
    virtual void sort() = 0;
    virtual ~BaseSort() = default;
};

class QuickSort : public BaseSort {
public:
    QuickSort(int* array, int len) : Array(array), len(len) {}
    
    void sort() override {
        quicksort(Array, 0, len - 1);
    }
    
private:
    int partition(int* arr, int start, int end);
    void quicksort(int* arr, int start, int end);
    
    int* Array;
    int len;
};

核心邏輯實現

void QuickSort::quicksort(int* arr, int start, int end) {
    if (start < end) {
        int mid = partition(arr, start, end);
        // 尾端遞迴優化：先處理較小分區，限制堆疊深度
        if (mid - start < end - mid) {
            quicksort(arr, start, mid - 1);
            quicksort(arr, mid + 1, end);
        } else {
            quicksort(arr, mid + 1, end);
            quicksort(arr, start, mid - 1);
        }
    }
}

int QuickSort::partition(int* arr, int start, int end) {
    int pivot = arr[end];
    int i = start - 1;
    
    for (int j = start; j < end; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[end]);
    
    #ifdef DEBUG
    printArray(arr, len, "PartitionResult");
    #endif
    
    return i + 1;
}

測試驗證

void printArray(int* arr, int len, const char* tag) {
    printf("%s: ", tag);
    for (int i = 0; i < len; ++i) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int a[] = {7, 3, 2, 9, 8, 5, 1, 10, 4, 6};
    int len = sizeof(a) / sizeof(a[0]);
    
    printArray(a, len, "Original");
    
    QuickSort qs(a, len);
    qs.sort();
    
    printArray(a, len, "Sorted");
    
    // 驗證有序性
    for (int i = 1; i < len; ++i) {
        if (a[i-1] > a[i]) {
            printf("ERROR: Not sorted at index %d\n", i);
            return 1;
        }
    }
    printf("Verification: PASSED\n");
    return 0;
}

關鍵優化技巧 (生產級)

1. 三數取中法選基準：`median-of-three` 避免有序陣列最壞情況
2. 小區間插入排序：`n < 16` 時切換至插入排序，減少遞迴開銷
3. 尾端遞迴消除：迴圈處理較大分區，遞迴處理較小分區，堆疊深度限制在 O(log n)
4. 三向切分：大量重複鍵值時 (Dutch National Flag)，單趟分出 `<` `=` `>` 三區
5. 隨機化基準：隨機選擇基準或打亂陣列，概率保證 O(n log n)

標準庫替代方案

#include 
#include 

std::vector v = {7,3,2,9,8,5,1,10,4,6};
std::sort(v.begin(), v.end());  // Introsort: 快排 + 堆排 + 插排混合
// 保證 O(n log n) 最壞情況，高度優化

實務開發優先使用 `std::sort`，手寫快排僅為教學、面試、特殊約束場景 (如嵌入式無 STL、自定義比較器極其複雜)。