基本思想 构造一个10*n的二维数组，一个长度为n的数组用于存储每次位排序时每个桶子里有多少个元素。 从低位开始，将所有元素放到对应的桶子（对应二维数组那一列），然后将所有元素按桶子编号拿出来，组成新数组，然后按高位处理。 代码
public class RadixSort { public static void radixSort(int[] arr, int d) { int n = 1;// 代表位数对应的数：1,10,100... int k = 0;// 保存每一位排序后的结果用于下一位的排序输入 int length = arr.length; int[][] bucket = new int[10][length];// 排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里 int[] order = new int[10];// 用于保存每个桶里有多少个数字 while (n < d) { for (int num : arr) { // 将数组arr里的每个数字放在相应的桶里 int digit = (num / n) % 10; bucket[digit][order[digit]] = num; order[digit]++; } for (int i = 0; i < 10; i++) {// 将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果 if (order[i] != 0) {// 这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中 for (int j = 0; j < order[i]; j++) { arr[k] = bucket[i][j]; k++; } } order[i] = 0;// 将桶里计数器置0，用于下一次位排序 } n *= 10; k = 0;// 将k置0，用于下一轮保存位排序结果 } } public static void main(String[] args) { int[] a = new int[] { 49, 38, 65, 97, 76, 13, 27, 50 }; radixSort(a, 100); for (int i : a) System.out.print(i + " "); } }时间复杂度 O(d(r+n))
