文档介绍：第9章 内部排序
----基数排序
基数排序 (Radix Sort)
问题：
1. 什么是“多关键字”排序？实现方法？
2. 单逻辑关键字怎样“按位值”排序？
基本思想：
借助多关键字排序的思想对单逻辑关键 ] 是队首指针，e[ ] 为队尾指针）
第一趟收集
930
063
083
184
505
278
008
109
589
269
r[0]→
109
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
063
278
269
083
184
505
109
930
589
008
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
第二趟分配（按次低位 i = 2 ）
269
589
063
505
109
184
930
008
278
083
930
063
083
184
505
278
008
109
589
269
第一趟收集的结果：
第二趟收集
r[0]→
r[0]→
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
083
008
930
589
184
109
269
505
063
278
f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]
第三趟分配（按最高位 i = 1 ）
r[0]→
排序结束！
269
930
184
008
083
589
109
063
278
505
269
589
063
505
109
184
930
008
278
083
r[0]→
第二趟收集的结果：
第三趟收集
基数排序算法分析
假设有n 个记录, 每个记录的关键字有d 位，每个关键字的取值有radix个, 则需要radix个队列, 进行d 趟“分配”与“收集”。因此时间复杂度：O ( d ( n+radix ) )。
基数排序需要增加n+2radix个附加链接指针，空间效率低
空间复杂度：O（radix）.
稳定性：稳定。(一直前后有序)。
用途：若基数radix相同，对于记录个数较多而关键码位数较少的情况，使用链式基数排序较好。
特点：不用比较和移动，改用分配和收集，时间效率高！
链表基数排序的算法：
void RadixSort (&list, int d, int radix ) {
int f[radix], e[radix];
for ( int i = 1; i < n; i++ ) r[i].next=i+1;
r[n].next=0; //静态链表初始化，将各记录顺次链接。
int p= 1; //p是链表元素的地址指针
for ( i = d-1; i >= 0; i-- ) { //开始做 d 趟分配/收集, i是key的第i位
for ( int j = 0; j < radix; j++ ) f[j] = 0; //初态＝各队列清空
while ( p!= 0 ) { // 开始将n个记录分配到radix个队列
int k = r[p]. key[i]; //取当前记录之key分量的第 i 位
if ( f[k] == 0) f [k] =p; //若第k个队列空, 此记录成为队首；
else r[e[k]].next=p; //若队列不空,链入原队尾元素之后
e[k] =p; //修改队尾指针，该记录成为新的队尾
p= r[p].next; } / / 选下一关键字，直到本趟分配完
j = 0; // 开始从0号队列（总共radix个队）开始收