基数排序
1.0概述
1.1 多关键字排序
n个记录的序列 {R1, R2, ... , Rn}对关键字(k1, k2, ... , kd)有序。
就是说，对于序列中任意两个记录Ri和Rj (1≤i＜j≤n) 都满足下列有序关系：
(ki1, ki2, ... , kid) ＜ (kj1, kj2, ... , kjd)
K1称为最主位关键字
Kd称为最主位关键字
多关键字排序按照关键字的顺序分为两种方式：
最主位优先MSD法：先对K1进行分组，同一组中记录，若关键字K1相等，再对各组按K2排序分成子组，... , 至最后对最次位关键字排序完成为止。
最次为优先LSD法：先对Kd进行排序，然后对Kd-1进行排序，依次类推，直至对主要位关键字K1排序完成为止。（排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分隔成若干个子序列）
例如：学生记录含三个关键字，
系别、班号和班内的序列号，其中以系别为最主位关键字。1.2 链式基数排序
假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。
对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称为基数排序法。
例如：关键字如下{209, 386, 768, 185, 247, 606, 230, 834, 539}
首先按其
个位数取值分别为0,1,...9分配成10组，之后按从0至9的顺序将他们收集在一起然后按其
十位数取值分别为0,1,...9分配成10组，之后再按从0至9的顺序将他们收集在一起最后按其
百位数重复一遍上述操作
在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体操作：
待排序记录以指针相链，构成一个链表
分配时，按当前关键字位所取值，将记录分配到不同的链队列中，每个队列中记录的关键字位相同
收集时，按当前关键字位取值从小到大将各队列首尾相链成一个链表对每个关键字位均 重复2）和3）两步
例如：
注意：
分配和收集的实际操作仅为修改链表中的指针和设置队列的头、尾指针
为查找使用，该链表尚需将它调整为有序表。
