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

一、计数排序概念

计数排序，又叫非比较排序。顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。

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

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

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

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

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

(1）假设要排序的数组A原始数据为{2，5，3，0，2，3，0，3}，遍历一遍找到最大值为max=5，min=0。 (2）定义一个辅助数组C。max-min+1=6，那么C的大小为6，C数组用memset初始化。 （3）C数组用作统计A数组中元素的个数，若A[k]-min==i，则C[i]++，0