排序算法9----计数排序（C）

? ? ? ? 计数排序是一种非比较排序，不比较大小?。

? ? ? ? 1、思想

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

? ? ? ? 2、步骤? ? ? ?

? ? ? ? 1、统计数据：统计每个数据出现了多少次。（建立一个count数组，范围从[MIN,MAX],MAX代表arr中最大的一个数，MIN对应arr中最小的一个数，然后for循环遍历arr，出现一个数，就在count中对应位置++）。这叫count和arr相对映射。（相对最小值和最大值来开count的范围）

? ? ? ? 2、用count覆盖arr：?因为count的下标代表arr中的数据值，count的内容代表出现的次数。

? ? ? ? 3、效率极高

? ? ? ? 特点时间复杂度：O(aN+countN（范围）)，即O( MAX {N,范围} )

? ? ? ? ? ? ? ?空间复杂度：?O（范围）

? ? ? ? 局限性：1、不适合分散的数据，更适合比较集中连续的数据。

? ? ? ? ? ? ? ? ? ? ? ?2、不适合浮点数、字符串、结构体数据排序。，只适合整数（包括负数），因为count和arr是相对映射。

? ? ? ? 4、代码

void CountingSort_incline(int*arr,int n)
{
	//找范围
	int min = arr[0], max = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] < min)
			min = arr[i];
		if (arr[i] > max)
			max = arr[i];
	}
	int range = max - min + 1;
	
	//开count数组
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail\n");
		exit(-1);
	}
	
	//统计次数
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;//相对位置++，不是绝对位置
	}

	//count“覆盖”回去arr
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)//即看下标（相对数）出现了几次，就覆盖回去几次
		{
			arr[i++] = j+min;//j+min代表还原，即从相对位置得到原来的绝对值
		}
	}

/*	例如：{-1，1，3，2，1，5，1，6}；min = -1，max = 6；
		count[8]；则每个数的相对值为arr[i] - min = arr[i] + 1;得到相对{0，2，4，3，2，6，2，7}
所以：count（下标出现次数）：1  0  3  1  1  0  1  1
	               相对下标：0  1  2  3  4  5  6  7
		下标还得到原数组元素的绝对值（下标 + min）：{ -1，0，1，2，3，4，5，6 }，分别对应次数{1，0，3，1，1，0，1，1}；
	则覆盖回去arr数组：{-1，1，1，1，2，3，5，6}；*/
}

? ? ? ? 5、实现效果

	int arr[] = { 1,3,10,2,1,3,1,5,11,-2 };
	int size = sizeof(arr) / sizeof(int);
	printf("原数组\n");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	printf("排序后\n");
	CountingSort_incline(arr,size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

原数组：1，3，10，2，1，3，1，5，11，-2

排序后：-2，1，1，1，2，3，3，5，10，11