数据结构之基数排序

  基数排序的思想是按组成关键字的各个数位的值进行排序，它是分配排序的一种。在该排序方法中把一个关键字 K_i看成一个 d 元组，即
      K¹_i,K²_i,···,K^d_i
其中，0≤ K^j_i<r，i=1~ n，j=1~d。这里的r 称为基数。若关键字是十进制的，则r=10； 若关键字是八进制的，则r=8。d是关键字的位数，d 值取所有待排序的关键字位数的最大值，其他不足d位的关键字在前面补零。
  在“K¹_i,K²_i，···,K^d_i”中，K¹_i称为最高有效位，K²_i称为次高有效位，K^d_i称为最低有效位。基数排序可以从最高有效位开始，也可以从最低有效位开始。
  基数排序的基本思想是： 设立r个队列，队列的编号分别为 0、1、2、···、r-1。首先按最低有效位的值把 n 个关键字分配到这个队列中；然后按照队列编号从小到大将各队列中的关键字依次收集起来；接着再按次低有效位的值把刚收集起来的关键字分配到r个队列中。重复上述分配和收集过程，直到按照最高有效位分配和收集。这样就得到了一个从小到大有序的关键字序列。为了减少记录移动的次数，队列可以采用链式存储分配。每个链队列设两个指针，分别指向队头和队尾。
  基数排序是一种稳定的排序方法。对于 n 个记录，执行一次分配和收集的时间为 O(n+r)。如果关键字有 d位，则要执行 d遍。所以总的运算时间为 O(d(n+r))。可见，对于不同的基数r，所用的时间是不同的。当r或d 较小时，这种排序方法较为节省时间。另外，基数排序适用干链式分配的记录的排序，其要求的附加存储量是r个队列的头、尾指针，所以附加存储量为 2r个存储单元。由于待排序记录是以链表方式存储的，相对于顺序分配而言，还增加了n 个指针域的空间。