基数排序

一个例子

有如下链表，要求按关键字“递减”的有序序列

观察发现个位、十位、百位都是0~9。可以建立一个0~9的辅助队列每趟依次根据个位、十位、百位的数字存储到队列的相应位置上去。

第一趟操作 按个位
分配：
以各位数为基准进行排序。遍历完链表后得到如下的各个队列。第一趟的“分配”操作完成。

收集：
将各个元素按要求收集起来，比如这个例子中要求递减序列，则从左往右从上往下依次收集各个元素组成新的链表。如下所示:

得到“个位”递减的有序序列。

第二趟操作 基于第一趟的序列 按十位
分配：
由于第一趟为“个位”递减序列。所以在第二趟中，如果“十位”相同，“个位”越大的越先入对。分配结果如下：

收集：
与第一趟相同，收集链表如下:

得到“十位”递减的有序序列，如果“十位”相同，则会按“个位”递减排序

第三趟操作 基于第二趟趟的序列 按百位
分配：
由于第二趟为“十位”递减序列。所以在第三趟中，如果“百位”相同，“十位”越大的越先入对。分配结果如下：

收集：
与前两趟相同，收集链表如下:

得到“百位”递减的有序序列，如果“百位”相同，则会按“十位”递减排序，如果“十位”相同，则会按“个位”递减排序。

例子总结

基数排序

定义

获得递增序列的方法与获得递减序列的方法的收集操作相反。
基数排序不是基于（关键字的）比较的排序算法

算法效率分析

空间复杂度：

时间复杂度

稳定性

基数排序是稳定的。

基数排序的应用

将学生按年龄递减排序

总结