C 語言遞歸實現插入排序：指針偏移與遞歸參數修正

原始代碼問題

void insert_sort(int *arr) {
    no_rec += 1;
    int key = *(arr + 1); // 固定偏移 1，未隨遞歸深度變化
    int j = no_rec;
    while (j > 0 && *(arr + j - 1) > key) { ... }
    if (no_rec < N - 1) insert_sort(arr + 1); // 指針前移，但 key 取值邏輯未同步
}

關鍵缺陷：key 固定取 arr+1，未根據遞歸層數 no_rec 動態調整；遞歸調用 arr+1 導致數組起始位置前移，但 j 計算基於全局 no_rec，索引混亂。

修正版代碼

#include <stdio.h>
#define N 5
int no_rec = 0;

void insert_sort(int *arr) {
    no_rec += 1;
    int key = *(arr + no_rec); // 關鍵修正：根據遞歸深度取待插入元素
    int j = no_rec;
    while (j > 0 && *(arr + j - 1) > key) {
        *(arr + j) = *(arr + j - 1);
        j--;
    }
    *(arr + j) = key;
    if (no_rec < N - 1) {
        insert_sort(arr); // 傳遞原數組首址，靠 no_rec 控制進度
    }
}

int main() {
    int arr[N] = {5, 3, 4, 6, 1};
    insert_sort(arr);
    for (int i = 0; i < N; i++) printf("%d ", arr[i]);
    return 0;
}

關鍵修正點

1. key = *(arr + no_rec)：第 k 次遞歸處理第 k 個元素 (0 基準下第 k 個)。
2. 遞歸調用 insert_sort(arr) 傳遞數組首址不變，靠全局/靜態變量 no_rec 記錄進度，避免指針偏移導致索引計算錯亂。
3. 也可改為傳遞當前處理長度 insert_sort(arr, len)，無需全局變量，更純粹。

無全局變量版本

void insert_sort_rec(int *arr, int n) { // 排序前 n 個元素
    if (n <= 1) return;
    insert_sort_rec(arr, n - 1); // 先排好前 n-1 個
    int key = arr[n - 1];
    int j = n - 2;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}