八大算法排序@计数排序（C语言版本）

计数排序

概念

??计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于排序一定范围内的整数数组。它利用了输入序列的数值范围来确定每个元素在输出序列中的位置。

算法思想

??主要思路是找出待排序数组的最大值和最小值，确认原数组的范围range，然后申请一有range个空间大小的数组并且数组内各个元素初始化为0，称之为计数数组。将原数组中的数映射到计数数组中，最终通过计数数组中的元素的数值，判断映射过来的数出现了多少次，以及原数组中的顺序情况。我们拿实现升序的计数排序来进行模拟演变。
如下，是初始状态图：

其中， arr1 = { 6 , 4 , 3 , 9 , 2 ,1 , 5 , 7 , 8 }是待排序的数组，变量maxi 和 mini 分别用来存放数组中最大的元素和最小的元素的下标。range是数组arr1的范围大小。

第一步：

找出原数组中的最大值和最小值的下标，通过下标算出原数组数据的范围range。再使用malloc函数，申请range个空间的计数数组retArr[range]；

第二步：

通过迭代循环，将原数组一个个的映射到计数数组中，如下：

需要注意的问题有：
1、偏移量的问题。映射关系要减去原数组的最小值，也是计数数组下标的问题。比如有个数组范围是10，但是最小值是100，最大值是109。比如数组中有个数105，要将它映射到计数数组中，直接将105映射到计数数组的话，那么计数数组就得开到有106个空间，这就造成了浪费。将105减去最小值100，这样映射到计数数组中的下标就是5，一样能够解决问题，这就避免了空间的浪费。

2、初始化问题。malloc动态申请的空间，没有初始化时数组内的各个元素都是随机值，而计数排序的关键就是对原数组中数据的大小、出现次数进行统计。所以对于申请开辟出来的计数数组中的初始值，我们要初始化好，一般都初始化为0，方便。也可以初始化为其他数，但是后面要消掉这个偏移量。

3、内存泄露问题。动态申请的空间，最后时得主动释放空间，要不然会造成内存泄露。

4、类型问题。计数排序只适用于整形数据的排序。字符类型要比较类型也不是不可以，但是要考虑ASCII码值的转换，比如字符 ‘1’ - 字符 ‘0’ 就等于整型数据1啦。但是像字符串、浮点型则不适用，因为字符串的比较大小的规则、浮点型的精确度问题，都不适用计数排序来排序。字符串和浮点型可以考虑使用其他的排序方法，如快速排序和归并排序等。

最后，我们得到了一个将原数组全部映射完到计数数组的，一个统计数组retArr。我们再通过计数数组retArr，复原出原数组，同时也就实现了对原数组的排序。

以上，便是对计数排序的大体图文介绍，下面用文字表述以上思路。

算法步骤

确定范围： 找出待排序数组中的最大值和最小值，确定数值范围。
计数： ????创建一个辅助数组（计数数组），长度为数值范围的大小，用于统计原始数组中每个元素出现的次数。
累加计数： 对计数数组进行累加操作，使得每个位置上的值表示小于或等于该位置值的元素个数。
输出： ????根据原始数组的值在计数数组中找到对应的位置，将元素放置到输出数组中。

接下来，就用代码来实现吧。

代码实现

// 时间复杂度：O(N+range)
// 空间复杂度：O(range)
// 只适用于整形，如果是浮点数或者字符串排序，还得用比较排序
void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	// 找出原数组中的最大值和最小值
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)		max = a[i];
		if (a[i] < min)		min = a[i];
	}
	// 算出原数组的范围
	int range = max - min + 1;
	// 申请开辟range个大小的空间
	int* retArr = (int*)malloc(sizeof(int) * range);
	memset(retArr, 0, sizeof(int) * range);	// 注意，要对该空间初始化为0，才能对数组a进行计数！！！！，否则数组自身随机值会导致计数的失败

	// 判断申请空间是否成功
	if (retArr == NULL)
	{
		printf("空间扩容失败\r\n");
		exit(-1);
	}

	// 将原数组映射到计数数组中，进行统计
	for (int i = 0; i < n; i++)
	{
		retArr[a[i] - min] += 1;
	}

	// 通过计数数组复原原数组的元素，同时完成排序的效果
	int index = 0;
	for (int j = 0; j < range; j++)
	{
		while (retArr[j]--)
		{
			a[index++] = j + min;
		}
	}
	
	free(retArr);
}

以上便是计数排序的代码实现，具体可以看着代码一点点意会，此处不做多加讲解。需要注意的便是下标的迭代问题了。

时间复杂度

O(N+range），其中N是数组元素个数，range是辅助计数数组的范围。
当N>>range时，时间复杂度为O(N)；
当range>>N时，时间复杂度为O(range)；
当N和range相近时，时间复杂度为O(N）或O(range)。

注：“ >> ” 是远大于的意思。
算计数排序时间复杂度的思想：
首先要遍历一遍原数组找出最大、最小值，需要N步；
其次需要将计数数组依次映射复原原数组，需要range步。至于比如说有的计数数组的元素值为3，那么该元素得迭代3次，对于常数次的动作，计算时间复杂度时不计入。

空间复杂度

O(range)

计数排序得向内存申请range个空间。所以空间复杂度为O(range）

注：“ range ” 是原数组的数值范围。

特性总结

1、只适合整形数据的排序，字符、字符串或浮点型等都不适用。
2、时间复杂度：O(N+range)
3、空间复杂度：O(range)
4、稳定性：稳定