什么是计数排序

Bertha 。 2023-02-19 13:28 15阅读 0赞

有这样一道排序题：数组中有20个随机数，取值范围为0待10，要求用最快的速度将这20个整数从小到大进行排序。

第一时间你可能会使用快速排序，因为快速排序的时间复杂度只有O(nlogn)。但是这种方法还是不够快，有没有比O(nlogn)更快的排序方法呢？你可能会有疑问：O(nlogn)已经是最快的排序算法了，怎么可能还有更快的排序方法？

让我们来回顾一下经典的排序算法，无论是归并排序，冒泡排序还是快速排序等等，都是基于元素之间的比较来进行排序的。但是有一种特殊的排序算法叫做**计数排序**，这种排序算法不是基于元素比较，而是利用数组下标来确定元素的正确位置。

在刚才的题目里，随即整数的取值范围是从0到10，那么这些整数的值肯定是在0到10这11个数里面。于是我们可以建立一个长度为11的数组，数组下标从0到10，元素初始值全为0，如下所示：

![在这里插入图片描述][20200622084539735.png]  
先假设20个随机整数的值是：9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9

让我们先遍历这个无序的随机数组，每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。

比如第一个整数是9，那么数组下标为9的元素加1：  
![在这里插入图片描述][20200622084548610.png]  
第二个整数是3，那么数组下标为3的元素加1：  
![在这里插入图片描述][20200622084608639.png]  
继续遍历数列并修改数组…

最终，数列遍历完毕时，数组的状态如下：  
![在这里插入图片描述][20200622084627104.png]  
数组中的每一个值，代表了数列中对应整数的出现次数。

有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10

显然，这个输出的数列已经是有序的了。

这就是计数排序的基本过程，**它适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能在某些情况甚至快过那些O(nlogn)的排序，例如快速排序、归并排序。**

public static int[] countSort(int[] array) {
        
        //1.得到数列的最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
        
            if (array[i] > max)
                max = array[i];
        }
        //2.根据数列的最大值确定统计数组的长度
        int[] coutArray = new int[max + 1];
        //3.遍历数列，填充统计数组
        for(int i = 0; i < array.length; i++)
            coutArray[array[i]]++;
    
        //4.遍历统计数组，输出结果
        int index = 0;
        int[] sortedArray = new int[array.length];
        for (int i = 0; i < coutArray.length; i++) {
        
            for (int j = 0; j < coutArray[i]; j++) {
        
                sortedArray[index++] = i;
            }
        }
    
        return sortedArray;
    }

这段代码在一开始补充了一个步骤，就是求得数列的最大整数值max，后面创建的数组countArray,长度就是max+1，以此保证数组最后一个下标是max。

从功能角度来看，这段代码可以实现整数的排序。但是这段代码其实并不严谨。

比如这个数列：95, 94, 91, 98, 99, 90, 99, 93, 91, 92。该数列最大值是99，但最小值是90，如果我们只以数列的最大值来决定统计数组的长度的话，就要创建长度为100的数组，那么就会浪费前面90个空间。

为了解决这个问题，我们不再以（输入数列的最大值+1）作为统计数组的长度，而是以（数列最大值和最小值的差+1）作为统计数组的长度。同时，数列的最小值作为一个偏移量，用于统计数组的对号入座。

以刚才的数列为例，统计数组的长度为 99-90+1=10，偏移量等于数列最小值90。

对于第一个整数95，对应的统计数组下标为95-90=5，如图所示：  
![在这里插入图片描述][20200622084756851.png]

public static int[] countSort(int[] arr){
        
            //1.得到数列的最值
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < arr.length; i++){
        
                if (arr[i] > max){
        
                    max = arr[i];
                }
    
                if (arr[i] < min){
        
                    min = arr[i];
                }
            }
    
            //2.根据数列的最值确定统计数组的长度
            int []countArray = new int[max - min + 1];
            //3.遍历数列，填充统计数组
            for (int i = 0; i < arr.length; i++){
        
                countArray[arr[i] - min]++;
            }
    
    
            //4.遍历统计数组，输出结果
            int index = 0;
            int[] sortArray = new int[arr.length];
            for (int i = 0; i < countArray.length; i++){
        
                while (countArray[i] > 0){
        
                    sortArray[index++] = i + min;
                    countArray[i]--;
                }
            }
    
            return sortArray;
        }
    
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
    
            int[] brr = countSort(arr);
    
            System.out.println(Arrays.toString(arr));
            System.out.println(Arrays.toString(brr));
        }

进阶一：

步骤：  
第一步：求出原始数组的最大值和最小值  
![在这里插入图片描述][20200622101607729.png]  
第二步：创建一个max - min + 1 长度的中间数组count  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]  
第三步：遍历原始数组，并且将其映射到中间数组：以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 7]  
第四步：对count数组变形，新元素的值是前面元素累加之和的值，即count\[i+1\] = count\[i+1\] + count\[i\];  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 8]  
第五步：创建一个和原始数组长度一样的结果数组  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 9]  
第六步：从头开始遍历原始数组，并通过中间数组填充结果数组：当前元素A\[j\]减去最小值min，作为索引，在计数数组中找到对应的元素值count\[A\[j\]-min\]，再将count\[A\[j\]-min\]的值减去1，就是A\[j\]在结果数组result中的位置，做完上述这些操作，count\[A\[j\]-min\]自减1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 12]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 14]

public int[] countSort3(int[] A) {
        
        // 找出数组A中的最大值、最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : A) {
        
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        // 初始化计数数组count
        // 长度为最大值减最小值加1
        int[] count = new int[max-min+1];
        // 对计数数组各元素赋值
        for (int num : A) {
        
            // A中的元素要减去最小值，再作为新索引
            count[num-min]++;
        }
        // 计数数组变形，新元素的值是前面元素累加之和的值
        for (int i=1; i<count.length; i++) {
        
            count[i] += count[i-1];
        }
        // 创建结果数组
        int[] result = new int[A.length];
        // 遍历A中的元素，填充到结果数组中去
        for (int j=0; j<A.length; j++) {
        
            result[count[A[j]-min]-1] = A[j];
            count[A[j]-min]--;
        }
        return result;
    }

如果我们想要原始数组中的相同元素按照本来的顺序的排列，那该怎么处理呢？

依旧以上一个数组\{101,109,107,103,108,102,103,110,107,103\}为例，其中有两个107，我们要实现第二个107在排序后依旧排在第一个107的后面，可以在第六步的时候，做下变动就可以实现，用倒序的方式遍历原始数组，即从后往前遍历A数组。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 15]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 16]

public int[] countSort4(int[] A) {
        
        // 找出数组A中的最大值、最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : A) {
        
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        // 初始化计数数组count
        // 长度为最大值减最小值加1
        int[] count = new int[max-min+1];
        // 对计数数组各元素赋值
        for (int num : A) {
        
            // A中的元素要减去最小值，再作为新索引
            count[num-min]++;
        }
        // 计数数组变形，新元素的值是前面元素累加之和的值
        for (int i=1; i<count.length; i++) {
        
            count[i] += count[i-1];
        }
        // 创建结果数组
        int[] result = new int[A.length];
        // 遍历A中的元素，填充到结果数组中去，从后往前遍历
        for (int j=A.length-1; j>=0; j--) {
        
            result[count[A[j]-min]-1] = A[j];
            count[A[j]-min]--;
        }
        return result;
    }

既然从后往前遍历原始数组的元素可以保证其原始排序，那么从前往后可不可以达到相同的效果？

答案时可以的。[待研究][Link 1]

虽然计数排序看上去很强大，但是它存在两大局限性：

1.当数列最大最小值差距过大时，并不适用于计数排序

比如给定20个随机整数，范围在0到1亿之间，此时如果使用计数排序的话，就需要创建长度为1亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。

2.当数列元素不是整数时，并不适用于计数排序

如果数列中的元素都是小数，比如3.1415，或是0.00000001这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。

正是由于这两大局限性，才使得计数排序不像快速排序、归并排序那样被人们广泛适用。

[https://www.cnblogs.com/xiaochuan94/p/11198610.html][Link 1]  
[动画][Link 2]

[20200622084539735.png]: https://img-blog.csdnimg.cn/20200622084539735.png
[20200622084548610.png]: https://img-blog.csdnimg.cn/20200622084548610.png
[20200622084608639.png]: https://img-blog.csdnimg.cn/20200622084608639.png
[20200622084627104.png]: https://img-blog.csdnimg.cn/20200622084627104.png
[20200622084756851.png]: https://img-blog.csdnimg.cn/20200622084756851.png
[20200622101607729.png]: https://img-blog.csdnimg.cn/20200622101607729.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200622101942259.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200622102227325.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200622102315660.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200622102351605.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200622102428318.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020062210245379.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200622102527350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200622102559332.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200622102935992.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200622103037236.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200622104930768.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200622105228648.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200622105402648.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200622105546352.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200622105716227.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200622111450838.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/20200622111522984.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[Link 1]: https://www.cnblogs.com/xiaochuan94/p/11198610.html
[Link 2]: https://www.bilibili.com/video/av79587511/