目录
一.基本思想
二.缺陷及优化
三.代码实现
四.特性总结
1.可以排序负数
2.适合范围集中的整数
3.时间复杂度：O(N+range)
4.空间复杂度：O(range)
5.稳定性：稳定
一.基本思想
根据待排序数组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初始化都为0int 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.适合范围集中的整数
由于需要值来表示下标，因此只能排序整数。同时该排序对排序数组的极差有一定要求，即最大数减去最小数的值不能太大，否则开辟这么大的空间费时费力,此时就不适合计数排序了，计数排序适用于范围集中的整数排序。
