当前课程知识点：数据结构 > 第9章 内部排序 > 9.7 基数排序 > 9.7 基数排序
同学们，大家好
我是云南大学信息学院教师孔兵
这节课我们讨论基数排序
基数排序的思路是借助多关键字排序的思想
对单关键字进行排序的方法
我先介绍一下多关键字排序，看一个扑克牌的引例
假设要把一副扑克牌排成这样自小到大的次序
草花2草花3到草花a，方块2方块3到方块a
红桃2到红桃a，黑桃2到黑桃a
每张扑克牌上可以看作有两个关键字
一个关键字是花色，另外一个是面值
从上述次序观察，花色的地位大于面值
怎么对扑克牌做这样的排序呢？
有2种方法
第1种方法是按照花色把扑克牌分为4堆
随后在每堆的内部再按面值进行排序
达到要求的排序结果
这种方法称为最高位关键字优先
第2种方式是按照面值把扑克牌分为13堆
每堆中包含同面值的4张扑克牌，这步称为分配
随后呢，将这13堆按照面值自小到大叠在一起
这步称为收集；再按花色把扑克牌分配4堆
最后将这4堆牌按花色自小到大收集
收集后的扑克牌达到要求的排序结果
这种方法按照面值和花色进行了两趟分配和收集
完成排序，因为首先处理较低的关键字面值
这种方法称为最低位关键字优先
链式基数排序就是借助多关键字排序方法中
最低位关键字优先的方法对单关键字进行排序
排序的思路是
把单逻辑关键字看成由若干个关键字复合而成
借助“分配”和“收集”两种操作对单逻辑关键字进行排序
把单逻辑关键字看成由若干个关键字复合而成是怎么回事？
看一个例子，关键字为3位的十进制整数
如258，可以看成由百位的2
十位的5和个位的8三个只有1位的关键字复合而成
从数值的大小可知，这3个1位的关键字地位是不一样的
百位大于十位，十位大于个位，个位最低
基于这样的认识，我们可以借助多关键字排序的方法
利用3趟分配和收集
对3位十进制整数的关键字进行排序
分配和收集的过程需要对排序的记录多次移动和重组
我们采用链式结构存储待排序的记录
从最低关键字开始，每趟分配和收集处理1位关键字
首先按这位关键字的值分配到相应的堆
1位十进制数的值是0到9，总共有10堆
每堆中的记录组织成一个无头结点的单链表
为了指示这10个单链表，设计了两个指针数组f和e
每个数组有10个单元，f[0]指向0堆的首元结点
e[0]指向0堆的尾结点，其它单元的情况一样
初始时两个数组中的指针都置空
设计两个指针数组给分配和收集带来很大的便利
结合例子看一下分配和收集的过程
例子中有10个记录，存储在单链表中
情形如图1所示
第1趟按最低关键字个位进行分配和收集
从链表中依次取下每个结点
按个位数的值分配到对应的堆中
分配后的结果如图2所示
其中0,3,4,5,8,9堆中有记录，其他堆为空
从0堆开始，自小到大
把非空的链表依次串联收集起来
结果如图3所示。观察图3中的链表
我们注意到，记录的关键字按最低位有序
第2趟按次低关键字十位进行分配和收集
收集后可以看到，记录的关键字按十位和个位有序
第3趟按最高关键字百位进行分配和收集
收集后可以看到，记录按关键字有序
经3趟的分配和收集完成了整个序列的排序
看一下基数排序时间复杂度
假设每个记录含有d个关键字（例子中为3）
每个关键字的取值范围为rd（例子中是10）
每趟分配的时间复杂度为O(n)
每趟收集的时间复杂度为O(rd)
整个排序需要d趟分配和收集
所以，基数排序的时间复杂度为O(d(n+rd))
好同学们，基数排序我们就介绍到这儿
下次课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
