1
public class Code02_RadixSort {
2

3
  // 可以设置进制，不一定10进制，随你设置
4
  public static int BASE = 10;
5

6
  public static int MAXN = 50001;
7

8
  public static int[] help = new int[MAXN];
9

10
  public static int[] cnts = new int[BASE];
11

12
  public static int[] sortArray(int[] arr) {
13
    if (arr.length > 1) {
14
      // 如果会溢出，那么要改用long类型数组来排序
15
      int n = arr.length;
16
      // 找到数组中的最小值
17
      int min = arr[0];
18
      for (int i = 1; i < n; i++) {
19
        min = Math.min(min, arr[i]);
20
      }
21
      int max = 0;
22
      for (int i = 0; i < n; i++) {
23
        // 数组中的每个数字，减去数组中的最小值，就把arr转成了非负数组
24
        arr[i] -= min;
25
        // 记录数组中的最大值
26
        max = Math.max(max, arr[i]);
27
      }
28
      // 根据最大值在BASE进制下的位数，决定基数排序做多少轮
29
      radixSort(arr, n, bits(max));
30
      // 数组中所有数都减去了最小值，所以最后不要忘了还原
31
      for (int i = 0; i < n; i++) {
32
        arr[i] += min;
33
      }
34
    }
35
    return arr;
36
  }
37

38
  // 返回number在BASE进制下有几位
39
  public static int bits(int number) {
40
    int ans = 0;
41
    while (number > 0) {
42
      ans++;
43
      number /= BASE;
44
    }
45
    return ans;
46
  }
47

48
  // 基数排序核心代码
49
  // arr内要保证没有负数
50
  // n是arr的长度
51
  // bits是arr中最大值在BASE进制下有几位
52
  public static void radixSort(int[] arr, int n, int bits) {
53
    // 理解的时候可以假设BASE = 10
54
    for (int offset = 1; bits > 0; offset *= BASE, bits--) {
55
      Arrays.fill(cnts, 0);
56
      for (int i = 0; i < n; i++) {
57
        // 数字提取某一位的技巧
58
        cnts[(arr[i] / offset) % BASE]++;
59
      }
60
      // 处理成前缀次数累加的形式
61
      for (int i = 1; i < BASE; i++) {
62
        cnts[i] = cnts[i] + cnts[i - 1];
63
      }
64
      for (int i = n - 1; i >= 0; i--) {
65
        // 前缀数量分区的技巧
66
        // 数字提取某一位的技巧
67
        help[--cnts[(arr[i] / offset) % BASE]] = arr[i];
68
      }
69
      for (int i = 0; i < n; i++) {
70
        arr[i] = help[i];
71
      }
72
    }
73
  }
74
}