基本思想
不通过比较,计下每个元素的出现次数,统计小于这个元素的个数N,将其放在N位。例如{8,5,9,1,3,2,6}这个序列,有4个小于6的元素,那么6在排序后应该放在数组的第5位。
实现方法
我们来举一个例子,假如绩效考核的总分只有5分,一共有8位同事。那么他们的分数应该在0到5分之间,将这8位同事的分数放在一个数组A[8]中,他们分别是:2,5,3,4,2,1,0,3。
分数从0到5 我们使用大小为6的数组C[6]表示桶,其中下标对应的分数。不过C[6]内存的不是每位同事,而是这个分数对应的个数。我么只需要遍历一边A[8]就可以得到C[6]的值。
个数 | 1 | 1 | 2 | 2 | 1 | 1 |
---|---|---|---|---|---|---|
角标 | 0 | 1 | 2 | 3 | 4 | 5 |
从上面的表格可以看出,分数为3的有2个,小于3分的有4个,所以分数为3分的同事在排序之后的有序数组R[8]中会保存下标 4,5的位置。
那我们如何计算出每个分数的的同事在有序数组中的位置?
思路是这样的: 我们对C[6]数组顺序求和,C[6]存储的数据就编程来下面的这个样子,C[k]里存储小于等于分数k的个数。
小于等于个数 | 1 | 2 | 4 | 6 | 7 | 8 |
---|---|---|---|---|---|---|
角标 | 0 | 1 | 2 | 3 | 4 | 5 |
然后我们从后一次扫描数组A。比如,当扫描到3时,我们可以从数组C中取出下标为3的值6,也就是说,到目前为止,包括自己在内,分数小于3的有6个人,也就是说3是数组R中的第6个元素(数组R下标为5的位置)。当3放入数组R中后,小于3的元素就剩下5个了。所以数组C[3]要减1,变成4.
以此类推扫描下去,当我们扫描完整个数组A后,数组R中的元素就按照从小到大有序排列了。
代码实现
public class CountingSort {
public static void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查找数组中最大的元素
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
int[] c = new int[max + 1];
// 计算每个元素的个数
for (int value : a) {
c[value]++;
}
// 依次累加
for (int i =1; i < c.length; i++) {
c[i] = c[i-1]+c[i];
}
//临时数组r 存储排序后的数据
int[] r = new int[n];
for (int i = n - 1; i >= 0; i--) {
int index = c[a[i]] - 1;
r[index] = a[i];
c[a[i]] --;
}
// 拷贝到数组a中
System.arraycopy(r, 0, a, 0, n);
}
public static void main(String[] args) {
int[] a = {2,5,3,4,2,1,0,3};
countingSort(a,a.length);
System.out.println(Arrays.toString(a));
}
}
打赏