基數排序

基數排序（英語：Radix sort）是一種非比較型整數排序演算法，其原理是將整數按位元數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。

基數排序
概況
類別	排序演算法
資料結構	陣列
複雜度
最壞時間複雜度	${\displaystyle O(kN)}$
空間複雜度	${\displaystyle O(k+N)}$
最佳解	Yes
相關變數的定義

它是這樣實現的：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

基數排序的方式可以採用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

歷史

基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片製表機（英語：Tabulation Machine）上的貢獻^[1]。基數排序演算法早在1923年被廣泛運用在打孔卡的排序^[2]。

效率

基數排序的時間複雜度是${\displaystyle O(k\cdot n)}$，其中${\displaystyle n}$是排序元素個數，${\displaystyle k}$是數字位數。注意這不是說這個時間複雜度一定優於${\displaystyle O\left(n\cdot \log \left(n\right)\right)}$，${\displaystyle k}$的大小取決於數字位的選擇（比如位元位數），和待排序資料所屬資料類型的全集的大小；${\displaystyle k}$決定了進行多少輪處理，而${\displaystyle n}$是每輪處理的運算元目。

以排序${\displaystyle n}$個不同整數來舉例，假定這些整數以${\displaystyle B}$為底，這樣每位數都有${\displaystyle B}$個不同的數字，${\displaystyle k=\log _{B}N}$，${\displaystyle N}$是待排序資料類型全集的勢。雖然有${\displaystyle B}$個不同的數字，需要${\displaystyle B}$個不同的桶，但在每一輪處理中，判斷每個待排序資料項只需要一次計算確定對應數位的值，因此在每一輪處理的時候都需要平均${\displaystyle n}$次操作來把整數放到合適的桶中去，所以就有：

${\displaystyle k\approx \log _{B}N}$

所以，基數排序的平均時間${\displaystyle T}$就是：

${\displaystyle T\approx \log _{B}\left(N\right)\cdot n}$

其中前一項是一個與輸入資料無關的常數，當然該項不一定小於${\displaystyle \log n}$。

如果考慮和比較排序進行對照，基數排序的形式複雜度雖然不一定更小，但由於不進行比較，因此其基本操作的代價較小，而且在適當選擇的${\displaystyle B}$之下，${\displaystyle k}$一般不大於${\displaystyle \log n}$，所以基數排序一般要快過基於比較的排序，比如快速排序。