C語言最大堆排序演算法完整解析與實作

最大堆排序：原理、實作與程式碼詳解

堆排序是利用堆這一資料結構設計的排序演算法，屬於選擇排序的一種。最大堆排序透過建立最大堆，每次將堆頂最大元素與陣列末尾交換，縮小堆範圍並重新調整，最終得到升序序列。

核心輔助函數

定義節點索引運算：

int left(int i) { return 2 * i; }
int right(int i) { return 2 * i + 1; }
int parent(int i) { return i / 2; }

關鍵操作：maxHeapify

維護最大堆性質，確保父節點大於子節點：

void maxHeapify(int *arr, int length, int i) {
    if (arr == 0 || i < 0) return;
    int l = left(i), r = right(i), largest = i;
    if (l < length && arr[l] > arr[largest]) largest = l;
    if (r < length && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        maxHeapify(arr, length, largest); // 遞迴調整受影響子樹
    }
}

建立最大堆

從最後一個非葉節點向前遞迴調用 maxHeapify：

void buildMaxHeap(int *arr, int length) {
    if (arr == 0 || length <= 0) return;
    for (int i = length / 2 - 1; i >= 0; i--)
        maxHeapify(arr, length, i);
}

堆排序主流程

重複將堆頂與當前末尾交換，縮小堆大小並重建：

void maxHeapSort(int *arr, int length) {
    if (arr == 0 || length <= 0) return;
    int temp;
    for (int i = length; i > 1; i--) {
        temp = arr[i - 1];
        arr[i - 1] = arr[0];
        arr[0] = temp;
        buildMaxHeap(arr, i - 1);
    }
}

測試主程式

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

複雜度與特性

• 時間複雜度：O(n log n) - 建堆 O(n)，n 次調整各 O(log n)
• 空間複雜度：O(1) - 原地排序
• 不穩定排序：相同值元素相對位置可能改變

最大堆排序適合大量資料排序，且無需額外記憶體空間，是系統級程式常用的高效演算法。