地特三等申論題
106年
[電力工程] 計算機概論
第 一 題
📖 題組：
三、水桶排序（bucket sort）是一種常見的排序方法。
三、水桶排序（bucket sort）是一種常見的排序方法。
📝 此題為申論題，共 2 小題
小題 (一)
使用水桶排序法將下列十個數字由小到大排列，必須清楚解釋排序過程。（15 分）
28, 57, 16, 0, 72, 99, 33, 82, 12, 67
思路引導 VIP
看到水桶排序法，首先要觀察數據的範圍，決定適當的水桶數量與映射規則（本題數字為0-99，適合以十位數分10個桶）。接著依照「分發到各桶（Scatter） → 桶內個別排序（Sort） → 依序合併（Gather）」的三個標準步驟，條理分明地寫出運作過程即可拿高分。
小題 (二)
當排序的數字有何種特性時，水桶排序法的平均時間複雜度可達 O(n)？請試述其理由。（10 分）
思路引導 VIP
看到水桶排序法（Bucket Sort）的時間複雜度，應直覺聯想到其對資料「分布狀態」的高度依賴。解題關鍵在於點出「均勻分布」（Uniform Distribution）這個特性，並透過分析資料分派、桶內排序及合併三個步驟的時間成本，來推導出平均時間複雜度為 O(n) 的理由。