排序算法 — 计数排序

计数排序

计数排序，是通过统计每一个数字出现的次数，并把它映射到与它自己本身数值相同的下标处，再遍历映射的数组使原数组有序的一种排序方法，计数排序的本质是一种哈希算法，也就是通过建立映射关系来达到排序的目的。

基本思路

先开辟一个映射数组，然后遍历原数组，数组中的元素是几就在开辟的的映射数组下标为几的位置+1。得到的这个映射数组就包含了原数组中所有元素的映射关系。遍历一遍映射数组找出原数组中出现过的数即可。

演示图

示例代码

void CountSort(int* a, int n)
{
	assert(a);
	int i = 0;
	int max = a[0];
	int min = a[0];
	//找出最大最小值，算出需要开辟多大的空间
	for (i = 1; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	//需要开辟的空间的大小range
	int range = max - min + 1;
	int* CountArr = (int*)malloc(sizeof(int) * range);
	if (CountArr == NULL)
	{
		perror(" ");
		return;
	}
	//一定要先初始化为0，不然的话是随机数就会影响统计的结果
	memset(CountArr, 0, sizeof(int) * range);
	//遍历数组，给映射数组对应的位置统计数组出现的次数
	for (i = 0; i < n; i++)
	{
		//减去min是它的相对映射的位置
		CountArr[a[i] - min]++;
	}

	//遍历映射数组
	int j = 0;
	for (i = 0; i < range; i++)
	{
		//对应的位置是几就把这个数字往原数组中填几次
		while (CountArr[i]--)
		{
			//由于上面在映射的时候减去了min，所以在重新
			//写回数组的时候需要加上min得到原来的值
			a[j++] = i + min;
		}
	}

	free(CountArr);
	CountArr = NULL;
}

时间复杂度和空间复杂度

时间复杂度是O(N)就能解决问题的，因为只遍历了两次数组。空间复杂度是O(range)，如果N（元素个数）远远大于range，那么可以认为是O(1)的，如果N和range是同一数量级的，那么是O(N)，如果range远远大于N，那么是O(range)。 在适当的场景下，计数排序的时间复杂度比其它的所有排序的时间复杂度都要低，可以认为是O(N)的，但是由于有很大的局限性，所以在很多地方都不适用。计数排序也就得不到推广。