C 語言堆排序演算法錯誤分析：sink 邏輯與迴圈邊界修正

原始碼問題

void abc(int a[], int e, int f) { // sink 下沉
    int i = e, j = 2*i, t = a[i];
    while (j+1 <= f) {
        if (a[j+1] > a[j]) j++;
        if (a[j] > a[i]) a[i] = a[j];
        i = j; j = 2*i;
    }
    a[i] = t;
}

主程式建堆與排序迴圈均有邊界錯誤，導致輸出結果錯誤。

核心錯誤點

1. sink 過程未完成交換：僅將較大子節點值上移 a[i] = a[j]，未將暫存值 t 下沉至最終位置，導致資料遺失。
2. 建堆起始索引錯：for (p=n/2; p>=1; p--) 若陣列從 1 起算正確，但主程式 a[15] 實際用 1..14，n=14 正確。
3. 排序迴圈邊界：for (p=14; p>=1; p--) 應為 p>1，否則 p=1 時 abc(a,1,1) 無意義。
4. 陣列下標從 1 開始：C 語言慣例從 0 起算，若強制從 1 起算需分配 n+1 大小並忽略 a[0]。

修正版 sink（下沉）

void sink(int a[], int k, int n) {
    int temp = a[k];
    for (int i = 2*k; i <= n; i *= 2) {
        if (i < n && a[i] < a[i+1]) i++; // 取較大子節點
        if (temp >= a[i]) break;         // 父節點已足夠大
        a[k] = a[i];                     // 子節點上移
        k = i;                           // 繼續下沉
    }
    a[k] = temp;                         // 放入最終位置
}

完整堆排序範本（0-based 索引）

void heapSort(int a[], int n) {
    // 建堆
    for (int i = n/2 - 1; i >= 0; i--) sink(a, i, n-1);
    // 排序
    for (int i = n-1; i > 0; i--) {
        swap(a[0], a[i]);
        sink(a, 0, i-1);
    }
}

調試建議

• 使用 IDE 斷點單步執行，觀察陣列每輪變化。
• 參考標準教材（如《資料結構》嚴蔚敏版）堆排序圖解與不變式分析。
• 測試資料含重複值、已排序、逆序、單元素等邊界情況。

掌握 不變式：以 k 為根的子樹已為大頂堆，是寫正確 sink 的關鍵。