链式基数排序java

### Java 链式基数排序的实现

链式基数排序是一种非比较型整数排序算法，适用于处理具有固定位数范围的数据。该方法通过分配桶来存储相同位数值的对象，并按顺序收集这些对象形成新的列表。

#### 基本原理
对于每一个待排序的关键字位置（个位、十位...），将所有记录按照当前关键字值放入对应的队列中；之后再依次取出各队列中的元素重新组成一个序列。重复上述过程直到最高位为止[^3]。

#### Java 实现代码示例
下面展示了一个基于单向链表结构的Java版本链式基数排序：

import java.util.LinkedList;
import java.util.Queue;

class ListNode {
    int val;
    ListNode next;
    
    public ListNode(int v){
        this.val = v;
        this.next = null;
    }
}

public class RadixSortLinkedList {

    private static final int BASE = 10; // 十进制
    
    /**
     * 对给定头节点指向的链表执行链式基数排序.
     */
    public static void radixSort(ListNode head) {
        if (head == null || head.next == null) return;

        Queue<ListNode>[] buckets = new LinkedList[BASE];
        for (int i = 0; i < BASE; ++i)
            buckets[i] = new LinkedList<>();

        int maxVal = getMaxValue(head);
        
        for (long exp = 1L; maxVal / exp > 0; exp *= BASE) {            
            distributeIntoBuckets(buckets, head, exp);           
            collectFromBuckets(buckets, head);
        }       
    }

    /** 获取最大值用于确定循环次数 **/
    private static int getMaxValue(ListNode node) {
        int maxValue = Integer.MIN_VALUE;
        while(node != null){
            if(maxValue < node.val)
                maxValue = node.val;
            node = node.next;
        }
        return maxValue;
    }

    /** 将节点分发至各个桶内 **/
    private static void distributeIntoBuckets(Queue<ListNode>[] buckets,
                                             ListNode head,long exp) {
        ListNode current = head;
        do{
            int index = (int)((current.val/exp)%BASE);
            buckets[index].offer(current);
            current = current.next;
        }while(current!=null && current.next!=null);

        // 处理最后一个结点
        if(current!=null){
            int index=(int)((current.val/exp)%BASE);
            buckets[index].offer(current);
        }
    }

    /** 收集来自不同桶内的数据并重组链表**/
    private static void collectFromBuckets(Queue<ListNode>[] buckets,
                                          ListNode head) {
        ListNode tail = null;
        for (Queue<ListNode> bucket : buckets) {
            while (!bucket.isEmpty()) {
                ListNode temp = bucket.poll();
                
                if(tail==null){ 
                    head=temp;
                }else{  
                    tail.next=temp;
                }
                tail=temp;
            }
        }
        tail.next=null;
    }
}

此程序首先创建了十个`Queue`实例作为“桶”，用来临时保存每一轮迭代过程中属于同一类别的节点。接着遍历整个链表，根据指定权重(`exp`)计算出每个节点应该放置在哪一个桶里。最后再次遍历所有的桶并将其中的内容连接起来构成最终有序的结果。