计数排序及其时间复杂度、代码(C++实现)、应用场景

一时失言乱红尘 2022-09-12 03:56 167阅读 0赞

### 文章目录 ###

*  一、计数排序概念
 *  二、计数排序代码
 *  三、计数排序代码
 *  四、计数排序应用场景

# 一、计数排序概念 #

计数排序，又叫非比较排序。顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_15_color_FFFFFF_t_70_g_se_x_16]

**上列中的映射方法称为绝对映射，即arr数组中的元素是几就在count数组中下标为几的位置++，但这样会造成空间浪费。例如，我们要将数组：102,101,108，进行排序，难道我们要开辟109个整型空间吗？**

**若是使用计数排序，我们应该使用相对映射，简单来说，数组中的最小值就相对于count数组中的0下标，数组中的最大值就相对于count数组中的最后一个下标。这样，对于数组：102,101,108，我们就只需要开辟用于储存4个整型的空间大小了，此时count数组中下标为i的位置记录的实际上是101+i这个数出现的次数。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_8_color_FFFFFF_t_70_g_se_x_16]

**总结：**  
 **绝对映射：count数组中下标为i的位置记录的是arr数组中数字i出现的次数。  
 相对映射：count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。**  
   
**------------------------------------------------------------------------------------------------------------------------------**

计数排序是一种非基于比较的**非稳定线性排序算法。**

基本思想是：用空间换时间，本质上是建立了基于元素的Hash表。

(1）假设要排序的数组A原始数据为\{2，5，3，0，2，3，0，3\}，遍历一遍找到最大值为max=5，min=0。  
![在这里插入图片描述][558bf040020e4966bfd6847e72f32760.png]  
(2）定义一个辅助数组C。max-min+1=6，那么C的大小为6，C数组用memset初始化。  
![在这里插入图片描述][d331acd7402a43d395947c28907d6be0.png]  
（3）C数组用作统计A数组中元素的个数，若A\[k\]-min==i，则C\[i\]++，0<=k<7，例如A中的0有2个，那么C\[0-min\]=2，min=0。  
![在这里插入图片描述][bff245805e464adebc544f832eb75c61.png]

# 二、计数排序代码 #

//计数排序的实现
    void CountSort(int* arr, int sz)
    { 
    	//1.首先找出最大值与最小值
    	int min = arr[0];
    	int max = arr[0];
    
    	for (int i = 0; i < sz; i++)
    	{ 
    		if (arr[i]>max)
    		{ 
    			max = arr[i];
    		}
    		if (arr[i] < min)
    		{ 
    			min = arr[i];
    		}
    	}
    
    	//计算出最大值和最小值之间的元素个数
    	int range = max - min + 1;
    
    	int* count = new int[range];
    	memset(count, 0, sizeof(count));
    
    	for (int i = 0; i < sz; i++) //统计相同元素出现次数（相对映射）
    	{ 
    		count[arr[i] - min]++;
    	}
    
    	int i = 0;
    	for (int j = 0; j < range; j++)
    	{ 
    		while (count[j]--)
    		{ 
    			arr[i] = j + min;
    		}
    	}
    	delete[range] count;
    }

# 三、计数排序代码 #

时间复杂度：O ( N + r a n g e ) 空间复杂度：O ( r a n g e ) 。

# 四、计数排序应用场景 #

计数排序只适用于数据范围较集中的序列的排序，若待排序列的数据较分散，则会造成空间浪费，并且计数排序只适用于整型排序，不适用与浮点型排序。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ee73b41b8d3f45ccb00a36e0e5c0f6bd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/05719c2ed3d34b079a02472762e789b9.png
[558bf040020e4966bfd6847e72f32760.png]: /images/20220828/1b3d4cdb41e94115a30765130ba0a593.png
[d331acd7402a43d395947c28907d6be0.png]: /images/20220828/ea03194d4bc743eb924be2ae183e82b1.png
[bff245805e464adebc544f832eb75c61.png]: /images/20220828/e47efbe004f84a67a99dbb51a060170d.png