堆排序：以完全二叉樹結構實現 O(n log n) 高效選擇

編輯：關於C語言

從選擇排序到堆排序的演進

簡單選擇排序每輪需掃描整個未排序區間尋找最值，比較結果未保留，導致大量重複比較。堆排序引入堆資料結構——一種滿足特定順序關係的完全二叉樹，將「尋找最值」優化為 O(1) 操作，並以 O(log n) 維護結構，整體達到 O(n log n) 時間複雜度。

核心概念：堆與大頂堆

完全二叉樹：除最後一層外每層節點滿，最後一層節點靠左排列。
大頂堆：任意節點值 ≥ 其左右子節點值。根節點即為全樹最大值。
陣列映射：索引 i 節點的左子節點 2i+1，右子節點 2i+2，父節點 (i-1)/2（0-based 索引）。

演算法三大步驟

建堆：從最後一個非葉節點 n/2 - 1 向前遞歸下沉，構建大頂堆。
排序：重複 n-1 次：交換堆頂（最大值）與堆尾元素，堆大小 -1，對新堆頂下沉調整恢復堆性質。
結果：陣列由小到大有序。

C 語言完整實現代碼

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

void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void HeapAdjust(int arr[], int s, int m) {
    int temp = arr[s];
    for (int j = 2 * s + 1; j < m; j = 2 * j + 1) {
        if (j + 1 < m && arr[j] < arr[j + 1]) j++;      // 取較大子節點
        if (temp >= arr[j]) break;                    // 滿足堆性質
        arr[s] = arr[j];                              // 子節點上移
        s = j;                                        // 繼續向下檢查
    }
    arr[s] = temp;
}

void HeapSort(int arr[], int n) {
    // 1. 建初始大頂堆
    for (int i = n / 2 - 1; i >= 0; i--)
        HeapAdjust(arr, i, n);
    // 2. 依次取出堆頂並重建
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        HeapAdjust(arr, 0, i);
    }
}

void print(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序前：\n"); print(arr, n);
    HeapSort(arr, n);
    printf("排序後：\n"); print(arr, n);
    return 0;
}

效能特性分析

指標	數值/特性
時間複雜度	O(n log n)（最好/最壞/平均一致）
空間複雜度	O(1)
穩定性	不穩定
比較次數	~ 2n log₂n
適用場景	大規模資料、實時系統（確定性時間）、嵌入式（無遞歸/額外空間）