计数排序就是这么容易

太过爱你忘了你带给我的痛 2023-10-06 11:45 16阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzc0NjA0_size_16_color_FFFFFF_t_70]

#### 文章目录 ####

*  前言
 *  1.计数排序(Counting Sort)
 *   *  1.1.计数排序(Counting Sort)
 *  2.原理
 *   *  2.1.步骤
     *  2.2.实例题目
 *  3.代码
 *   *  3.1.代码
 *  4.扩展阅读
 *   *  4.1.局限性

## 前言 ##

> 声明：参考来源互联网，有任何争议可以留言。站在前人的肩上，我们才能看的更远。

> 本教程纯手打，致力于最实用教程，不需要什么奖励，只希望多多转发支持。  
> 欢迎来我公众号，希望可以结识你，也可以催更，微信搜索：JavaPub

> 有任何问题都可以来谈谈 ！

![20200616161009430.jpg][]

> **计数排序**是比较容易的排序算法，但是对数量级较小的整数排序很实用。

## 1.计数排序(Counting Sort) ##

### 1.1.计数排序(Counting Sort) ###

> 计数排序是一个**非基于比较**的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对**一定范围**内的**整数排序**时，它的复杂度为 `Ο(n+k)`（其中k是整数的范围），**快于任何比较排序算法**。当然这是一种牺牲空间换取时间的做法，而且当 `O(k)>O(n*log(n))` 的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n\*log(n)), 如 [归并排序][Link 1]，[堆排序][Link 2]）

*例如*：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

*  计数排序是一个简单的排序算法，看下边原理很容易理解。

## 2.原理 ##

### 2.1.步骤 ###

*  算法的步骤如下：

1.  找出待排序的数组中最大和最小的元素
2.  统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3.  对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4.  反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

![aHR0cHM6Ly9zdGF0aWMwMS5pbWdrci5jb20vdGVtcC82MTU1YzUyOGNkZTQ0ZjZkODVhOTZjZWI5NWVjYzJkYi5naWY][]

> 如果有疑问，看下边一个例子

### 2.2.实例题目 ###

> 题目：数组里有20个随机数，取值范围为从0到10，要求用最快的速度把这20个整数从小到大进行排序。

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

通过**计数排序**特性分析题目，我们知道整数的取值范围是从0到10，那么这些整数的值肯定是在0到10这11个数里面。于是我们可以建立一个长度为11的数组，数组下标从0到10，元素初始值全为0，如下所示：

![format_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：

![format_png 1][]

*  第二个整数是3，那么数组下标为 3 的元素加 1：

![format_png 2][]

*  继续遍历数列并修改数组…

最终，数列遍历完毕时，数组的状态如下：

![format_png 3][]

数组中的每一个值，代表了数列中对应整数的出现次数。

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

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

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

## 3.代码 ##

### 3.1.代码 ###

@Test
    public void sortJavaPub(){
        
    	int [] array = {
        2,1,5,3,4};
    	//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;
    		}
    	}
    	System.out.println(Arrays.toString(sortedArray));
    }

返回结果：

[1, 2, 3, 4, 5]

## 4.扩展阅读 ##

### 4.1.局限性 ###

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

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

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzc0NjA0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200620222046683.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzc0NjA0,size_16,color_FFFFFF,t_70
[20200616161009430.jpg]: https://img-blog.csdnimg.cn/20200616161009430.jpg
[Link 1]: https://mp.weixin.qq.com/s/VM9R4Y3uvFcmRuvmoWxLdw
[Link 2]: https://mp.weixin.qq.com/s/ajLmV6eVAFsV9El0aD_PjA
[aHR0cHM6Ly9zdGF0aWMwMS5pbWdrci5jb20vdGVtcC82MTU1YzUyOGNkZTQ0ZjZkODVhOTZjZWI5NWVjYzJkYi5naWY]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMS5pbWdrci5jb20vdGVtcC82MTU1YzUyOGNkZTQ0ZjZkODVhOTZjZWI5NWVjYzJkYi5naWY
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMS5pbWdrci5jb20vdGVtcC8yYzFlZjFiNDFiMDc0YmMxOTZiMzRhNTI4NmFmNmJmMi5qcGc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMS5pbWdrci5jb20vdGVtcC9kZGYxZmJhZTlmNzg0NjhmOTA2MDQ2MmJkZWEwZTkzZC5qcGc?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMS5pbWdrci5jb20vdGVtcC8xYjU1NTNkMGY1Zjc0NmMyOGNlMDJhNjk2MzVlYWMzMi5qcGc?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdGF0aWMwMS5pbWdrci5jb20vdGVtcC8zZTk4OTUxYTIzYjI0NDA2OTA1ZTNiMGFhZjFkMmU1Yi5qcGc?x-oss-process=image/format,png