本文主要是介绍【算法】计数排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

对数组 [4,1,5,0,8,3,7,5,1] 进行排序，我们可以开辟一大小为10的辅组数组空间help[10]，初值均为0。扫描数组，扫描到4，help[4]+1；扫描到1，help[1]+1；扫描到5，……。最后整个help数组是[1,2,0,1,1,2,0,1,1,0]。扫描help数组，元素非0代表着与下标值相同的这个数存在，个数等于元素值，能得到排序结果： [0,1,1,3,4,5,5,7,8]。

计数排序就是这种不基于比较的排序，只不过对上面举例的方法进行了更进一步改进。

算法描述

1. 找出待排序数组中的最大值Max和最小值Min，构建大小为 Max-Min+1 辅助数组 help[]
2. 统计待排序数组中每个值为 i 的元素出现的次数，存入辅助数组 help 的第 i-Min 位置
3. help[i] 累加其之前所有计数，也即从第二项开始 help[i] += help[i-1]
4. 反向遍历原始数组，扫描到值 i 时，根据 help[i-Min] 找到 i 在结果数组应该排在第几位。

限制：输入的元素必须要属于有限集合。

时间复杂度为O(n+k)，空间复杂度为O(n+k)。n为待排序数组的规模，k为辅助数组的规模。

例如在上面的例子中[4,1,5,0,8,3,7,5,1]的最大值为8，最小值是0，可以构建大小为9的辅助数组help，统计值次数后，help数组为[1,2,0,1,1,2,0,1,1]，累加计数后help数组为[1,3,3,4,5,7,7,8,9]。下面详细描述反向遍历原始数组过程：

1. 扫描到值 1 时，help[1-0] = 3，help[1-0]--，help数组为[1,2,3,4,5,7,7,8,9]，1 排在结果数组的第3个位置；
2. 扫描到值 5 时，help[5-0] = 7，help[5-0]--，help数组为[1,2,3,4,5,6,7,8,9]，5 排在结果数组的第7个位置；
3. 扫描到值 7 时，help[7-0] = 8，help[7-0]--，help数组为[1,2,3,4,5,6,7,7,9]，7 排在结果数组的第8个位置；
4. 扫描到值 3 时，help[3-0] = 4，help[3-0]--，help数组为[1,2,3,3,5,6,7,7,9]，3 排在结果数组的第4个位置；
5. 扫描到值 8 时，help[8-0] = 9，help[8-0]--，help数组为[1,2,3,3,5,6,7,7,8]，8 排在结果数组的第9个位置；
6. 扫描到值 0 时，help[0-0] = 1，help[0-0]--，help数组为[0,2,3,3,5,6,7,7,8]，0 排在结果数组的第1个位置；
7. 扫描到值 5 时，help[5-0] = 6，help[5-0] --，help数组为[0,2,3,3,5,5,7,7,8]，5 排在结果数组的第6个位置；
8. 扫描到值 1 时，help[1-0] = 2，help[1-0] --，help数组为[0,1,3,3,5,5,7,7,8]，1 排在结果数组的第2个位置；
9. 扫描到值 4 时，help[4-0] = 5，help[4-0] --，help数组为[0,1,3,3,4,5,7,7,8]，4 排在结果数组的第5个位置；

结果数组为[0,1,1,3,4,5,5,7,8]。

Java代码实现

public class CountSort{

    public static int[] countSort(int[]arr){
        int[] res = new int[arr.length]; //结果数组
        //求最大值和最小值
        int max = arr[0],min = arr[0];
        for(int value : arr){
            if(value > max){
                max = value;
            }
            if(value < min){
                min = value;
            }
        }
        int k= max - min + 1;
        int[] help=new int[k];
        for (int value : arr) {
            help[value - min] += 1;
        }
        //累加计数
        for(int i=1; i < help.length; ++i){
            help[i]=help[i] + help[i-1];
        }
        //反向遍历
        for(int i= arr.length-1; i >= 0; --i){
            res[--help[arr[i] - min]]= arr[i];
        }
        return res;
    }
}

小结

计数排序是一种空间换时间的算法，优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法，但当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序。要求排序元素的取值要在一定范围内，并且比较集中，其有限偏序集不能太大，才能发挥出计数排序的优势。

这篇关于【算法】计数排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！