基数：假设长度为 n 的线性表中每个结点
a
j
a_j
aj 的关键字由
d
d
d 元组
(
k
j
d
−
1
,
k
j
d
−
2
,
k
j
d
−
3
,
.
.
.
,
k
j
1
,
k
j
0
)
(k^{d-1}_j,k^{d-2}_j,k^{d-3}_j,...,k^1_j,k^0_j)
(kjd−1,kjd−2,kjd−3,...,kj1,kj0) 组成，其中
0
≤
k
j
i
≤
r
−
1
（
0
≤
j
<
n
，
0
≤
i
≤
d
−
1
）
0≤k_j^i≤r-1（0≤j<n，0≤i≤d-1）
0≤kji≤r−1（0≤j<n，0≤i≤d−1），
r
r
r 称为基数
基数排序得到递减序列过程：
初始化：设置
r
r
r 个空队列，
Q
r
−
1
,
Q
r
−
2
,
.
.
.
,
Q
0
Q_{r-1},Q_{r-2},...,Q_0
Qr−1,Qr−2,...,Q0
按照各个关键字位权重递增的次序（个、十、百），对
d
d
d 个关键字位分别做分配和收集
分配：顺序扫描各个元素，若当前处理的关键字位
=
x
= x
=x，则将元素插入
Q
x
Q_x
Qx 队尾
收集：把
Q
r
−
1
,
Q
r
−
2
,
.
.
.
,
Q
0
Q_{r-1},Q_{r-2},...,Q_0
Qr−1,Qr−2,...,Q0 各个队列中的结点依次出队并链接
2. 算法性能分析
空间复杂度：
O
(
r
)
O(r)
O(r)
时间复杂度：一趟分配
O
(
n
)
O(n)
O(n)，一趟收集
O
(
r
)
O(r)
O(r)，总共
d
d
d 趟分配、收集，总的时间复杂度为
O
(
d
(
n
+
r
)
)
O(d(n+r))
O(d(n+r))
