2public class RadixSort implements IArraySort {
3
4 @Override
5 public int[] sort(int[] sourceArray) throws Exception {
6 // 对 arr 进行拷贝，不改变参数内容
7 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
8
9 int maxDigit = getMaxDigit(arr);
10 return radixSort(arr, maxDigit);
11 }
12
13 /**
14 * 获取最高位数
15 */
16 private int getMaxDigit(int[] arr) {
17 int maxValue = getMaxValue(arr);
18 return getNumLenght(maxValue);
19 }
20
21 private int getMaxValue(int[] arr) {
22 int maxValue = arr[0];
23 for (int value : arr) {
24 if (maxValue < value) {
25 maxValue = value;
26 }
27 }
28 return maxValue;
29 }
30
31 protected int getNumLenght(long num) {
32 if (num == 0) {
33 return 1;
34 }
35 int lenght = 0;
36 for (long temp = num; temp != 0; temp /= 10) {
37 lenght++;
38 }
39 return lenght;
40 }
41
42 private int[] radixSort(int[] arr, int maxDigit) {
43 int mod = 10;
44 int dev = 1;
45
46 for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
47 // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
48 int[][] counter = new int[mod * 2][0];
49
50 for (int j = 0; j < arr.length; j++) {
51 int bucket = ((arr[j] % mod) / dev) + mod;
52 counter[bucket] = arrayAppend(counter[bucket], arr[j]);
53 }
54
55 int pos = 0;
56 for (int[] bucket : counter) {
57 for (int value : bucket) {
58 arr[pos++] = value;
59 }
60 }
61 }
62
63 return arr;
64 }
65 private int[] arrayAppend(int[] arr, int value) {
66 arr = Arrays.copyOf(arr, arr.length + 1);
67 arr[arr.length - 1] = value;
68 return arr;
69 }
70}
GitHub Repo：Sort Article
Follow: MisterBooo · GitHub