目录
1. 排序思想
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：
-
统计相同元素出现次数。
-
根据统计的结果将序列回收到原来的序列中。
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）按次数放到原数组中。
代码：
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. 特性总结
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度： O(MAX(N, 范围 ))
- 空间复杂度： O( 范围 )
- 稳定性：稳定
Original: https://blog.csdn.net/qq_65139309/article/details/127820737
Author: 青衫哥
Title: 排序8: 计数排序
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/659276/
转载文章受原作者版权保护。转载请注明原作者出处！