基數排序法（Radix sort）介紹

 基數排序法是什麼

一種非比較型排序法。適合排非整數數據，如浮點數、字串。透過逐位進行排序。適合數據量大且數據範圍有限。

舉例

欲用基數排序法排數列[170, 45, 75, 90, 802, 24, 2, 66]。

1. 首先排個位數

170 (0)

45(5)

75(5)

90(0)

802(2)

24(4)

2(2)

66(6)

排序後變成[170, 90, 802, 2, 24, 45, 75, 66]

2. 排十位數

170(7)

90(9)

802(0)

2(0)

24(2)

45(4)

75(7)

66(6)

排序後變成[802, 2, 24, 45, 66, 170, 75, 90]

3. 排百位數

802（8）

2（0）

24（0）

45(0)

66（0）

170（1）

75（0）

90（0）

排序後變成[ 2, 24, 45,66, 75, 90,170,802]

時間複雜度

O(d*(n+k))，其中d為位數，k為基數，如十進位是10，數值範圍為0~9。為了對每一位排序用計數排序法，首先建最大值加1長度的計數陣列O(k)，再將元素頻率填入計數陣列O(n)所以時間複雜度為O(n+k)。

空間複雜度

計數陣列空間O(k)加額外輸出陣列O(n)，故空間複雜度為O(n+k)