堆排序算法原理與學生成績管理系統實戰應用

排序算法概覽

排序是數據處理基石。按時間複雜度分類：

• O(n²)：插入、冒泡、選擇排序，適合小規模數據。
• O(n log n)：快速排序、堆排序、歸並排序，適合大規模數據。

堆排序以 原地排序、不穩定、最壞情況 O(n log n) 見長，無需額外內存，適合內存受限環境。

堆排序核心原理

1. 堆的定義與性質

• 完全二叉樹：除最後一層外節點滿，最後一層靠左排列。
• 順序存儲映射：數組下標從 1 開始，節點 i 的左子 2i、右子 2i+1、父節點 i/2。
• 大根堆：每個節點 ≥ 子節點，根節點為最大值。
• 小根堆：每個節點 ≤ 子節點，根節點為最小值。

2. 排序流程

1. 建堆：從最後一個非葉節點 n/2 向前遞歸 篩選，構建大根堆。
2. 輸出與重建：交換堆頂（最大值）與末尾元素，堆尺寸 -1，對新根篩選恢復堆序。重複 n-1 次得升序序列。

3. 關鍵操作：篩選

void Sift(RecordNode r[], int low, int high) {
    int i = low, j = 2*i;
    RecordNode tmp = r[i];
    while (j <= high) {
        if (j < high && r[j].key < r[j+1].key) ++j;  // 取較大子節點
        if (tmp.key >= r[j].key) break;               // 滿足堆序
        r[i] = r[j];  // 子節點上移
        i = j; j = 2*i;
    }
    r[i] = tmp;
}

實戰：學生成績排名系統

場景描述

輸入：n 名學生，每條記錄含 考號、分數。要求按分數降序輸出排名，同分同名次。

數據結構設計

struct Student {
    int id;       // 考號
    double score; // 分數
    int rank;     // 名次（排序後計算）
};

完整堆排序實現

void HeapSort(Student arr[], int n) {
    // 1. 建立大根堆（按 score）
    for (int i = n/2; i >= 1; --i)
        Sift(arr, i, n);

    // 2. 反復輸出堆頂並重建
    for (int i = n; i > 1; --i) {
        swap(arr[1], arr[i]);       // 最大值移至末尾
        Sift(arr, 1, i-1);          // 剩餘元素重建堆
    }
    // 現在 arr[1..n] 為升序，需逆序或調整比較方向得降序
}

名次計算邏輯

void ComputeRanks(Student arr[], int n) {
    int rank = 1;
    for (int i = n; i >= 1; --i) {  // 從最高分遍歷
        if (i < n && arr[i].score != arr[i+1].score)
            rank = n - i + 1;         // 分數變化，名次 = 已處理人數 + 1
        arr[i].rank = rank;
    }
}

圖示演示（9 名學生）

算法複雜度分析

• 時間：建堆 O(n)，n-1 次篩選每次 O(log n)，總 O(n log n)（最好/平均/最壞一致）。
• 空間：O(1) 原地排序，僅需常數臨時變量。
• 穩定性：不穩定，相同鍵值元素相對位置可能改變。

工程應用建議

1. 數據量 < 50 時，插入排序常更快（常數因子小）。
2. 需穩定排序時改用歸並排序或 std::stable_sort。
3. C++ 實戰直接用 std::make_heap、std::sort_heap 或 std::sort（內部混合快排/堆排/插排）。
4. 海量數據外部排序可結合歸並與堆（優先隊列）實現 K 路歸並。