漳州正规网站建设,做网站九州科技,上海网页设计服务,南翔企业网站开发建设基数排序是生活中咱们写程序用的比较少的排序#xff0c;但是这个排序比较巧妙#xff0c;今天就给大家讲一讲#xff0c;原理都在代码里面#xff0c;下面会给一些解释。
import java.util.Arrays;public class Code04_RadixSort {// only for no-negative valuepublic s… 基数排序是生活中咱们写程序用的比较少的排序但是这个排序比较巧妙今天就给大家讲一讲原理都在代码里面下面会给一些解释。
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 数组的前一个位置。 上面是整段核心代码的解释通过这段代码的解释可以 把整个流程都搞明白了
