2、排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，...…，依次类推，直至最后对最次位关键字排序完成为止。先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:无序序列3,2,301,2,153,1,202,3,182,1,20对K2排序1,2,152
3、,3,183,1,202,1,203,2,30对K1排序3,1,202,1,201,2,153,2,302,3,18对K0排序1,2,152,1,202,3,183,1,203,2,30二、链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。例如：对下列这组关键字{209,386
4、,768,185,247,606,230,834,539}首先按其“个位数”取值分别为0,1,…,9“分配”成10组，之后按从0至9的顺序将它们“收集”在一起；然后按其“十位数”取值分别为0,1,…,9“分配”成10组，之后再按从0至9的顺序将它们“收集”在一起；最后按其“百位数”重复一遍上述操作。在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：１．待排序记录以指针相链，构成一个链表；２．“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个
5、队列中记录的“关键字位”相同；３．“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;４．对每个关键字位均重复2)和3)两步。例如：p→369→367→167→239→237→138→230→139进行第一次分配f[0]r[→230←0]f[7]r[→367→167→237←7]f[8]r[→138←8]f[9]r[→369→239→139←9]进行第一次收集p→230→367→167→237→138→369→239→139p→230→367→167→237→138→369→239→139进行第二次
6、分配f[3]r[→230→237→138→239→139←3]f[6]r[→367→167→369←6]进行第二次收集p→230→237→138→239→139→367→167→369p→230→237→138→239→139→367→167→369进行第三次分配f[1]r[→138→139→167←1]f[2]r[→230→237→239←2]f[3]r[→367→369←3]进行第三次收集之后便得到记录的有序序列p→138→139→167→230→237→239→367→369提醒注意：１．“分配”和“收集”
7、的实际操作仅为修改链表中的指针和设置队列的头、尾指针；２．为查找使用，该链表尚需应用算法Arrange将它调整为有序表。基数排序的时间复杂度为O(d(n+rd))其中：分配为O(n)收集为O(rd)(rd为“基”)d为“分配-收集”的趟数p→012345673691367216732394237513862307-1391进行第一次分配f[0]=r[0]=-1;f[1]=r[1]=-1;f[2]=r[2]=-1;f[3]=r[3]=-1;f[4]=r[4]=-1;f[5]=r[5]=-1;f[6]=r[6]=-1
8、;f[7]=r[7]=-1;f[8]=r[8]=-1;f[9]=r[9]=-1;p→012345673691367216732394237513862307-1391进行第一次分配f[0]=r[0]=-1;f[1]=r[1]=-1;f[2]=r[2]=-1;f[3]=r[3]=-1;f[4]=r[4]=-1;f[5]=r[5]=-1;f[6]=r[6]=-1;f[7]=r
