|
|
|
如何依据实际情况，对任意r进制运用基数排序是基数排序算法设计的关键。下面通过例子来说明和理解基数排序。
|
|
|
|
若下列C程序的功能是：用基数排序法对读入的n个无符号整数进行排序（排成从小到大的次序），请在程序空缺处填上适当字句，使其能正确执行。具体如下：
|
|
|
|
|
|
基数排序的两种主要方法是：最高位优先MSD（Most Significant Digit first）和最低位优先LSD（Least Significant Digit first）。这里的程序采用最低位优先LSD方法对输入的n个整数进行排序，采用的主要思想是把各整数看成由4个16位数组成；若从低到高分别称为L1、L2、L3、L4，则执行如下步骤。
|
|
|
|
（1）初始化计数器count[0…15]，使各个count[i]=0(0≤i≤15)。
|
|
|
|
（2）统计L1为0、1、…、15的各个整数个数分别到count[0…15]。
|
|
|
|
（3）将count[0]、count[1]、…、count[15]合并起来得到L1为j(0≤j≤15)的整数在一趟排序后的起始位置；如a[j]在count[(a[j]>divisor%) Radix]到count[(a[j]/divisor)%Radix+1]-1之间；同时L1相同的整数的前后位置没有明显的界限，只需要根据读入的次序来定。
|
|
|
|
（4）按照得到的各个整数a[i]的位置count[j]将该元素登记在相应的位置上，同时count[j]增加1，以便存放下一个和整数a[i]的L1相同的元素。
|
|
|
|
|
|
|
|
（1）count[(a[i]/divisor)% Radix]
|
|
|
|
（2）count[(a[i]/divisor)% Radix]+1
|
|
|
|
|
|
|
|
进一步推广，若把整数看成八进制或其他进制，同样也能得到问题的答案。
|
|
|
