C語言快速排序算法代碼逐行深度分析：分區邏輯與遞歸結構

標準快速排序實現

void sort(int a[], int size) {
    int i = 0, j = size - 1;
    int pivot = a[0];                 // 基準值

    if (size > 1) {
        while (i < j) {
            // 從右向左找首個 < pivot
            for (; i < j; j--) {
                if (a[j] < pivot) {
                    a[i] = a[j];      // 填左坑
                    break;
                }
            }
            // 從左向右找首個 > pivot
            for (; i < j; i++) {
                if (a[i] > pivot) {
                    a[j] = a[i];      // 填右坑
                    break;
                }
            }
        }
        a[i] = pivot;                 // 基準歸位
        sort(a, i);                   // 遞歸左半
        sort(&a[i+1], size - i - 1);  // 遞歸右半
    }
}

「挖坑填坑」分區過程圖解

初始陣列：[6, 9, 7, 3, 4]，pivot=6，i=0, j=4

最終：[4, 3, 6, 7, 9]，基準 6 歸位，左側 ≤ 6，右側 ≥ 6。

關鍵細節解析

1. 基準值保存：pivot = a[0]，原位置成為第一個坑。
2. 交替掃描：先右後左，每次填坑產生新坑，無需額外交換變量。
3. 終止條件：i == j 時坑位即基準最終位置。
4. 遞歸邊界：size <= 1 直接返回。
5. 指針算術**：&a[i+1] 傳遞右半區首地址，size - i - 1 為右半長度。

常見變體與優化

複雜度與穩定性

• 平均：O(n log n)
• 最壞：O(n²)（已有序 + 固定首元素基準）
• 空間：O(log n) 遞歸棧
• 穩定性：不穩定（相等元素可能交換相對序）

調試建議

在分區循環中打印 i, j, a[i], a[j]，觀察坑位移動軌跡，是理解快排的最佳方式。

1. 上一篇文章： C語言可變參數函數實現原理：va_list、va_start、va_arg、va_end 深度解析
2. 下一篇文章： C語言模擬默認參數：宏技巧、重載模擬與實戰方案

C 語言入門

C 語言型別轉換完全指南：強制轉型、整數提升、算術轉換與避坑實戰

C 語言型別轉換完全指南 型別轉換是 C 語言靜態型別系統中

C語言動態內存管理核心：malloc/free 與指標的協作機制

動態內存管理的核心地位 動態內存管理配合指標，實現 C/C+

C 語言判斷語句詳解：if/else/switch/三元運算符

C 語言判斷語句詳解：if/else/switch/三元運算

C 語言文件操作詳解（三）：讀寫操作全面指南

C 語言文件操作詳解（三）：讀寫操作全面指南 接續前文文件打