网站访问很慢,扫码进入网站如何做,网站开发销售,辽宁省城乡和住房建设厅老网站基数排序的思想是按组成关键字的各个数位的值进行排序#xff0c;它是分配排序的一种。在该排序方法中把一个关键字 Ki看成一个 d 元组#xff0c;即 K1i,K2i,,Kdi 其中#xff0c;0≤ Kjir#xff0c;i1~ n#xff0c;j1~d。这里的r 称为基数。若关键字是… 基数排序的思想是按组成关键字的各个数位的值进行排序它是分配排序的一种。在该排序方法中把一个关键字 Ki看成一个 d 元组即 K1i,K2i,···,Kdi 其中0≤ Kjiri1~ nj1~d。这里的r 称为基数。若关键字是十进制的则r10 若关键字是八进制的则r8。d是关键字的位数d 值取所有待排序的关键字位数的最大值其他不足d位的关键字在前面补零。 在“K1i,K2i···,Kdi”中K1i称为最高有效位K2i称为次高有效位Kdi称为最低有效位。基数排序可以从最高有效位开始也可以从最低有效位开始。 基数排序的基本思想是 设立r个队列队列的编号分别为 0、1、2、···、r-1。首先按最低有效位的值把 n 个关键字分配到这个队列中然后按照队列编号从小到大将各队列中的关键字依次收集起来接着再按次低有效位的值把刚收集起来的关键字分配到r个队列中。重复上述分配和收集过程直到按照最高有效位分配和收集。这样就得到了一个从小到大有序的关键字序列。为了减少记录移动的次数队列可以采用链式存储分配。每个链队列设两个指针分别指向队头和队尾。 基数排序是一种稳定的排序方法。对于 n 个记录执行一次分配和收集的时间为 O(nr)。如果关键字有 d位则要执行 d遍。所以总的运算时间为 O(d(nr))。可见对于不同的基数r所用的时间是不同的。当r或d 较小时这种排序方法较为节省时间。另外基数排序适用干链式分配的记录的排序其要求的附加存储量是r个队列的头、尾指针所以附加存储量为 2r个存储单元。由于待排序记录是以链表方式存储的相对于顺序分配而言还增加了n 个指针域的空间。
