基数排序
基数排序（Radix Sort）是一种不基于关键字比较的排序方法。
突破比较排序下界
基于关键字比较的排序方法有复杂度下界 O(n log n)。基数排序利用桶结构突破了这个下界。
基本思想
将关键字分成一个个分量，基于分量的取值范围设置桶的数量，有次序地按照每个分量进行分配与回收。经过所有分量处理后得到排序好的序列。
示例
先对个位数进行分配并回收，再对十位数、百位数，最后得到有序序列。
算法分析
- 时间复杂度：O(d × (n + k))，d 为位数（分量数），k 为桶数
- 空间复杂度：O(n + k)
- 稳定性：稳定
局限性
- 关键字必须可以拆分成可比的分量
- 分量必须有限
- 分量的取值范围必须有限
链接到
- 上一个知识点：6.10 归并排序
- 下一个知识点：6.12 内部排序方法比较