闸北区网站建设网页设360排名优化工具
基数排序是生活中咱们写程序用的比较少的排序，但是这个排序比较巧妙，今天就给大家讲一讲，原理都在代码里面，下面会给一些解释。
import java.util.Arrays;public class Code04_RadixSort {// only for no-negative valuepublic static void radixSort(int[] arr) {if (arr == null || arr.length < 2) {return;}radixSort(arr, 0, arr.length - 1, maxbits(arr));}public static int maxbits(int[] arr) {int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);}int res = 0;while (max != 0) {res++;max /= 10;}return res;}// arr[L..R]排序 , 最大值的十进制位数digitpublic static void radixSort(int[] arr, int L, int R, int digit) {final int radix = 10;int i = 0, j = 0;// 有多少个数准备多少个辅助空间int[] help = new int[R - L + 1];for (int d = 1; d <= digit; d++) {// 有多少位就进出几次// 10个空间// count[0] 当前位(d位)是0的数字有多少个// count[1] 当前位(d位)是(0和1)的数字有多少个// count[2] 当前位(d位)是(0、1和2)的数字有多少个// count[i] 当前位(d位)是(0~i)的数字有多少个int[] count = new int[radix]; // count[0..9]for (i = L; i <= R; i++) {// 103 1 3// 209 1 9j = getDigit(arr[i], d);count[j]++;}for (i = 1; i < radix; i++) {count[i] = count[i] + count[i - 1];}for (i = R; i >= L; i--) {j = getDigit(arr[i], d);help[count[j] - 1] = arr[i];count[j]--;}for (i = L, j = 0; i <= R; i++, j++) {arr[i] = help[j];}}}public static int getDigit(int x, int d) {return ((x / ((int) Math.pow(10, d - 1))) % 10);}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {
// int testTime = 500000;
// int maxSize = 6;
// int maxValue = 100000;
// boolean succeed = true;
// for (int i = 0; i < testTime; i++) {
// int[] arr1 = generateRandomArray(maxSize, maxValue);
// int[] arr2 = copyArray(arr1);
// radixSort(arr1);
// comparator(arr2);
// if (!isEqual(arr1, arr2)) {
// succeed = false;
// printArray(arr1);
// printArray(arr2);
// break;
// }
// }
// System.out.println(succeed ? "Nice!" : "Fucking fucked!");
//
// int[] arr = generateRandomArray(maxSize, maxValue);int[] arr = new int[]{2,1,5,3,7};printArray(arr);radixSort(arr);printArray(arr);}}
上面是基数排序的整段代码，其实最核心的还是下面部分：
public static void radixSort(int[] arr, int L, int R, int digit) {final int radix = 10;int i = 0, j = 0;// 有多少个数准备多少个辅助空间int[] help = new int[R - L + 1];for (int d = 1; d <= digit; d++) {// 有多少位就进出几次// 10个空间// count[0] 当前位(d位)是0的数字有多少个// count[1] 当前位(d位)是(0和1)的数字有多少个// count[2] 当前位(d位)是(0、1和2)的数字有多少个// count[i] 当前位(d位)是(0~i)的数字有多少个int[] count = new int[radix]; // count[0..9]for (i = L; i <= R; i++) {// 103 1 3// 209 1 9j = getDigit(arr[i], d);count[j]++;}for (i = 1; i < radix; i++) {count[i] = count[i] + count[i - 1];}for (i = R; i >= L; i--) {j = getDigit(arr[i], d);help[count[j] - 1] = arr[i];count[j]--;}for (i = L, j = 0; i <= R; i++, j++) {arr[i] = help[j];}}}
for (i = R; i >= L; i--): 这是一个循环，从数组中的右端（R）向左端（L）遍历。
j = getDigit(arr[i], d): 这一行代码用于获取第i个元素arr[i]在第d位上的数字j。通常，getDigit函数会根据位数d来提取数字。例如，如果d是个位数，那么getDigit可能会返回arr[i]的个位数字；如果d是十位数，那么它可能会返回arr[i]的十位数字，以此类推。
help[count[j] - 1] = arr[i]: 这行代码将第i个元素arr[i]放入辅助数组help中的合适位置。count[j]表示第j个数字在当前位数d上的出现次数，通过count[j] - 1找到j在help数组中的合适位置，然后将arr[i]放入这个位置。
count[j]--: 在将arr[i]放入help数组后，将count[j]减一，以便下一个相同数字的元素（如果有的话）可以放入help数组的前一个位置。
上面是整段核心代码的解释，通过这段代码的解释，可以 把整个流程都搞明白了