第八章 排序 十、基数排序

一、定义

1. 基数排序（Radix Sort）是一种非比较排序算法，它将待排序元素按照其数值的各位数字（或字母）来排序。
2. 该算法的基本思想是将整数按照位数切分成不同的数字，然后根据每个位数上的数字进行排序。
3. 与其他排序算法相比，基数排序的时间复杂度为 O(d*n)，其中 d 表示位数，n 表示待排序元素个数。
4. 在实际应用中，基数排序通常采用桶排序来实现，因此它也被称为桶排序的一种扩展，并且通常被用来对整数排序，而不是字符串等其他类型的数据。

二、例子

1、我们有如下序列，我们要将它进行基数排序

2、把所有数字按个位数分配

3、由于我们要得到一个递减的序列，所以我们以个位进行一次收集

从右到左，从上到下，得到一个以个位数递减的序列

4、基于以个位数递减的序列，我们再以十位进行分配

由于第一次进行的个位数的收集，所以这一次收集是个位数更大的先入队（在同一队中）

5、以十位数进行收集

6、以百位数进行分配

7、以百位数进行收集，得到最终序列

三、算法效率分析

四、稳定性

稳定

五、应用

六、总结