3.3.5 - Bucket Sort

(MSD) Radix Sort

1. 演算法

1. 依照資料的最高位數值分派到對應的buckets

2. 每一個bucket各自排序

3. 合併buckets

Distribution & Merge只需做一次，適用於當位數很多時。

e.g. 排序179, 258, 33, 55, 145, 392, 219, 633, 175, 600

依照百位數來分派數值：

$bucket0: 33→55\\ bucket1: 145→175→179\\ bucket2:219→258\\ bucket3:342 \\ bucket4\\ bucket5\\ bucket6:600→633\\ bucket7\\ bucket8\\ ...$

合併: $33→55→145→175→179→219→258→342→600→633$