快速排序遞歸缺少終止條件導致棧溢出的修復

問題代碼缺陷

原代碼 quicksort(k, s, t) 缺少 if (s >= t) return; 終止判斷，導致遞歸無限深入直到棧溢出，無輸出結果。

修正代碼

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a; *a = *b; *b = temp;
}

void quicksort(int k[], int s, int t) {
    if (s >= t) return; // 關鍵終止條件
    int i = s, j = t + 1;
    while (1) {
        do i++; while (!(k[i] >= k[s] || i == t));
        do j--; while (!(k[j] <= k[s] || j == s));
        if (i < j) swap(&k[i], &k[j]);
        else break;
    }
    swap(&k[s], &k[j]);
    quicksort(k, s, j - 1);
    quicksort(k, j + 1, t);
}

int main() {
    int k[10] = {2,5,6,3,7,8,0,9,12,1};
    for (int i = 0; i < 10; i++) printf("%d ", k[i]);
    printf("\n");
    quicksort(k, 0, 9);
    for (int i = 0; i < 10; i++) printf("%d ", k[i]);
    printf("\n");
    return 0;
}

關鍵點

• 遞歸函數必須有明確的基線條件（Base Case）。
• 分區邏輯採用 Hoare 分區方案，i 從左向右找 ≥ 基準，j 從右向左找 ≤ 基準。
• 調試技巧：在遞歸入口打印 s, t 觀察收斂過程。