基数排序之代码解析

        基数排序是生活中咱们写程序用的比较少的排序，但是这个排序比较巧妙，今天就给大家讲一讲，原理都在代码里面，下面会给一些解释。

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 数组的前一个位置。

上面是整段核心代码的解释，通过这段代码的解释，可以 把整个流程都搞明白了