友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
排序
.10. 基数排序
基数排序通过从低位到高位，对数字的每一位进行排序来获得排序结果。比较适合数量不多，但是每个数字之间相差很大的情况。而且时间复杂度是 \(O(nk)\)，n 表示数量， k 表示最大位数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* 基数排序
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-29 15:45:01
*/
public void radixSort(int[] array) {
if (null == array || array.length < 2) {
return;
}
int max = Arrays.stream(array).max().orElse(0);
int length = array.length;
for (int exp = 1; exp < max; exp *= 10) {
int[] counter = new int[10];
for (int num : array) {
// 获取指定位的值
int digit = (num / exp) % 10;
counter[digit]++;
}
// 将数量从小向大汇总，
// 稍作处理即可映射出每个数字应该存储的坐标
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 存储临时结果
int[] temp = new int[length];
for (int i = length - 1; i >= 0; i--) {
int digit = (array[i] / exp) % 10;
// counter[digit] 是一个数量统计，-1 是指向应该存储的坐标
int index = counter[digit] - 1;
temp[index] = array[i];
counter[digit]--;
}
for (int i = 0; i < length; i++) {
array[i] = temp[i];
}
}
}