Contents

从低位往高位进行分组，组合，用到了队列和链表

可以参考下严蔚敏那本教材里的图

package ysj;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.concurrent.TimeUnit;

public class Test {

	// d为数据长度
	private static void radixSorting(int[] arr, int length, int d) {
	    for (int i = 0; i < d; i++) {
	        arr = radixSort(arr, length, i); // 按照d位进行排序
	        print(arr, i + 1, d);
	    }
	}

	// 把每次按位排序的结果打印出来
	static void print(int[] arr, int k, int d) {
	    if (k == d)
	        System.out.println("最终排序结果为：");
	    else
	        System.out.println("按第" + k + "位排序后，结果为：");
	    for (int t : arr) {
	        System.out.print(t + " ");
	    }
	    System.out.println();
	}

	// 进行排序
	private static int[] radixSort(int[] arr, int length, int expIndex) {
	    List<LinkedList<Integer> > queues = new ArrayList<LinkedList<Integer> >(10);
	    for(int i = 0; i < 10; i++){
	    	queues.add(new LinkedList<Integer>());
	    }
	    
		for(int i = 0; i < arr.length; i++){
			queues.get(getBitData(arr[i], expIndex)).offer(arr[i]);
		}
		int [] arr2 = new int[length];
		int k = 0;

		for(Queue<Integer> que : queues){
			while(!que.isEmpty()){
				arr2[k++] = que.poll();
			}
		}
		
	    return arr2;
	}

	// 获取data指定位的数
	private static int getBitData(int data, int expIndex) {
	    while (data != 0 && expIndex > 0) {
	        data /= 10;
	        expIndex--;
	    }
	    return data % 10;
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 326, 453, 608, 835, 751, 435, 704, 690, 88, 79,
		        79 };
		System.out.println("基数排序前为：");
		for (int t : arr) {
		    System.out.print(t + " ");
		}
		System.out.println();
		radixSorting(arr, arr.length, 4);
	}
}