目录
1. 排序思想
2. 图解
3. 代码实现
3.1 逻辑
4. 特性总结
1. 排序思想
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：
1. 统计相同元素出现次数。
2. 根据统计的结果将序列回收到原来的序列中。
2. 图解
上面有一个数组，我们根据数组可以知道有 0 ~ 10 范围内的数字。我们开辟一个数组，其中有11个元素，每个元素的下标对应着数字，而数组中的数据代表着下标数字出现的次数。 我们统计完所有数字出现的次数之后，根据次数将数字填入到原数组中，就完成了排序。
这种数字对应下标的叫做绝对映射。那么如果是100 ~ 110范围的数字我们总不可能开110个空间吧，所以我们下面介绍一种相对映射的办法。
我们可以将100作为下标0,110作为下标10来标记数字，这样就只需要开11个空间就行了。
3. 代码实现
3.1 逻辑
a、求最大最小值：先遍历一遍数组找到最大值和最小值 max 和 min，这时候就能够确定相对的范围大小range = max min 1（之所以加1是因为是闭区间要多加一个元素）。 b、计数：然后开始重新遍历一遍计数，我们遍历一遍原数组，每次取到的数字就是新开辟的数组的下标，这里因为我们为了取到相对位置，需要将取到的数组减去 min 我们 即可。 c、排序（将统计好的数字放到数组）：我们遍历一遍排好的数组，次数大于1的数字（这里取到的数字需要重新加上min）按次数放到原数组中。
代码：
代码语言：javascript复制void CountSort(int* a, int n)
{
int max = a[0], min = a[0];
//找最大最小值
for (int i = 1; i < n; i)
{
if (a[i] > max)
{
max = a[i];
}
if(a[i] < min)
{
min = a[i];
}
}
//确定范围
int range = max - min 1;
int* countArr = (int*)calloc(range, sizeof(int));
//计数
for (int i = 0; i < n; i)
{
//相对映射
countArr[a[i] - min] ;
}
int j = 0;
for (int i = 0; i < range; i)
{
while (countArr[i]--)
{
a[j ] = i min;
}
}
free(countArr);
countArr = NULL;
}4. 特性总结
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。 2. 时间复杂度： O(MAX(N, 范围 )) 3. 空间复杂度： O( 范围 ) 4. 稳定性：稳定
