目录
一.基本思想
根据待排序数组a创建一个新的数组count，该数组的下标应包含数组a的所有值，统计a数组中每个数据出现的次数，记录到count，再将count转换覆盖到a，完成计数排序。
例如下图所示，在数组a中1出现了两次，那么对应在count数组中下标为1的值就为2，数组a中没有值为3的值，那么count数组中下标为3的值就为0，最后的转换就是根据次数依次将下标排列而出，得到最终结果。
二.缺陷及优化
count数组的开辟依据待排序数组的值的大小，上图中下标0-9就代表了取值的整个区间，正好能够满足绝对映射，即下标正好对应值。但有时候会存在问题，例如在数组【100,101,105,102,107,109,104】来排序，需要创建一个下标由0到109的数组吗？答案肯定是否定的，这样浪费的空间太多（0-99的空间都是浪费的），效率也低，使用相对映射，就可满足需求，将下标为0对应100，下标为9对应109即可，实现可以如下图：
三.代码实现
//计数排序
void CountSort(int* a, int n)
{
//找最大值和最小值确定区间
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
//确定范围,calloc初始化都为0
int range = max - min + 1;
int* count = (int*)calloc(range, sizeof(int));
//统计次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
}四.特性总结
1.可以排序负数
存在负数的情况，max-min+1仍然得到的是正的范围。如9-(-5)+1 = 15，此时仍然保持相对映射，min = -5时，-5对应的下标为-5-（-5）= 0，即min对应的始终是下标为0的位置，其余相对同理，因此计数排序是可以排负数的。
2.适合范围集中的整数
由于需要值来表示下标，因此只能排序整数。同时该排序对排序数组的极差有一定要求，即最大数减去最小数的值不能太大，否则开辟这么大的空间费时费力,此时就不适合计数排序了，计数排序适用于范围集中的整数排序。
