基数排序

(图片来自 基数排序 - 十大经典排序算法

思路

基数排序的思想在于将待排序数列补全成同样的位数(不足可前面补 0),然后按每个位数分别比较,例如最多为三位数时,先将所有数在开头补 0 到三位数,然后先按照个位分桶,放回(此时个位已有序),再按照十位排序,放回(此时十位已有序),最后按照百位排序,放回(百位已有序),得到最终结果。

基数排序、计数排序、桶排序三个算法有点类似,都利用了桶的思想,不过其实差别挺大的:

  • 计数排序是一个值一个桶,插入桶然后 concat 起来得到结果;
  • 桶排序是多个值一个桶,每个桶负责一定的数值范围,桶内排序完再 concat 所有桶;
  • 基数排序则是先按低位分桶再 concat,再向越来越高位分桶再 concat,直到最高位。

分析

假设待排序序列的数值的最大位数为 $d$,那么

  • 平均、最优、最差时间复杂度都为 $O(n \times d)$,注意这个时间复杂度不一定优于 $O(n \log n)$。但是由于基数排序不基于比较,所以一般比比较排序快。
  • 算法稳定。

实现

见《🔢 排序算法 00. 代码实现》(本博客)。