快速排序演算法原理與C語言高效實現

快速排序核心思想

快速排序採用分治法：從序列挑選基準值，將小於基準者置左、大於者置右（分區操作），基準最終位於正確位置；遞迴對左右子序列排序，直到長度 0 或 1。關鍵在於分區演算法的實現。

分區邏輯（單向掃描法）

1. 假定首元素為基準 res = arr[low]
2. high 向左找第一個 < res 的元素，交換到 low
3. low 向右找第一個 > res 的元素，交換到 high
4. 重複直到 low == high，返回基準最終位置

C語言實現代碼

#include <stdlib.h>

void swap(int arr[], int i, int j) {
    int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}

// 分區：返回基準最終位置
int getPivot(int arr[], int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        swap(arr, low, high);
        while (low < high && arr[low] <= pivot) low++;
        swap(arr, low, high);
    }
    return low;
}

void QSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIdx = getPivot(arr, low, high);
        QSort(arr, low, pivotIdx - 1);
        QSort(arr, pivotIdx + 1, high);
    }
}

void Quick_Sort(int arr[], int low, int high) {
    QSort(arr, low, high - 1);
}

int main() {
    int arr[10];
    for (int i = 0; i < 10; i++) arr[i] = rand() % 33;
    printf("Before sort:\n");
    for (int i = 0; i < 10; i++) printf("%d ", arr[i]);
    Quick_Sort(arr, 0, 10);
    printf("\nAfter sort:\n");
    for (int i = 0; i < 10; i++) printf("%d ", arr[i]);
    system("pause");
    return 0;
}

執行結果

Before sort: 8 20 31 1 29 16 27 21 1 11
After sort: 1 1 8 11 16 20 21 27 29 31

效能與優化重點

常見優化：

• 基準選取： 三數取中（首、中、尾）、隨機基準、九分位數等，避免最壞情況。
• 小區間改用插入排序： 長度 < 10-20 時切換。
• 尾端遞迴消除： 對較大分區遞迴，較小分區迴圈處理，減少堆疊深度。
• 三向切分： 處理大量重複鍵值（Dutch National Flag 問題）。