目录
导入
之前我的博客介绍了七大排序：插入、希尔、选择、堆排、冒泡、快排、归并。
插入排序、希尔排序_SAKURAjinx的博客-CSDN博客
选择排序、堆排序、冒泡排序_SAKURAjinx的博客-CSDN博客
归并排序详解（递归+非递归）_SAKURAjinx的博客-CSDN博客
这些都是常见的比较类排序，所谓的比较类，就是按数的大小（如果是字符按ASCLL值）进行比较后排序。今天介绍的计数排序则是非比较排序，也就是说它不需要比较数的大小。
计数排序的思想
对于一个数组 {6,1,5,9,3,8,1,6,2,1} ，它的最大值是9，最小值是1，创建一个0~9 的数组，将原数组里的数按出现的次数放到对应的位置上。新的数组里各个位置上就是对应的数出现的次数。
然后按对应的数及它出现的次数将数组还原（出现0次的去掉），就排好了，这就是计数排序。
上图是计数排序的大致过程。
计数排序的思想优化
有人在其中发现了一些问题，比如如果数字太大的话，那开辟的数组就很大，这种方法就变得很不方便了。
确实，假设数组的值是这样的：1000,1500,2000,2500,1000,1000,2000 。这样数组最大值是2500，数组个数却只有7个，难道要开辟 0~2,500的数组吗？太过于浪费了。
于是，又有人想出了解决方法：既然嫌开辟的数组太大，又要包含最大最小数，那我们可以开辟一个相对于最大最小数的合理数组。如这里最小为1000，最大是2500，那么不用下标从0开始开辟，可以将1000转化为0,2500转化为1500，这样就节省了1000个int大小的空间。
这种方式叫相对映射，而一开始介绍的叫绝对映射。
这样调整一下创建新数组的下标，就可以较好的解决数过大的问题。
而且，相对映射还有一个优点：如果有负数的话，绝对映射就不行了，数组下标为负，越界了。
此时只能用相对映射。
计数排序代码实现
void CountSort(int* a, int n)
{
int max = a[0], min = a[0];
for (int i = 0; i < n; ++i)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min + 1;
/*int* tmp = (int*)malloc(sizeof(int) * range);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
memset(tmp, 0, sizeof(int) * range);*/
int* tmp = (int*)calloc(range,sizeof(int));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
for (int i = 0; i < n; ++i)
{
tmp[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; ++i)
{
while (tmp[i]--)
{
a[j++] = i + min;
}
}
free(tmp);
tmp = NULL;
}
int main()
{
int a[] = { 5,9,6,1,0,3,4,-8,-1,0,2 };
int n = sizeof(a) / sizeof(a[0]);
CountSort(a, n);
for (int i = 0; i < n; ++i)
{
printf("%d ", a[i]);
}
return 0;
}计数排序的时间复杂度是O(N+range），空间复杂度是O(range)。
不难发现，当N >= range 时，时间复杂度很小，计数排序很快；
当range远大于N（数比较分散），那么计数排序就比较慢了。
附送一张表
