2、词典)有序关系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)(1,2,15)(2,1,20)(2,3,18)(3,1,20)(3,2,30)(1,2,15)(2,1,20)(2,3,18)(3,1,20)(3,2,30)有序无序则称序列{R1,…,Rn}对多关键字(Ki0,Ki1,…,Kid-1)有序。实现多关键字排序通常有两种作法:最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别在每个子序列中对K1进行排序，...…，依次类推，直至
3、最后对最次位关键字排序完成为止。最低位优先LSD法：先对Kd-1进行排序，然后在次基础上直接对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。例如:学生记录含三个关键字:(系号,班号,序号),要求对对学生记录排序，系号为主关键字。对K0排序对K1排序对K2排序无序序列3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,30最高位优先MSD的排序过程如下:1,2,152,1,202,3,183,1,203,2,301,2,
4、152,1,202,3,183,1,203,2,30例如:学生记录含三个关键字:(系号,班号,序号),要求对对学生记录排序，系号为主关键字。对K2排序对K1排序对K0排序无序序列3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,181,2,152,1,202,3,183,1,203,2,30最低位优先LSD的排序过程如下:二、链式基数排序基数排序法是一种不需要进行关键字间比较
5、的排序方法。其特点是：对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的办法按最低位优先LSD进行排序。例如：对下列这组关键字{209,386,768,185,247,606,230,834,539}首先按其“个位数”取值分别为0,1,…,9“分配”成10组；(230),(834),(185),(386,606),(247),(768),(539,209){230,834,185,386,606,247,768,539,209}之后按从0至9的顺
6、序将它们“收集”在一起;然后按其“十位数”取值分别为0,1,…,9“分配”成10组；最后按其“百位数”重复一遍上述操作。“分配”{230,834,185,386,606,247,768,539,209}之后再按从0至9的顺序将它们“收集”在一起；(606,209),(230,834,539),(247),(768),(185,386){606,209,230,834,539,247,768,185,386}(185),(209,230,247),(386),(539),(606),(768),(83
7、4){185,209,230,247,386,539,606,768,834}然后“收集”在一起；在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：１．待排序记录以指针相链，构成一个链表；２．“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；３．“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;４．对每个关键字位均重复2)和3)两步。例如：p→369→367→167→239→237
8、→138→230→139进行第一次分配进行第一次收集f[0]r[0]f[7]r[7]f[8]r[8]f[9]r[9]p→230→230←→367←→167→237→367→167→237→138→368→239→139→369←→239→139→138←进行第二次分配p→230→237→138→239→139p→230→367→167→237→138→368→239→139f[3]r[3]f[6]r[6]→230←→237→138→239→139→367←→167→3
