9.6 基数排序 (Radix Sort)
基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。
多关键码排序：
1.以扑克牌排序为例。每张扑克牌有两个“关键码”：花色和面值。其有序关系为：
花色：
面值：2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
2.如果我们把所有扑克牌排成以下次序：
3.这就是多关键码排序。排序后形成的有序序列叫做词典有序序列。
4.对于上例两关键码的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。
5.一般情况下，假定有一个 n 个对象的序列 {V0, V1, …, Vn-1 }，且每个对象Vi 中含有 d 个关键码
6.如果对于序列中任意两个对象 Vi 和 Vj ( 0 ≤ i< j ≤ n-1 ) 都满足：
7.则称序列对关键码 (K1, K2, …, Kd) 有序。其中，K1 称为最高位关键码，Kd 称为最低位关键码。
8.如果关键码是由多个数据项组成的数据项组，则依据它进行排序时就需要利用多关键码排序。
9.实现多关键码排序有两种常用的方法
（1） 最高位优先MSD (Most Significant Digit first)
（2） 最低位优先LSD (Least Significant Digit first)
10. 最高位优先法通常是一个递归的过程：
（1） 先根据最高位关键码K1排序,得到若干对象组，对象组中每个对象都有相同关键码K1。
（2） 再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。
（3） 依此重复，直到对关键码Kd完成排序为止。
（4） 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。
11. 最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组都参加排序。
12. LSD和MSD方法也可应用于对一个关键码进行的排序。此时可将单关键码 Ki 看作是一个子关键码组：
9.6.2 链式基数排序
基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。在这种方法中，把单关键码 Ki 看成是一个d元组：
其中的每一个分量 ( 1≤ j ≤ d ) 也可看成是一个关键码。
分量
(1≤ j ≤ d ) 有radix种取值，则称radix为基数。例如，关键码984可以看成是一个3元组(9, 8, 4)，每一位有0, 1, …, 9等10种取值，基数radix = 10。关键码‘data’可以看成是一个4元组(d, a, t, a)，每一位有‘a’, ‘b’, …, ‘z’等26种取值，radix = 26。
针对d元组中的每一位分量，把对象序列中的所有对象, 按 的取值，先“分配”到rd个队列中去。然后再按各队列的顺序，依次把对象从队列中“收集”起来，这样所有对象按取值 排序完成。
如果对于所有对象的关键码K0, K1, …, Kn-1，依次对各位的分量，让 j = d, d-1, …, 1，分别用这种“分配”、“收集”的运算逐趟进行排序，在最后一趟“分配”、“收集” 完成后，所有对象就按其关键码的值从小到大排好序了。
各队列采用链式队列结构，分配到同一队列的关键码用链接指针链接起来。每一队列设置两 个队列指针： int front [radix]指示队头， int rear [radix] 指向队尾。
为了有效地存储和重排 n 个待排序对象，以静态链表作为它们的存储结构。在对象重排时不必移动对象，只需修改各对象的链接指针即可。
基数排序的“分配”与“收集”过程 第一趟 ：
基数排序的“分配”与“收集”过程 第二趟 ：
基数排序的“分配”与“收集”过程 第三趟 ：
链表基数排序：
template <class Type> void RadixSort
( staticlinklist<Type> &list, const int d, const int radix ) {
int rear[radix], front[radix];
for ( int i = 1; i < list.CurrentSize; i++ )
list.Vector[i].link = i+1;
list.Vector[n].link = 0; //静态链表初始化
int current = 1; //链表扫描指针
for ( i = d-1; i >= 0; i-- ) { //做 d 趟分配.收集
for ( int j = 0; j < radix; j++ ) front[j] = 0;
while ( current != 0 ) { //逐个对象分配
int k = list.Vector[current].key[i]; //第 i 位
if ( front[k] == 0) //原链表为空,对象链入
front[k] = current;
else //原链表非空,链尾链入
list.Vector[rear[k]].link = current;
rear[k] = current; //修改链尾指针
current = list.Vector[current].link;
}
j = 0; //从0号队列开始收集
while ( front[j] == 0 )
j++; //空队列跳过
list.Vector[0].link = current = front[j];
int last = rear[j];
for ( k = j+1; k < radix; k++) //逐个队列链接
if ( front[k] ) {
list.Vector[last].link = front[k];
last = rear[k];
}
list.Vector[last].link = 0;
}
}
算法分析：
1.若每个关键码有d 位，需要重复执行d 趟“分配”与“收集”。每趟对 n 个对象进行“分配”，对radix个队列进行“收集”。总时间复杂度为O ( d ( n+radix ) )。
2.若基数radix相同，对于对象个数较多而关键码位数较少的情况，使用链式基数排序较好。
3.基数排序需要增加n+2radix个附加链接指针。
4.基数排序是稳定的排序方法。