[数据结构与算法]计数排序的简单总结

计数排序不发生比较，较为节约时间，但较为耗费空间，其平均时间复杂度：o(n+k)(平方)、空间复杂度：o(k)；

计数排序是稳定排序、外部排序；

局限性在于需要原数组集中在一定范围内，否则该算法极占空间；

动图如下：

算法要注意的是优化后的代码如何写。

3个步骤如下：

//第0步 找最大值和最小值

1.算法需要新建一个数组cnt[d],其中d为数组中的“最大值减最小值+1”，在c语言中由于数组下标不能为变量，所以要用到calloc函数为cnt申请空间（代码见后）。

2.用cnt[]数组计数;

3.用双重嵌套循环对原数组赋值。

优化方案：

找到原数组的最大和最小值（有时算法题目中会直接要求你输入有多少个数组cnt的下标）；

代码细节：

对每个cnt下标计数时（即cnt[xx]++时)，需要xx为"原数组元素-min",就是要减去偏移量；

在第三步的赋值时要在i上加上一个偏移量；

对于洛谷P1271运用计数排序的代码如下：

#include<stdio.h>
#include<stdlib.h>
int a[2000001];
int findmax(int* arr,int len)
{
	int i, max = arr[0];
	for (i = 1; i < len; i++)
		if (arr[i] > max)
			max = arr[i];
	return max;
}
int findmin(int* arr, int len)
{
	int i, min = arr[0];
	for (i = 1; i < len; i++)
		if (arr[i] < min)
			min = arr[i];
	return min;
}
void countsort(int* arr,int len,int n)
{
	//int max=findmax(arr,len);
	int min=findmin(arr,len);
	
	int d =n;
	int* cnt,i,j,k=0;
	cnt = (int*)calloc(d, sizeof(int));
	for(i=0;i<len;i++)
		
	cnt[arr[i]-min]++;
	for (i = 0; i < d; i++)//第一个循环，遍历下标
		for (j = 0; j < cnt[i]; j++)//第二个循环，看有几个该下标数字的元素

			arr[k++] = i + min;
}
int main()
{
	
	int i,n,m;
	scanf_s("%d %d", &n, &m);
	for(i=0;i<m;i++)
		scanf_s("%d", &a[i]);
	countsort(a,m,n);
	for (i = 0; i < m; i++)
		printf("%d ", a[i]);
	return 0;
}