普考申論題
114年
[統計] 資料處理概要
第 三 題
📖 題組：
QuickSort 和 MergeSort 是常見的排序演算法，各自有優點與缺點。
QuickSort 和 MergeSort 是常見的排序演算法，各自有優點與缺點。
📝 此題為申論題，共 3 小題
小題 (三)
與上面問題同一個數列，利用 MergeSort 進行由小到大的排序，請寫出並說明每一次循環的結果。（10 分）
思路引導 VIP
看到合併排序法（Merge Sort），首先聯想「分而治之（Divide and Conquer）」的核心策略。解題時應先將數列不斷對半「分割」至剩單一元素，接著詳細寫出由小到大逐層「合併」的每一循環結果。若遇跨題組但未提供原數列之情形，應自行假設一組標準數列作為示範，並清楚說明推演邏輯。
小題 (一)
請設計出一最佳演算法，以能最快速查詢一資料 D 是否存在於資料串列 L1或 L2內。
思路引導 VIP
看到題目強調資料『已排序』且要求『最快速查詢』，應立即聯想到時間複雜度為 O(log N) 的『二分搜尋法 (Binary Search)』。答題關鍵在於分別針對遞增 (L1) 與遞減 (L2) 串列，寫出邏輯方向相反的搜尋步驟。
小題 (二)
並求出該演算法之時間複雜度（請越精確估算越佳）。
思路引導 VIP
遇到已排序串列合併的題目，應直覺聯想到歸併排序（Merge Sort）中的合併（Merge）程序。特別注意本題 L1 為遞增、L2 為遞減，因此需運用雙指標技巧，將 L2 從尾端往回讀取，即可在最少比較次數下，以 O(N1+N2) 的線性時間內高效完成合併並精確分析複雜度。
合併排序法實務
💡 採用分而治之策略，遞迴分割數列至最小單位後再層層合併排序。
🔗 Merge Sort 演算法三步驟
- 1 Divide (分割) — 將原始數列從中間點不斷對半切開。
- 2 Conquer (克服) — 遞迴處理子數列，直到每個子數列僅剩 1 個元素。
- 3 Combine (合併) — 將兩個已排序的子數列依序比大小，合併成較大數列。
↓
↓
🔄 延伸學習：思考 Merge Sort 為何適合處理無法全部載入記憶體的大型檔案 (External Sort)。
