C++ 遞歸函數詳解：快速排序遞歸實現全解析

遞歸函數核心概念

函數直接或間接調用自身。必須包含：
1. 基線條件：終止遞歸
2. 遞歸步驟：將問題縮小為子問題

快速排序遞歸邏輯

1. 選樞軸（通常取首元素 key = a[low]）
2. 雙指針分區：left 從左找 ≥key，right 從右找 ≤key，交換
3. 指針相遇處放置 key
4. 遞歸處理左、右子數組

完整代碼

#include 

void QuickSort(int a[], int low, int high) {
    if (low >= high) return; // 基線條件
    int key = a[low];
    int left = low, right = high;
    while (left < right) {
        while (left < right && a[right] >= key) --right;
        a[left] = a[right];
        while (left < right && a[left] <= key) ++left;
        a[right] = a[left];
    }
    a[left] = key; // 放置樞軸
    QuickSort(a, low, left-1);  // 左子數組
    QuickSort(a, left+1, high); // 右子數組
}

int main() {
    int a[] = {32, 8, 65, 18, 19, 12, 61};
    QuickSort(a, 0, 6);
    for (int i=0; i<7; ++i) printf("%4d", a[i]);
    return 0;
}

遞歸執行流程圖解

QuickSort(0,6) key=32
├─ 分區後：[8,18,19,12] 32 [65,61]
├─ QuickSort(0,3) key=8
│  ├─ 分區：[] 8 [18,19,12]
│  ├─ QuickSort(0,-1) 返回
│  └─ QuickSort(1,3) key=18 ...
└─ QuickSort(5,6) key=65 ...

遞歸深度與棧溢出

• 最壞情況（有序數組）深度 O(n)，可能棧溢出
• 優化：隨機選樞軸、三數取中、小區間改用插入排序
• 尾遞歸優化：編譯器可將尾調用優化為循環

遞歸 vs 迭代

快速排序是遞歸分治的經典教學案例，理解其分區邏輯與遞歸結構，有助於掌握分治算法設計思想。

1. 上一篇文章： LeetCode Linked List Cycle II：找環入口節點
2. 下一篇文章： LeetCode Binary Tree Preorder Traversal：非遞歸前序遍歷

關於C++

UVA 1382 Distant Galaxy：枚举矩形边界最大边上点数

题目大意 N 个点（N≤100），求轴平行矩形，使边界上点数

C++ 輸出數字金字塔：兩種樣式完整代碼

樣式一：對稱遞增遞減金字塔 每行數字從行號遞減至 1 再遞增

Windows Socket 網路程式設計完整入門與範例碼

Windows Socket 概述 Windows Sock

LightOJ 1030 Discovering Gold：洞穴期望黃金 DP

題目描述 1×N 洞穴，起點 1，終點 N。每回合擲 6 面