排序－基数

基数排序是种与众不同的排序方法，它不是基于比较和交换。其理论时间效率是O(n)。
基数排序的基本想法是将每个数字按照一定的基数拆分，然后根据每一位将数据反复排序。

例如：
    代排序数组:{7,3,1,5,4}
    基数:2

用基数表示源排序数组:{111,011,001,101,100}
首先按照第0位（从右边数起）,根据0位是0,还是1将数组中数据放入0队列或1队列中，然后再将数据从两个队列中取出，这样便完成了对0位的排序。
    此时数组变成了{100,111,011,001,101}
然后在按照此算法对第1位操作：
    此时数组变成了{100,001,101,111,011}
然后在按照此算法对第2位操作：
    此时数组变成了{001,011,100,101,111}
没有更高的位数，排序结束。
    翻译成十进制:{1,3,4,5,7}

基数排序时间与n成正比，也和数值的相对于基数的倍数成正比。
但当排序数据量比较大的情况下，一般来说，数值用基数表示的位数也会相应变大。一般来说实际中基数排序一般会蜕化到O(n * log n)

注意基数选取多少都可以，但是用2的幂可以直接使用位操作，大部分计算机位操作的速度都比较快。另外基数排序只能排列关键值为整数的数据。

排序过程中需要使用队列，为了简单期间，此处使用了用数组作为底层数据结构支撑的队列，但这样对空间浪费较大，实际中可以考虑使用用链表作为底层数据结构支撑的队列，关于队列的数据结构请参见（LinkedQueue 队 ，Queue 队 ）

 

class Queue {   
    int[] values;   
    int head = -1;   
    int tail = -1;   
    Queue(int size) {   values  = new int[size]; }   
    boolean isEmpty() { return head == tail; }   
    void put(int value) {   values[++head] = value; };   
    int get() { return values[++tail]; };   
    void clean() { head = -1; tail = -1; }   
}   
  
class Radix {   
    public static void main(String[] args) {   
        int[] a = {6,4,3,2,4,1,2};   
        sort(a,4);   
        println(a);   
    }   
  
    /**  
     * @param radix 2的幂  
     * @param a 源数据数组  
     */  
    public static void sort(int[] a,int radix) {   
        int base = 1<<radix;   
        Queue[] q = new Queue[base];   
        for(int i=0; i<base; i++) {         
            q[i] = new Queue(a.length);   
        }   
  
        int bit = 0;   
        int sum;   
        do {   
            sum = 0; //判断是否要再继续   
            for(int i: a) {   
                int remain = i >> bit;   
                q[remain&(base - 1)].put(i);   
                sum |= remain;   
            }   
            bit += radix;   
            //从队列中取出数据，放入原数组中   
            int i = 0;   
            for(int j=0; j<q.length; j++) {   
                while(!q[j].isEmpty()) a[i++] = q[j].get();   
                q[j].clean();   
            }   
        } while(sum > 0);   
    }   
  
    public static void println(int[] a) {   
        for(int i: a) System.out.print(i + " ");   
        System.out.println();   
    }   
}