C 語言遞迴實作陣列排序：快速排序遞迴版完整教學

題目要求

• C 語言
• 遞迴演算法
• 陣列排序
• 不得使用迴圈 (隱含要求：主排序邏輯用遞迴，分區掃描通常仍需迴圈，教學上常允許)

演算法選擇：快速排序

快速排序天然適合遞迴：
`QuickSort(arr, low, high)` → 分區 → 遞迴排序左半部 → 遞迴排序右半部

完整程式碼 (Hoare 分區法，含詳細註解)

#include 
#include 

/**
 * 交換兩個整數
 */
void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

/**
 * Hoare 分區：返回分區點索引
 * 陣列區間 [low, high] (含兩端)
 */
int partition(int arr[], int low, int high) {
    int pivot = arr[low];           // 選第一個元素為基準 (教學簡化，實務建議三數取中)
    int i = low - 1;
    int j = high + 1;

    while (1) {                     // 分區掃描通常用迴圈，純遞迴極繁複且無意義
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(&arr[i], &arr[j]);
    }
}

/**
 * 快速排序遞迴主函數
 * @param arr  待排序陣列
 * @param low  區間起始索引 (含)
 * @param high 區間結束索引 (含)
 */
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 分區
        quickSort(arr, low, pi);             // 遞迴排序左半部
        quickSort(arr, pi + 1, high);        // 遞迴排序右半部
    }
}

/* 輔助：列印陣列 */
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90, 5, 77, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始陣列: ");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    printf("排序後:   ");
    printArray(arr, n);
    return 0;
}

執行流程圖解 (關鍵遞迴樹)

QuickSort(0, 9) pivot=64 → partition → pi=6
├─ QuickSort(0, 6) pivot=12 → pi=2
│  ├─ QuickSort(0, 2) pivot=5 → pi=1
│  │  ├─ QuickSort(0, 1) → sorted
│  │  └─ QuickSort(2, 2) → base case
│  └─ QuickSort(3, 6) pivot=22 → pi=4
│     ├─ QuickSort(3, 4) → sorted
│     └─ QuickSort(5, 6) → sorted
└─ QuickSort(7, 9) pivot=77 → pi=8
   ├─ QuickSort(7, 8) → sorted
   └─ QuickSort(9, 9) → base case

關鍵點說明

• 分區函數用迴圈：`partition` 內的雙指針掃描**極難用純遞迴實作且無教學價值**，教學題目通常默許分區用迴圈、主排序用遞迴
• 基準選擇：固定選 `arr[low]` 易遇最壞情況 O(n²) (已排序陣列)；生產碼用 **三數取中** 或 **隨機基準**
• 尾遞迴優化：對較大分區用迴圈、較小分區遞迴，限制堆疊深度 O(log n)
• 穩定性：快速排序**不穩定**，相等元素相對順序可能改變

純遞迴分區 (僅供理論參考，極不推薦)

// 純遞迴掃描 i, j (教學展示遞迴可替代迴圈，實務不可用)
int partitionRecursive(int arr[], int low, int high, int pivot, int i, int j) {
    if (i >= j) return j;
    if (arr[i] < pivot) return partitionRecursive(arr, low, high, pivot, i+1, j);
    if (arr[j] > pivot) return partitionRecursive(arr, low, high, pivot, i, j-1);
    swap(&arr[i], &arr[j]);
    return partitionRecursive(arr, low, high, pivot, i+1, j-1);
}

其他遞迴排序演算法

總結

**快速排序**是教學展示遞迴排序的最佳範例：邏輯清晰 (`分區 → 遞迴左 → 遞迴右`)、原地排序、平均 O(n log n)。**分區掃描建議保留迴圈**，強行純遞迴會嚴重降低可讀性與效能。生產環境請用 `qsort` (C 標準庫) 或 `std::sort` (C++)。

1. 上一篇文章： C 語言遞迴計算圓周率 π：萊布尼茨級數/尼爾坎塔級數實作 (精確到小數點後 3 位)
2. 下一篇文章： Python 爬取美團外賣商家資料：動態網頁、AJAX 介面分析與反爬應對

程式設計綜合問答

Android Handler 更新 UI 崩潰：findViewById ID 錯誤導致 View 為 null

錯誤現象 Handler 中 ReturnShow.setT

JavaScript 字符串數組轉整型數組：parseInt 映射與箭頭函數寫法

場景 URL 參數 `X#Y` 中 `Y` 為分號分隔數字串

jQuery `click` 與 `attr("onclick")` 事件綁定差異：返回值傳遞機制導致預設行為阻擋成敗

程式碼場景 點一下 點兩下 function retur

Java 函數式編程：將函數作為參數傳遞的演進與實戰

Java 8 前：介面 + 匿名內部類 // 定義函數型介面