排序——基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较

package base;import java.util.Arrays;public class BaseSort {
    public static void main(String[] args) {
    int[] arr = new int[]{
    100, 1022, 2, 22};int digit = countBiggestDigit(arr);baseSort(arr, 0, arr.length - 1, digit);System.out.println(Arrays.toString(arr));}/*1、count数组，统计词频，按前缀和累加的方式2、help 辅助数组*/public static void baseSort(int[] arr, int left, int right, int digit) {
    final int countSize = 10;// count 数组统计词频// count 数组前缀和// 倒序遍历数组，根据该位数所在下标位置，找到下标位置// 辅助数组的值赋给 源数组int[] help = new int[right - left + 1];for (int i = 1; i <= digit; i++) {
    // count[0] 当前位 i位是0的数字有多少个// count[1] 当前位 i位是0、1的数字有多少个// count[2] 当前位 i位是0、1、2的数字有多少个int[] count = new int[countSize];for (int j = left; j <= right; j++) {
    // 获取位数上的数字，如获取个位数int numberOfDigit = getDigit(arr[j], i);count[numberOfDigit] = count[numberOfDigit] + 1;}for (int j = 1; j < countSize; j++) {
    count[j] = count[j] + count[j - 1];}for (int j = right; j >= left; j--) {
    int numberOfDigit = getDigit(arr[j], i);count[numberOfDigit] = count[numberOfDigit] - 1;help[count[numberOfDigit]] = arr[j];}for (int j = 0; j < help.length; j++) {
    arr[left + j] = help[j];}}}/*** 获取数组中最大的位数*/public static int countBiggestDigit(int[] arr) {
    int digit = 0;for (int i = 0; i < arr.length; i++) {
    int curDigit = 0;int num = arr[i];while (num != 0) {
    curDigit++;num = num / 10;}digit = Math.max(digit, curDigit);}return digit;}/*** 获取数字，某个位数上的数字* 如 num = 103 ，digit = 1，返回值为3** @param num* @param digit* @return*/public static int getDigit(int num, int digit) {
    int result = 0;for (int i = 0; i < digit; i++) {
    result = num % 10;num = num / 10;}return result;}
}