基数排序¶
上一节介绍了计数排序,它适用于数据量
基数排序(radix sort)的核心思想与计数排序一致,也通过统计个数来实现排序。在此基础上,基数排序利用数字各位之间的递进关系,依次对每一位进行排序,从而得到最终的排序结果。
算法流程¶
以学号数据为例,假设数字的最低位是第
- 初始化位数
。 - 对学号的第
位执行“计数排序”。完成后,数据会根据第 位从小到大排序。 - 将
增加 ,然后返回步骤2.
继续迭代,直到所有位都排序完成后结束。
下面剖析代码实现。对于一个
其中
此外,我们需要小幅改动计数排序代码,使之可以根据数字的第
[file]{radix_sort}-[class]{}-[func]{radix_sort}
为什么从最低位开始排序?
在连续的排序轮次中,后一轮排序会覆盖前一轮排序的结果。举例来说,如果第一轮排序结果
算法特性¶
相较于计数排序,基数排序适用于数值范围较大的情况,但前提是数据必须可以表示为固定位数的格式,且位数不能过大。例如,浮点数不适合使用基数排序,因为其位数
- 时间复杂度为
、非自适应排序:设数据量为 、数据为 进制、最大位数为 ,则对某一位执行计数排序使用 时间,排序所有 位使用 时间。通常情况下, 和 都相对较小,时间复杂度趋向 。 - 空间复杂度为
、非原地排序:与计数排序相同,基数排序需要借助长度为 和 的数组res
和counter
。 - 稳定排序:当计数排序稳定时,基数排序也稳定;当计数排序不稳定时,基数排序无法保证得到正确的排序结果。