堆排序算法 C 語言完整實現與解析

算法原理回顧

堆排序利用最大堆（或最小堆）特性，分兩階段：建堆將無序數組調整為堆結構；排序反覆交換堆頂與末尾元素，縮小堆規模並重新調整，最終得到有序序列。時間複雜度 O(n log n)，空間複雜度 O(1)，不穩定排序。

完整代碼實現

#include <stdio.h>
#include <stdlib.h>

// 交換數組兩個元素
void swap(int A[], int i, int j) {
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

// 向下調整以 i 為根的子堆，維持最大堆性質
void Max_Heap(int A[], int heap_size, int i) {
    int l = 2 * i + 1;      // 左子節點
    int r = 2 * i + 2;      // 右子節點
    int largest = i;        // 假設當前節點最大

    if (l < heap_size && A[l] > A[largest]) largest = l;
    if (r < heap_size && A[r] > A[largest]) largest = r;

    if (largest != i) {
        swap(A, i, largest);
        Max_Heap(A, heap_size, largest); // 遞歸調整受影響子樹
    }
}

// 自底向上構建最大堆
void buildHeap(int A[], int length) {
    // 最後一個非葉節點索引 = length/2 - 1
    for (int i = length / 2 - 1; i >= 0; --i) {
        Max_Heap(A, length, i);
    }
}

// 堆排序主流程
void heapSort(int A[], int length) {
    buildHeap(A, length);           // 1. 建堆
    for (int i = length - 1; i >= 0; --i) {
        swap(A, i, 0);              // 2. 堆頂(最大)與末尾交換
        Max_Heap(A, i, 0);          // 3. 縮小堆規模並調整新堆頂
    }
}

int main() {
    int A[] = {9, 8, 1, 6, 5, 4, 3, 2, 7, 0};
    int n = sizeof(A) / sizeof(A[0]);
    
    heapSort(A, n);
    
    printf("排序結果: ");
    for (int i = 0; i < n; ++i)
        printf("%d ", A[i]);
    printf("\n");
    return 0;
}

關鍵點解析

1. 建堆起始索引

length/2 - 1 是最後一個非葉節點，葉節點天然滿足堆性質，無需調整。

2. Max_Heap 遞歸調整

比較父節點與左右子節點，若子節點更大則交換，並遞歸向下調整被交換的子節點，確保子樹重新滿足堆性質。

3. 排序階段縮小邊界

每輪將當前最大值（堆頂）換至未排序區末尾，堆規模 i 遞減，調整範圍同步縮小，已排序區在數組尾部自然增長。

運行結果

排序結果: 0 1 2 3 4 5 6 7 8 9

優化方向

• 迭代版 Max_Heap 避免遞歸開銷
• 支持泛型（通過 void* + 比較函數指針）
• 引入哨兵優化邊界判斷

總結

堆排序是原地、O(n log n) 最壞情況保證的排序算法，適合內存受限、需穩定性能場景。理解「建堆-交換-調整」三部曲是掌握其精髓的關鍵。