|
|
知识路径: > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 常用的排序算法、查找算法、数值计算、字符串处理、数据压缩算法、递归算法、图的相关算法 > 排序 >
|
相关知识点:10个
|
|
|
|
基数排序的思想是:设立r个队列,队列的编号分别为0,1,2,…,r-1。首先按最低有效位的值,把n个关键字分配到这r个队列中;然后从小到大将各队列中关键字再依次收集起来;接着按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程,直至最高有效位,这样得到了一个从小到大有序的关键字序列。为了减少记录移动的次数,队列可以采用链式存储分配,称为链队列。每个链队列设有两个指针,分别指向队头和队尾。
|
|
|
对于n个记录,执行一次分配和收集的时间为O(n+r),如果关键字有d位,则要执行d遍,所以总的运算时间为O(d(n+r))。基数排序适用于链式分配的记录的排序,是一种稳定的排序方法。
|
|
|
|
|
|
|
|
|
|
|
|