跳转至

基数类

基数排序

【基数排序】基数排序属于“分配式排序”，又称“桶子法”

【思想】“多关键字排序”：它是通过键值的部份资讯，将要排序的元素分配至某些“桶”中

【两种实现方法】

方法 介绍 例子：扑克牌
最高位优先 1. 先按一种规则（ 最高位 ）将数据分成若干个子序列
2. 再对每个子序列按 次高位 排序		 1. 先准备4个桶，按 花色 （最高位）进行分配；
2. 再对每种花色13张牌进行排序（可以采用其他排序方法，也可采用最低位基数排序）
最低位优先 不必分成子序列 ，每次排序 全体元素都参与 。可以不通过比较，而通过“分配”和“收集”来进行排序 1. 准备13个桶，按**数字**将牌分配到13个桶中；
2. 然后从第一个桶开始依次收集；
3. 再将收集好的牌按**花色**分配到4个桶中
4. 然后还是从第一个桶开始依次收集
经过两次“分配”和“收集”操作，最终使牌有序

【 最低位优先基数排序 用于数字排序的步骤】从 最低位 开始基数排序

  1. 准备10个桶（先进先出的队列，从桶的上面进，下面出）
  2. 按关键字的 个位 ，分流到10个桶中，然后再按顺序收集元素
  3. 按关键字的 十位 ，分流到桶中，然后再按顺序收集元素
  4. 一直下去，直到数字最大值的最高位

【特殊符号】

  1. n：为序列中元素的个数
  2. d：为元素的关键字位数（如930，有三位数，d=3）
  3. rd：关键字每一位的取值范围（如关键字为930，每一位的取值都0-9，所以rd=10）

【时间复杂度】平均和最坏情况下都是O(d(n+rd))

  1. 基数排序的每一趟都要进行“分配”，“收集” → n+rd
    1. 分配：依次对序列中每个关键字进行，即要扫描整个序列 → n
    2. 收集：需要依次对每个桶进行收集，而桶的数量取决于关键字的取值范围 → rd
  2. 基数排序需要d趟（关键字的位数） → d

【空间复杂度】O(rd)：每个桶实际上是一个队列，需要头尾指针，共有rd个桶，所以需要2rd个存放指针的空间

【评价】基数排序适合的 元素很多 的情况，但组成元素的关键字的 取值范围较小 ，如数字0-9是可以接受的

  • 如果关键字取值范围很大，比如26个字母，并且序列中大多数元素的 最高位关键字都不相同，那么这时可以考虑使用 “最高位优先法”。先根据最高位排成若干子序列，然后分别对这些子序列进行直接插入排序