- 基数排序
- 基数排序的基本思想
- 基数排序的性能分析
基数排序 基数排序的基本思想
基数排序是一种很特别的排序方法，它不基于比较进行排序，而是采用多关键字排序思想（即基于关键字各位的大小及逆行排序），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。
基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。
以 r r r为基数的最低位优先基数排序的过程：
假设线性表由结点序列
a
0
,
a
1
,
.
.
.
,
a
n
−
1
a_0,a_1,...,a_{n-1}
a0,a1,...,an−1 构成，每个结点
a
i
a_i
ai 的关键字由
d
d
d 元组（
k
i
d
−
1
k^{d-1}_i
kid−1，
k
i
d
−
2
k^{d-2}_i
kid−2，… ，
k
i
1
k^{1}_i
ki1，
k
i
0
k^{0}_i
ki0）组成，其中
0
≤
k
i
j
≤
r
−
1
（
0
≤
i
＜
n
，
0
≤
j
≤
d
−
1
）
0≤k^{j}_i≤r-1（0≤i＜n，0≤j≤d-1）
0≤kij≤r−1（0≤i＜n，0≤j≤d−1）。在排序过程中，使用
r
r
r个队列
Q
0
Q_0
Q0，
Q
1
Q_1
Q1，…，
Q
r
−
1
Q_{r-1}
Qr−1.
排序过程如下：
对
i
=
0
,
1
,
.
.
.
,
d
−
1
i=0,1,...,d-1
i=0,1,...,d−1，依次做一次“分配”和“收集”（其实是一次稳定的排序过程）。
- 分配：开始时，把 Q 0 Q_0 Q0， Q 1 Q_1 Q1，…， Q r − 1 Q_{r-1} Qr−1各个队列置成空队列，然后依次考察线性表中的每个结点 a i （ i = 0 , 1 , . . . , n − 1 ） a_i（i=0,1,...,n-1） ai（i=0,1,...,n−1），若 a i a_i ai 的关键字 k i j = k k^{j}_i=k kij=k，就把 a i a_i ai 放进队列 Q k Q_k Qk中。
- 收集：把
Q
0
Q_0
Q0，
Q
1
Q_1
Q1，…，
Q
r
−
1
Q_{r-1}
Qr−1各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。
基数排序示例：
基数排序的性能分析
空间复杂度
一趟排序需要的辅助空间为 r r r（ r r r个队列），但以后的排序中会重复使用这些队列，故基数排序的空间复杂度为 O ( r ) O(r) O(r)。
时间复杂度
基数排序需要进行 d d d 趟分配和手机，一趟分配需要 O ( n ) O(n) O(n)，一趟搜集需要 O ( r ) O(r) O(r)，所以基数排序的时间复杂度为 O ( d ( n + r ) ) O(d(n+r)) O(d(n+r))，它与序列的初始状态无关。
稳定性
对于基数排序算法而言，很重要的一点就是按位排序必须是稳定的。因此，基数排序是一种稳定的排序方法。
