高考申論題
106年
[電力工程] 計算機概論
第 二 題
📖 題組：
三、水桶排序（bucket sort）是一種常見的排序方法。
三、水桶排序（bucket sort）是一種常見的排序方法。
📝 此題為申論題，共 2 小題
小題 (二)
當排序的數字有何種特性時，水桶排序法的平均時間複雜度可達 O(n)？請試述其理由。（10 分）
思路引導 VIP
考生看到此題應先回想水桶排序（Bucket Sort）的運作機制：將資料分配到有限數量的水桶中，對各桶分別排序後合併。接著推導：要達到線性時間複雜度 O(n)，必須確保『每個桶內的資料量極少（趨近常數）』，由此即可反推輸入資料必須具備『均勻分布』的特性。
小題 (一)
使用水桶排序法將下列十個數字由小到大排列，必須清楚解釋排序過程。（15 分）
28, 57, 16, 0, 72, 99, 33, 82, 12, 67
28, 57, 16, 0, 72, 99, 33, 82, 12, 67
思路引導 VIP
看到水桶排序法（Bucket Sort）的題目，首要任務是『觀察數值範圍』並『決定水桶劃分區間與數量』。接著只要按照『分配（Scatter）→ 桶內排序（Sort）→ 合併（Gather）』三個標準步驟進行圖解或條列說明，將每個數字映射到對應水桶並展示內部排序過程，即可穩穩拿下分數。