C語言快速排序算法原理與代碼完整實現

什麼是快速排序？

快速排序是對冒泡排序的改進，由 C.A.R. Hoare 於 1962 年提出。它同樣採用分治策略，平均時間複雜度為 O(n log n)，是實際應用中最快的通用排序算法之一。

算法核心思想

1. 選擇一個基準值（通常取第一個元素）
2. 分區：將數組重新排列，使左側元素 ≤ 基準值，右側元素 ≥ 基準值
3. 遞歸：對左右兩個子區間分別進行快速排序
4. 基準值最終位置確定，不再參與後續分區

詳細分區過程（單向掃描法）

以序列 [32, 12, 7, 78, 23, 45] 為例，基準值 key=32：

1. low=0, high=5，從右向左掃描找 <32 的元素：45→23（找到）
2. 將 23 移至 low 位置，low++ → [23, 12, 7, 78, 23, 45]
3. 從左向右掃描找 >32 的元素：12→7→78（找到）
4. 將 78 移至 high 位置，high-- → [23, 12, 7, 78, 23, 78]
5. 重複直到 low >= high，最後將 key 放入 low 位置
6. 第一輪分區結果：[23, 12, 7, 32, 78, 45]，基準值 32 位置確定

完整 C 語言代碼實現

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

#define N 6

int partition(int arr[], int low, int high) {
    int key = arr[low];  // 基準值
    while (low < high) {
        // 從右向左找小於 key 的元素
        while (low < high && arr[high] >= key) high--;
        if (low < high) arr[low++] = arr[high];
        // 從左向右找大於 key 的元素
        while (low < high && arr[low] <= key) low++;
        if (low < high) arr[high--] = arr[low];
    }
    arr[low] = key;  // 基準值歸位
    return low;
}

void quickSort(int arr[], int start, int end) {
    if (start < end) {
        int pos = partition(arr, start, end);
        quickSort(arr, start, pos - 1);
        quickSort(arr, pos + 1, end);
    }
}

int main() {
    int arr[N] = {32, 12, 7, 78, 23, 45};
    
    printf("排序前：\n");
    for (int i = 0; i < N; i++) printf("%d\t", arr[i]);
    
    quickSort(arr, 0, N - 1);
    
    printf("\n排序後：\n");
    for (int i = 0; i < N; i++) printf("%d\t", arr[i]);
    printf("\n");
    return 0;
}

運行結果

排序前：32 12 7 78 23 45
排序後：7 12 23 32 45 78

算法特性分析

常見優化策略

• 隨機選取基準值：避免有序數組退化為 O(n²)
• 三數取中法：取首、中、末三者中位數作為基準值
• 小區間改用插入排序：當區間長度 < 10 時，插入排序更快
• 尾遞歸優化：減少遞歸棧深度

適用場景

快速排序適用於：大數據量、內存敏感、不要求穩定性的通用排序場景。C++ STL 的 std::sort、Java 的 Arrays.sort（基本類型）底層多基於快速排序變體實現。