資料結構：C語言堆排序（建堆、調整、原地排序）

算法流程

1. 建大頂堆：從最後一個非葉節點 length/2-1 向前遞迴下沉調整。
2. 排序：堆頂（最大值）與末尾交換，堆尺寸 -1，重新下沉調整新堆頂。重複至尺寸 1。

完整程式碼

#include 
#include 

void HeapAdjust(int arr[], int i, int length) {
    int child, temp;
    for (; 2*i+1 < length; i = child) {
        child = 2*i + 1;
        if (child < length-1 && arr[child+1] > arr[child]) child++;
        if (arr[i] < arr[child]) {
            temp = arr[i]; arr[i] = arr[child]; arr[child] = temp;
        } else break;
    }
}

void HeapSort(int arr[], int length) {
    for (int i = length/2 - 1; i >= 0; --i) HeapAdjust(arr, i, length);
    for (int i = length-1; i > 0; --i) {
        // 交換堆頂與末尾
        arr[i] ^= arr[0]; arr[0] ^= arr[i]; arr[i] ^= arr[0];
        HeapAdjust(arr, 0, i);  // 縮小堆範圍
    }
}

int main() {
    int num[] = {98,48,777,63,57,433,23,1112,1};
    int n = sizeof(num)/sizeof(num[0]);
    printf("原始："); for(int i=0;i

關鍵細節

2*i+1、2*i+2 為左右子節點索引（0-based）。
下沉調整 HeapAdjust 保證父節點 ≥ 子節點。
交換使用 XOR 無暫存變數（教學示範），實務建議用 temp。
不穩定排序，時間 O(n log n)，空間 O(1)。


執行結果
原始：98 48 777 63 57 433 23 1112 1
排序：1 23 48 57 63 98 433 777 1112