114 年 國立政治大學資訊管理學系碩士班科技組《資料結構》

演算法定義

1. 建立最小堆：自 $i=\left\lfloor\frac{n}{2}\right\rfloor$ 迭代至 $1$，對每個 $i$ 執行 sift‑down，保證父節點 $\le$ 子節點。時間 $O(n)$。
2. 重複抽取最小值：
   • 取出根節點 (最小鍵)，與最後一個元素交換，堆大小 $n\!\leftarrow\!n-1$。
   • 在新根上執行 sift‑down，恢復堆性質。
   • 重複直到堆空。抽取 $n$ 次，每次 $O(\log n)$，總時間 $O(n\log n)$。

void heapSort(vector<int>& a){
    // build min‑heap
    for(int i=a.size()/2-1;i>=0;--i) siftDown(a,i);
    // extract
    for(int end=a.size()-1; end>0; --end){
        swap(a[0],a[end]);          // 把最小值放到序列尾端
        siftDown(a,0,end);          // 堆大小縮小為 end
    }
    // 現在 a 為遞減序列，若要遞增再 reverse()
}

排序過程（以 1‑索引陣列表示，H 為當前堆，S 為已排好序列）

1. In‑Place Quick Sort（Lomuto 版）

// A: 整數陣列, lo, hi 為索引範圍 (含 hi)
void quickSort(int A[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(A, lo, hi);   // 返回 pivot 最終位置
        quickSort(A, lo, p - 1);
        quickSort(A, p + 1, hi);
    }
}

// Lomuto partition，選最後一個元素為 pivot
int partition(int A[], int lo, int hi) {
    int pivot = A[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; ++j) {
        if (A[j] <= pivot) {
            ++i;
            // swap A[i]、A[j]
            int tmp = A[i]; A[i] = A[j]; A[j] = tmp;
        }
    }
    // 把 pivot 放到正確位置
    ++i;
    int tmp = A[i]; A[i] = A[hi]; A[hi] = tmp;
    return i;          // pivot index
}

時間複雜度
最壞 $O(n^{2})$（退化為線性搜尋），平均 $O(n\log n)$，原地 $O(1)$ 额外空間（遞迴棧深度 $O(\log n)$）。

2. 排序過程示範（示例關鍵集合）

初始陣列
$A = [34,\;7,\;23,\;32,\;5,\;62]$

1. AVL 排序演算法

AVL‑Sort(Keys):
    T ← empty AVL
    for each k in Keys:
        T ← AVL‑Insert(T, k)          // 旋轉保持高度平衡
    return Inorder(T)                // 中序走訪即為遞增序列

插入、旋轉、刪除均保證 $O(\log n)$，整體排序 $O(n\log n)$，空間 $O(n)$。

2. 插入與平衡過程（示例 Key 集）
假設鍵序列 $[50,30,70,20,40,60,80,14,36]$。以下以「節點 (值, 高度)」表示，↺、↻ 分別為左、右旋。