Java版基数排序[稳定]

原理：分配加收集

复杂度： O(d(n+r)) r为基数d为位数 空间复杂度O(n+r)

// 基数排序public void radixSort(int[] a, int begin, int end, int digit) {// 基数final int radix = 10;// 桶中的数据统计int[] count = new int[radix];int[] bucket = new int[end-begin+1];// 按照从低位到高位的顺序执行排序过程for (int i = 1; i <= digit; i++) {// 清空桶中的数据统计for (int j = 0; j < radix; j++) {count[j] = 0;}// 统计各个桶将要装入的数据个数for (int j = begin; j <= end; j++) {int index = getDigit(a[j], i);count[index]++;}// count[i]表示第i个桶的右边界索引for (int j = 1; j < radix; j++) {count[j] = count[j] + count[j - 1]; }// 将数据依次装入桶中 // 这里要从右向左扫描，保证排序稳定性 for (int j = end; j >= begin; j--) {int index = getDigit(a[j], i);bucket[count[index] - 1] = a[j];count[index]--;}// 取出，此时已是对应当前位数有序的表for (int j = 0; j < bucket.length; j++) {a[j] = bucket[j];}}}// 获取x的第d位的数字，其中最低位d=1private int getDigit(int x, int d) {String div = "1";while (d >= 2) {div += "0";d--;}return x/Integer.parseInt(div) % 10;}}