基数排序-软考在线

基数排序



考试要求：掌握

知识路径： > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 常用的排序算法、查找算法、数值计算、字符串处理、数据压缩算法、递归算法、图的相关算法 > 排序

基数排序的思想是：设立r个队列，队列的编号分别为0,1,2,…,r-1。首先按最低有效位的值，把n个关键字分配到这r个队列中；然后从小到大将各队列中关键字再依次收集起来；接着按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程，直至最高有效位，这样得到了一个从小到大有序的关键字序列。为了减少记录移动的次数，队列可以采用链式存储分配，称为链队列。每个链队列设有两个指针，分别指向队头和队尾。

对于n个记录，执行一次分配和收集的时间为O(n+r)，如果关键字有d位，则要执行d遍，所以总的运算时间为O(d(n+r))。基数排序适用于链式分配的记录的排序，是一种稳定的排序方法。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5