8-9基数排序

基于链表的基数排序
一.过程

将每个元素拆为个位、十位、百位，每一位的取值可能是0-9

建立十个队列。先处理个位（按最低位优先LSD），520的个位是0，放入Q₀，211的个位是1，放入Q₁

即

同一个位的元素按照队列的规则从队尾进入
以此类推

按出队顺序，按递减次序排序，因此从Q₉到Q₀搜集元素
得到438→888→168→007→666→996…
至此完成了个位由大到小的排列

同样，按照十位放入队列。十位为3的放到Q₃，以此类推

再按照出队顺序，从Q₉到Q₀搜集元素

再按百位元素放入队列，收集

即

至此完成了排序
可以看出
1.百位的权重>十位的权重>个位的权重，每次都先处理权重最低的次序。
2.对于n个待排序元素，每个关键字可以拆分成d元组（百位十位个位就是三元组），其中百位叫做最高位关键字（最主位关键字），个位叫做最低位关键字（最低次关键字）
3.每一位的可能取值为0~9，即r=10，0~r-1，r称为基数

二.效率分析
1.空间复杂度，需要r个辅助队列，O( r)
2.时间复杂度：被拆成3个部分，进行3趟的分配和收集。对于拆成d个部分，需要进行d趟分配和收集。每一趟的分配需扫描所有元素O(n)，每一趟收集需要O( r) （对每个队列的收集只需要O(1)）。因此总的时间复杂度为O(d(n+r))
d趟分配和收集（个十百三位）
n个元素
每个部分r个可能取值（0-9）
3.稳定性
按照队列先进先出的原则，该算法是稳定的

三.基数排序的应用
对10000名学生的信息按年龄递减排序
生日可拆分为三组关键字：年（1991-2005）、月（1-12）、日（1-31）
显然，权重年>月>日
其中，年月日越小，年龄越大，所以每次收集都是从左至右

在以下几种情况下可以优先选择基数排序
数据元素的关键字可以方便的拆分为d组（个十百），d较小，关键字的取值范围r较小，数据元素个数n较大

四.总结