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

最終 min-heap（level order，bottom-up 建堆）：[1, 7, 3, 19, 16, 5, 12, 28, 35, 92, 48, 17, 22, 18]

1. 把 $n$ 個元素建成 min-heap。
2. 取出並輸出 root（當前最小值）。
3. root 與 heap 最後一個元素交換，heap size 減 1。
4. 對 root 做 heapify-down，恢復 heap 結構。
5. 重複 2～4 共 $n$ 次，輸出序列即為遞增排序；時間 $O(n\log n)$。

依序取出的序列：1, 3, 5, 7, 12, 16, 17, 18, 19, 22, 28, 35, 48, 92

（如簡答圖）

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

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

Inorder 輸出：1, 3, 5, 7, 12, 16, 17, 18, 19, 22, 28, 35, 48, 92

1. Divide：陣列由中點切成兩半。
2. Conquer：遞迴排序兩半，直到子陣列只剩 1 個元素。
3. Merge：兩個已排序子陣列各設一指標，每次取較小者放入結果並前移該指標；一方取完後，另一方剩餘元素直接接上。

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

切分：

[17, 35, 12, 28, 16, 5, 18] [7, 19, 92, 48, 3, 22, 1]

[17, 35, 12, 28] [16, 5, 18] [7, 19, 92, 48] [3, 22, 1]

[17, 35] [12, 28] [16, 5] [18] [7, 19] [92, 48] [3, 22] [1]

[17] [35] [12] [28] [16] [5] [18] [7] [19] [92] [48] [3] [22] [1]

合併：

[17, 35] [12, 28] [5, 16] [18] [7, 19] [48, 92] [3, 22] [1]

[12, 17, 28, 35] [5, 16, 18] [7, 19, 48, 92] [1, 3, 22]

[5, 12, 16, 17, 18, 28, 35] [1, 3, 7, 19, 22, 48, 92]

[1, 3, 5, 7, 12, 16, 17, 18, 19, 22, 28, 35, 48, 92]

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

範圍 0～13，pivot 17 歸位 index 6：[7, 1, 12, 3, 16, 5, 17, 18, 19, 92, 48, 28, 22, 35]

範圍 0～5，pivot 7 歸位 index 3：[3, 1, 5, 7, 16, 12, 17, 18, 19, 92, 48, 28, 22, 35]

範圍 0～2，pivot 3 歸位 index 1：[1, 3, 5, 7, 16, 12, 17, 18, 19, 92, 48, 28, 22, 35]

範圍 4～5，pivot 16 歸位 index 5：[1, 3, 5, 7, 12, 16, 17, 18, 19, 92, 48, 28, 22, 35]

範圍 7～13，pivot 18 歸位 index 7：[1, 3, 5, 7, 12, 16, 17, 18, 19, 92, 48, 28, 22, 35]

範圍 8～13，pivot 19 歸位 index 8：[1, 3, 5, 7, 12, 16, 17, 18, 19, 92, 48, 28, 22, 35]

範圍 9～13，pivot 92 歸位 index 13：[1, 3, 5, 7, 12, 16, 17, 18, 19, 35, 48, 28, 22, 92]

範圍 9～12，pivot 35 歸位 index 11：[1, 3, 5, 7, 12, 16, 17, 18, 19, 28, 22, 35, 48, 92]

範圍 9～10，pivot 28 歸位 index 10：[1, 3, 5, 7, 12, 16, 17, 18, 19, 22, 28, 35, 48, 92]

排序結果：[1, 3, 5, 7, 12, 16, 17, 18, 19, 22, 28, 35, 48, 92]