堆排序算法 C 語言完整實現與核心邏輯解析

算法概述

堆排序是一種基於二叉堆結構的選擇排序，時間複雜度穩定為 O(n log n)，空間複雜度 O(1)，不穩定。本文提供完整、可編譯運行的 C 語言實現，並逐步拆解關鍵函數邏輯。

完整源碼

#include \
#include \

void swap(int A[], int i, int j) {\
    int tmp = A[i];\
    A[i] = A[j];\
    A[j] = tmp;\
}\

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, largest, i);\
        Max_Heap(A, heap_size, largest);\
    }\
}\

void buildHeap(int A[], int length) {\
    for (int i = length / 2 - 1; i >= 0; i--) {\
        Max_Heap(A, length, i);\
    }\
}\

void heapSort(int A[], int length) {\
    buildHeap(A, length);\
    for (int i = length - 1; i >= 0; i--) {\
        swap(A, i, 0);\
        Max_Heap(A, i, 0);\
    }\
}\

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

核心函數詳細解析

1. swap：元素交換

標準三步交換，作為堆調整的基本操作。

2. Max_Heap：維護大頂堆性質

• 參數：數組 A、當前堆大小 heap_size、待調整節點索引 i。
• 計算左右子節點索引 l=2i+1、r=2i+2。
• 在 i、l、r 中找出最大值索引 largest。
• 若 largest != i，交換並遞歸向下調整受影響的子樹。

3. buildHeap：構建初始大頂堆

• 從最後一個非葉節點 length/2 - 1 開始，逆序調用 Max_Heap。
• 自底向上保證每個子樹滿足堆性質，最終整個數組成為大頂堆。

4. heapSort：排序主流程

1. 調用 buildHeap 構建大頂堆，此時 A[0] 為最大值。
2. 將堆頂 A[0] 與當前堆尾 A[i] 交換，最大值歸位。
3. 堆大小減 1（i），對新堆頂調用 Max_Heap 恢復堆性質。
4. 重複步驟 2-3 直到堆大小為 1，數組有序。

運行結果

0	1	2	3	4	5	6	7	8	9

關鍵特性總結

常見錯誤與調試技巧

1. 索引越界：l < heap_size 而非 l <= heap_size，因索引從 0 開始。
2. 遞歸深度：最大深度 log₂n，棧溢出風險極低；極大數據可改寫為迭代版。
3. 測試用例：空數組、單元素、已排序、逆序、重複元素，驗證邊界條件。

堆排序以其穩定的性能表現和極低的空間開銷，成為嵌入式系統、標準庫實現（如 glibc qsort 退化時）的首選算法之一。掌握其 C 語言實現，有助於深入理解數據結構與算法工程化。