政大 113 年資管所（科技組） 資料結構 參考答案

自 index 8 往前逐一 heapify-down：

i=8（值 16）：[1, 8, 4, 53, 12, 7, 35, 103, 56, 14, 63, 29, 20, 72, 38, 18, 22, 16]

i=7（值 103）：[1, 8, 4, 53, 12, 7, 35, 103, 56, 14, 63, 29, 20, 72, 38, 18, 22, 16]

i=6（值 35）：[1, 8, 4, 53, 12, 7, 72, 103, 56, 14, 63, 29, 20, 35, 38, 18, 22, 16]

i=5（值 7）：[1, 8, 4, 53, 12, 29, 72, 103, 56, 14, 63, 7, 20, 35, 38, 18, 22, 16]

i=4（值 12）：[1, 8, 4, 53, 63, 29, 72, 103, 56, 14, 12, 7, 20, 35, 38, 18, 22, 16]

i=3（值 53）：[1, 8, 4, 103, 63, 29, 72, 53, 56, 14, 12, 7, 20, 35, 38, 18, 22, 16]

i=2（值 4）：[1, 8, 72, 103, 63, 29, 38, 53, 56, 14, 12, 7, 20, 35, 4, 18, 22, 16]

i=1（值 8）：[1, 103, 72, 56, 63, 29, 38, 53, 16, 14, 12, 7, 20, 35, 4, 18, 22, 8]

i=0（值 1）：[103, 63, 72, 56, 14, 29, 38, 53, 16, 1, 12, 7, 20, 35, 4, 18, 22, 8]

最終 Max-Heap：[103, 63, 72, 56, 14, 29, 38, 53, 16, 1, 12, 7, 20, 35, 4, 18, 22, 8]

1. 以 bottom-up 方式把 $n$ 個 key 建成 Max-Heap。
2. swap(A[0], A[heapSize-1])，把當前最大值送到未排序區尾端。
3. heapSize--，對新 root 做 heapify-down。
4. 重複 2～3 共 $n-1$ 次，陣列即由小到大排好。

時間：建堆 $O(n)$，$n-1$ 次 heapify-down 各 $O(\log n)$，總計 $O(n\log n)$；空間 $O(1)$。

（如簡答圖）

1. 建樹：$n$ 個 key 依序插入 AVL tree，每次 $O(\log n)$，共 $O(n\log n)$。
2. 輸出：對樹做 Inorder Traversal，$O(n)$，輸出即遞增序列。

時間 $O(n\log n)$，空間 $O(n)$。

Merge Sort：陣列由中點切成兩半，遞迴排序後以 merge 把兩個已排序子陣列合併（各設一指標，取較小者依序放入結果）。

$T(n)=2T(n/2)+O(n)$；Master Theorem：$a=2$、$b=2$、$n^{{\log }_{2}2}=n$ 與 $f(n)=n$ 同階，Case 2，$T(n)=\Theta (n\log n)$。

切分：

[1, 8, 4, 53, 12, 7, 35, 103, 16] [14, 63, 29, 20, 72, 38, 18, 22, 56]

[1, 8, 4, 53, 12] [7, 35, 103, 16] [14, 63, 29, 20, 72] [38, 18, 22, 56]

[1, 8, 4] [53, 12] [7, 35] [103, 16] [14, 63, 29] [20, 72] [38, 18] [22, 56]

[1, 8] [4] [53] [12] [7] [35] [103] [16] [14, 63] [29] [20] [72] [38] [18] [22] [56]

[1] [8] [4] [53] [12] [7] [35] [103] [16] [14] [63] [29] [20] [72] [38] [18] [22] [56]

合併：

[1, 8] [4] [53] [12] [7] [35] [103] [16] [14, 63] [29] [20] [72] [38] [18] [22] [56]

[1, 4, 8] [12, 53] [7, 35] [16, 103] [14, 29, 63] [20, 72] [18, 38] [22, 56]

[1, 4, 8, 12, 53] [7, 16, 35, 103] [14, 20, 29, 63, 72] [18, 22, 38, 56]

[1, 4, 7, 8, 12, 16, 35, 53, 103] [14, 18, 20, 22, 29, 38, 56, 63, 72]

[1, 4, 7, 8, 12, 14, 16, 18, 20, 22, 29, 35, 38, 53, 56, 63, 72, 103]

1. Partition：$pk=A[m]$、$i=m+1$、$j=n$。$i$ 由左往右找第一個 $\ge pk$、$j$ 由右往左找第一個 $\le pk$；若 $i<j$ 則 swap(A[i],A[j])，重複到 $i,j$ 交會，最後 swap(A[m],A[j])，pivot 歸位。
2. 對 pivot 左右兩個子區間各自遞迴，直到區間只剩 0～1 個元素。

pivot 取範圍第一個元素，每次 partition 後的陣列：

範圍 0～17，pivot 1 歸位 index 0：[1, 8, 4, 53, 12, 7, 35, 103, 16, 14, 63, 29, 20, 72, 38, 18, 22, 56]

範圍 1～17，pivot 8 歸位 index 3：[1, 7, 4, 8, 12, 53, 35, 103, 16, 14, 63, 29, 20, 72, 38, 18, 22, 56]

範圍 1～2，pivot 7 歸位 index 2：[1, 4, 7, 8, 12, 53, 35, 103, 16, 14, 63, 29, 20, 72, 38, 18, 22, 56]

範圍 4～17，pivot 12 歸位 index 4：[1, 4, 7, 8, 12, 53, 35, 103, 16, 14, 63, 29, 20, 72, 38, 18, 22, 56]

範圍 5～17，pivot 53 歸位 index 13：[1, 4, 7, 8, 12, 38, 35, 22, 16, 14, 18, 29, 20, 53, 72, 63, 103, 56]

範圍 5～12，pivot 38 歸位 index 12：[1, 4, 7, 8, 12, 20, 35, 22, 16, 14, 18, 29, 38, 53, 72, 63, 103, 56]

範圍 5～11，pivot 20 歸位 index 8：[1, 4, 7, 8, 12, 16, 18, 14, 20, 22, 35, 29, 38, 53, 72, 63, 103, 56]

範圍 5～7，pivot 16 歸位 index 6：[1, 4, 7, 8, 12, 14, 16, 18, 20, 22, 35, 29, 38, 53, 72, 63, 103, 56]

範圍 9～11，pivot 22 歸位 index 9：[1, 4, 7, 8, 12, 14, 16, 18, 20, 22, 35, 29, 38, 53, 72, 63, 103, 56]

範圍 10～11，pivot 35 歸位 index 11：[1, 4, 7, 8, 12, 14, 16, 18, 20, 22, 29, 35, 38, 53, 72, 63, 103, 56]

範圍 14～17，pivot 72 歸位 index 16：[1, 4, 7, 8, 12, 14, 16, 18, 20, 22, 29, 35, 38, 53, 56, 63, 72, 103]

範圍 14～15，pivot 56 歸位 index 14：[1, 4, 7, 8, 12, 14, 16, 18, 20, 22, 29, 35, 38, 53, 56, 63, 72, 103]

排序結果：[1, 4, 7, 8, 12, 14, 16, 18, 20, 22, 29, 35, 38, 53, 56, 63, 72, 103]