基本思想

不通过比较,计下每个元素的出现次数,统计小于这个元素的个数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]的值。

个数112211
角标012345

从上面的表格可以看出,分数为3的有2个,小于3分的有4个,所以分数为3分的同事在排序之后的有序数组R[8]中会保存下标 4,5的位置。

那我们如何计算出每个分数的的同事在有序数组中的位置?

思路是这样的: 我们对C[6]数组顺序求和,C[6]存储的数据就编程来下面的这个样子,C[k]里存储小于等于分数k的个数。

小于等于个数124678
角标012345

然后我们从后一次扫描数组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));
    }
}

打赏
支付宝 微信
上一篇 下一篇