[数据结构与算法]【数据结构】计数排序

计数排序

前面专栏里讲的都是比较排序，计数排序是一种非比较排序。

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

对于 1000 、10001 、1002 类似的数据，从0开始会有大量的空间浪费，所以有优化的思路。

遍历数组，找出最大和最小的值，这个值就是需要开辟的空间大小，然后将数映射到计数的数组中，取数的时候需要把数字加上最小值。

C语言实现程序

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}

	// 开辟 max-min+1 大小的数组
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);
	if (count == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	// 计数
	for (int i = 0; i < n; ++i)
	{
		count[a[i] - min]++;
	}

	// 把数据拷贝回到a
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

特性分析

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,range))
3. 空间复杂度：O(range)
4. 稳定性：不稳定