基数排序分析

在排序算法里，我们总习惯说 “快排是平均效率最高的”，但在某些场景下 —— 比如给手机号排序、给 10 万条 “0-9999” 的数字排序 ——基数排序的速度会远超快排。

原因很简单：基数排序是 “非比较排序”，不需要通过元素间的比较来确定顺序，而是靠 “按位分组” 实现排序，时间复杂度能稳定在 O (n*k)（k 是数字的位数）。

基数排序的核心其实就是把数字按每一位（个位、十位、百位…）拆开来排序。

代码逻辑

1.找最小值（处理负数）

考虑到如果数组有负数，按位提取会出问题，所以需要先把所有数转成非负。

1
2
3
4


int min = arr[0];
for (int i = 1; i < n; i++) {
    min = Math.min(min, arr[i]);
}

2.平移数组 + 找最大值

平移后数组使得所有元素均≥0；

记录最大值max，是为了通过bits(max)计算 “需要排序几轮”。

1
2
3
4
5


int max = 0;
for (int i = 0; i < n; i++) {
    arr[i] -= min; 
    max = Math.max(max, arr[i]);
}

3.bits（计算位数）

1
2
3
4
5
6
7
8


public static int bits(int number) {
    int ans = 0;
    while (number > 0) {
        ans++;
        number /= BASE;
    }
    return ans;
}

4.radixSort（按位排序）

 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


public static void radixSort(int[] arr, int n, int bits) {
		// offset：当前处理的位数（比如：1=个位，10=十位，100=百位...）
		for (int offset = 1; bits > 0; offset *= BASE, bits--) {
			// 初始化计数数组（每次处理新的位，都要清空）
			Arrays.fill(cnts, 0);
			// 统计当前位（offset对应的位）上，0~BASE-1的出现次数
			for (int i = 0; i < n; i++) {
				// 提取arr[i]在当前位的数字
				int digit = (arr[i] / offset) % BASE;
				cnts[digit]++; 
			}

			// 将计数数组转为“前缀和数组”（确定元素在help中的位置）
			for (int i = 1; i < BASE; i++) {
				cnts[i] += cnts[i - 1];
			}

			// 逆序遍历原数组，填充辅助数组help
			for (int i = n - 1; i >= 0; i--) {
				// 再次提取当前位数字
				int digit = (arr[i] / offset) % BASE;
				// 前缀和-1：得到当前元素在help中的索引
				help[--cnts[digit]] = arr[i];
			}

			// 将辅助数组的结果复制回原数组（完成当前位的排序）
			for (int i = 0; i < n; i++) {
				arr[i] = help[i];
			}
		}
	}

完整代码 链接：https://pan.quark.cn/s/3071ab17556e