3.3.4 - Radix Sort

(LSD) Radix Sort

1. 演算法

準備r-1個buckets(r進制)，假設資料中最大值的為數個數為d，則需要執行d回合。每回合執行下面兩個步驟

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

2. Merge: 依照buckets的編號合併資料

從個位數開始到d，共執行d回合。

e.g. $\{179, 208, 306, 93, 859, 984, 55, 9, 271, 33\} _{10}$

1. Distribution: 個位數

1. Merge: {271, 93, 33, 984, 55, 306, 208, 179, 859, 9}

2. Distribution: 十位數

2. Merge: {306, 208, 9, 33, 55, 859, 271, 179, 984, 93}

3. Distribution: 百位數

3. Merge: {9, 33, 55, 93, 179, 208, 271, 306, 859, 984}

2. 性質

• Time Complexity: $O(n)$

  n筆資料為r進制，其最大值有d位數，總共花 $O(d*(n+r))$，d、r可視為常數。

• Space Complexity: $O(r*n)$

  共需r個buckers，每個buckets的大小為n。

Radix sorting is a unstable sorting method.