计数排序CountingSort

我就是我 2022-05-22 04:11 177阅读 0赞

> 转载请标明出处：  
> 原文首发于： [http://www.zhangruibin.com][http_www.zhangruibin.com]  
> 本文出自 [RebornChang的博客][http_www.zhangruibin.com]

# **厚颜打广告，博主个人博客地址[传送门][Link 1] ，欢迎来访** #

计数排序是什么?  
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 \[1-2\] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）(摘自百度百科)  
看了上面百科解释,可以大概对计数排序有一个简单的了解,那么,现在再来一张计数排序的原理图:  
![这里写图片描述][70]  
如图所示,右边横向数组为\[8,2,3,4,3,6,6,3,9\],其中最小值为2,最大值为9.  
那么接下来走一下计数排序的流程:  
第一步:因为数组中最小值为2,最大值为9,所以拿来十个桶,并且依次编号一到九.  
第二步:从右边数组里面依次取数字,放到与数字对应的桶中.(比如8放到编号为8的桶,有三个3就把这三个三放到编号为3的桶中).  
第三步:图中左边一排桶中,有的放了一个数字,有的放了三个数字,有的没有放数字,并且最重要一点–同中所放的数字值和同的序号相同,那么顺序遍历取出桶的序号,就是排序后的数组.  
上面就是最简单的桶排序步骤,下面来一点延伸:

1.对于上面的排序,拿来的十个桶,为什么要拿十个桶?  
2.可不可以少拿点不浪费资源(开辟的内存资源)?  
3.怎样确定最大的桶代表的数字,而不会出现数字没有对应的桶装?  
由这点疑问我们可以对桶排序进行一点灵活的运用.  
1.先找到待排序数组的最小值与最大值,最大值减去最小值,就是所需的桶的最多个数.  
2.找到的最小值与最大值,可以保证桶能代表所有的数字.  
3.把桶中的数字依序存入到新数组就能保证新数组的有序性.  
那么接下来就是代码部分了:  
注:因为博主代码是根据输入的数字动态生成随机数组,所以,生成数组中数字大小不一定,这样可以保证数字排序的真实性.  
主要代码为:  
1.找待排序数组的最小值和最大值:

//创建一个随机的数组
            int [] tempArray = new CreatAIntArray().creatArrayLength();
     //开始声明桶,找到数组的最小值和最大值
            int minNum = tempArray[0];
            int maxNum = tempArray[0];
            for (int i = 0;i < tempArray.length;i++){
                if (tempArray[i] < minNum){
                    minNum = tempArray[i];
                }
                if (tempArray[i] > maxNum){
                    maxNum = tempArray[i];
                }
            }
            System.out.println("最小数字为:"+minNum);
            System.out.println("最大数字位:"+maxNum);

2.声明一个桶数组用来存储对应的待排序数组数字:

//找到最大最小值的之后,就开始声明有序桶,桶的初始位代表的值为minNum最大值为maxNum
            //数组的长度为(maxNum-minNum+1)
            int[] bucketArray = new int[(maxNum-minNum+1)];
            //声明了有序桶之后,开始对数字进行放桶操作
            for (int j = 0;j < tempArray.length;j++){
                //因为是找到了待排序数组的最小值minNum,所以,与数组数组比较的值应为(j+minNum)
                //如果遍历的值大小与数组代表的数字大小相等,则放入
                //j次循环得到的数字是tempArray[j],则存储到下标为tempArray[j]+minNum的桶中
                bucketArray[tempArray[j]-minNum] = bucketArray[tempArray[j]-minNum]+1;
            }

3:声明新数组,对桶中的数组进行存储和打印输出:

//可以声明新数组对该序列进行存储
            int[] finalArray = new int[tempArray.length];
            int count = 0;
            for (int k = 0;k < bucketArray.length;k++){
                if (bucketArray[k] != 0){
                    //桶里装的值可能不是1,所以,在不等于一的时候,对桶里面的数字进行遍历存储
                    if (bucketArray[k]!= 1){
                        for (int z = 0;z < bucketArray[k];z++){
                            finalArray[count] = k+minNum;
                            count++;
                        }
                    }else {
                        finalArray[count] = k+minNum;
                        count++;
                    }
                }
            }
            System.out.println("排序后的数组为:"+Arrays.toString(finalArray));

以上是博主的创建数组,排序数组,输出数组的代码,其核心计数排序代码非常简单:

for (int j = 0;j < tempArray.length;j++){
                bucketArray[tempArray[j]-minNum] = bucketArray[tempArray[j]-minNum]+1;
            }

本节代码运行效果如下:  
![这里写图片描述][70 1]  
代码已经上传到GitHub上,地址如下:  
[https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/CountingSort.java][https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_CountingSort.java]  
Over!

[http_www.zhangruibin.com]: http://www.zhangruibin.com
[Link 1]: http://zhangruibin.com
[70]: /images/20220522/5c0c31d737134e0ead924a5a6c8e3e13.png
[70 1]: /images/20220522/3d65d4050e1a4a8fb180fc5cb927db80.png
[https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_CountingSort.java]: https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/CountingSort.java