基数排序（JAVA）

算法

---

  开门见山，基数排序是内排序中性格比较怪异的一种，它无需比较和交换，而是按位分配和收集。通俗地讲就是，对各元素先按个位上的数值排序，接着十位，百位……直到最大元素的最高位，从而排序完成。具体算法如下
  1. 求最大位数。由于基数排序是按位排序，所以先要确定最大位数，才能知道排序的趟数。求最大位数的方法是求最大元素的最高位，用循环做比较简单。
  2. 分配。由于每位的取值范围是0-9，因此需要十个容器来装，我们一般用十个队列即可，这十个队列标号为0-9。对于每一趟，我们取每一个元素在该位的数值依次入队。
  3. 收集。在一趟排序完成后，我们按顺序从0-9队列中依次出队收集元素。
  4. 继续进行分配和收集，直到最大位数排序完成。

例子

---

为了方便直观了解算法，这次不举4,1,3,2,5的例子。不妨以324,1234,45,87,4为例：最大位数为4，故要分配和收集四次

第一次分配
第一次收集为：324,1234,4,45,87
第二次分配
第二次收集为：4,324,1234,45,87
第三次分配
第三次收集为：4,45,87,1234,324
第四次分配
第四次收集为：4,45,87,324,1234
已经有序，排序完成

Codes

---

package com.fairy.InnerSort;

import java.util.Scanner;
/**
 * 队列结构
 * @author Fairy2016
 *
 */
class Queue {
    int data[];
    int front;
    int rear;
}
/**
 * 基数排序
 * @author Fairy2016
 *
 */
public class BaseSort {
    
    public static void sort(int a[], int n) {
        //求最大位数
        int count = getNumberCount(getMax(a, n));
        //十个队列，分别存储数位数值为0-9的元素
        Queue [] queues = new Queue[10];
        //各队列初始化
        for(int i = 0; i < 10; i++) {
            queues[i] = new Queue();
            queues[i].data = new int[n];
            queues[i].front = queues[i].rear = -1;
        }
        int m = 1;//m控制取第几位（从个位开始取直到count）
        while(count > 0) {
            for(int i = 1; i <= n; i++) {
                int t = a[i] / m % 10;
                //根据数值分配入队
                queues[t].data[++queues[t].rear] = a[i];
            }
            //从队号0-9顺序出队收集元素
            int s = 1;
            for(int j = 0; j < 10; j++) {
                while(queues[j].front != queues[j].rear) {
                    a[s++] = queues[j].data[++queues[j].front];
                }
                //收集后队列清空，方便下一趟排序
                queues[j].front = queues[j].rear = -1;
            }
            m *= 10;
            count --;
        }
    }
    /**
     * 筛选出最大元素方便确定位数
     * @param a
     * @param n
     * @return
     */
    public static int getMax(int a[], int n) {
        a[0] = a[1];
        for(int i = 2; i <= n; i++) {
            if(a[i] > a[0]) {
                a[0] = a[i];
            }
        }
        return a[0];
    }
    
    /**
     * 求排序元素的最大位数
     * @param t
     * @return
     */
    public static int getNumberCount(int t) {
        int count = 1;
        t = t / 10;
        while(t != 0) {
            count++;
            t /= 10;
        }
        return count;
    }

    public static void Print(int a[], int n) {
        for(int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String args[]) {
        int n;
        int a[];
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            n = scanner.nextInt();
            if(n > 0) {
                a = new int[n+1];
                for(int i=1; i <= n; i++) {
                    a[i] = scanner.nextInt();
                }
                sort(a, n);
                Print(a, n);
            }
        }
        scanner.close();
    }
}

结语

---

  用到了10个队列，易知基数排序的空间复杂度为o(10n)。而其时间复杂度由最大位数count（排序多少趟）和分配收集操作决定。其中每趟的分配操作要遍历序列故时间复杂度为o(n)，每趟的收集操作由r个队列出队决定，故时间复杂度为o(10)。所以每趟分配与收集的时间复杂度为o(n+10)，总的时间复杂度为o(count*(n+r=10))。在各元素位数相近时比较实用，否则将有大批空间是浪费的。