7.5.2 基数排序

基数排序是一种很特别的排序方法，它不是基于比较进行排序的，而是采用多关键字排序思想，借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。

以r为基数的最低位优先基数排序的过程：

假设线性表由结点序列a0,a1,……an-1构成，每个结点aj的关键字由d元组[{ k((d-1j),k(d-2,j),……,k(1,j),k(0,j) }组成，

其中0<=k(i,j)<=r-1   (0<=j<n,0<=i<=d-1).

在排序过程中，使用r个队列Q0,Q1,……Qr-1。排序过程如下：

对i=0,1,……，d-1,依次做一次“分配”和“收集”（其实就是一次稳定的排序过程）。

分配：开始时，把Q0,Q1,……，Qr-1各个队列置成空队列，然后依次考察线性表中的每一个结点aj(j=0,1,……，n-1),如果aj的关键字k(i,j)=k，就把aj放进Qk队列中。

收集：把Q0,Q1，……Qr-1各个队列中的结点依次首尾相连，得到新的结点序列，从而组成新的线性表

原始序列：329—>457—>657—>839—>436—>720—>355

1、按个位分配

收集：720—>355—>436—>457—>657—>329—>839

2、按十位分配

收集：720—>329—>436—>839—>355—>457—>657

3、按百位分配

收集：329—>355—>436—>457—>657—>720—>839

空间效率：一趟排序需要的辅助空间为r(r个队列)，但以后的排序中重复使用这些队列，所以基数排序的空间复杂度为O(r).

时间效率：基数排序需要进行d趟分配和收集，一趟分配需要O(n),一趟收集需要O(r),所以基数排序的时间复杂度为O(d(n+r))，它与序列的初始状态无关。

稳定性：对于基数排序算法而言，很重要一定是按位排序时必须是稳定的，因此，这也保证了基数排序保持稳定性。