简介
用来排序0~100数字最好的算法, 可以在基数排序中更有效的排序范围较大的数组
算法实现
思路图示
具体步骤
最大/小值: 找出Arr(待排序的数组)中最大(max)和最小(min)的元素；- 创建计数数组C, 长度是 K (K = max - min + 1)
计数: 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；累加C中数据进行累加(c[i]=c[i]+c[i-1]), 累加结束 c[i] 则代表 数字(i + min) 最终存储下标填充B：将每个元素(i+min)放在新数组B的第C(i)项，每放一个元素就将C(i)减去1。
算法图示
最大/小值 , 计数 , 累加
填充
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
public static int[] sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr;
}
// 找出最大值和最小值
int max = 0;
int min = 0;
for (int i : arr) {
max = Math.max(max, i);
min = Math.min(min, i);
}
int k = max - min + 1;
int[] c = new int[k];
// 计数
int length = arr.length;
for (int i = 0; i < length; i++) {
c[arr[i] - min] = c[arr[i] - min] + 1;
}
// 求和
for (int i = 1; i < k; i++) {
c[i] = c[i] + c[i - 1];
}
// 回填
int[] b = new int[length];
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
int index = c[num - min] - 1;
c[num - min]--;
b[index] = num;
}
return b;
}
时间复杂度
O(n+k)
f(n) = n(最大/小) + n(计数) + k(求和) + n(回填) = 3n + k = O(n+k)
空间复杂度
O(n+k)
f(n) = n(数组B) + k(数组c) = O(n+k)
