【Java】基数排序

基数排序是指借助对多关键码进行分配和收集的思想对单关键码进行排序。

多关键码排序有两类：最主位优先（MSD）、最次位优先（LSD）。

下面是编码实现（Java）：

首先是需要使用LinkedList定义的Node：

public class LinkedNode {
    
    //定义结点泛型数据域
    private T data;
    
    //定义结点后继引用域
    private LinkedNode next;
    
    //无参构造函数，构造空结点
    public LinkedNode() {
        data = null;
        next = null;
    }
    
    //构造数据域为element的结点
    public LinkedNode(T element) {
        data = element;
        next = null;
    }

    public T getData() {
        return data;
    }

    public void setData(T element) {
        this.data = element;
    }

    public LinkedNode getNext() {
        return next;
    }

    public void setNext(LinkedNode successor) {
        this.next = successor;
    }
    
}

实现类

public class RadixSortDemo {
    
    /**
     * 基数排序算法
     * @param first
     * @param digit 记录的位数
     */
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static void radixSort(LinkedNode first, int digit) {
        //存储队头引用
        LinkedNode[] front = new LinkedNode[10];
        //存储队尾引用
        LinkedNode[] rear  = new LinkedNode[10];
        //首尾相接时引用队尾
        LinkedNode tail = new LinkedNode();
        //base为被除数
        int key, base = 1;
        for (int i = 1; i