Java教程

【算法】计数排序

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

对数组 [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))的时候其效率反而不如基于比较的排序。要求排序元素的取值要在一定范围内,并且比较集中,其有限偏序集不能太大,才能发挥出计数排序的优势。

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