目录
个人格言：悟已往之不谏，知来者犹可追
克心守己，律己则安！
1. 计数排序的思想动图
2. 从思想到代码的实现
>1.创建临时数组
我们先创建一个临时的数组tmp并且该数组的最大下标为原数组中元素的最大值（里面的元素初始化为0）
//先遍历原数组找到最大值
int max = a[0];
for (int i = 1; i < n; i++)
{
if (max < a[i])
{
max = a[i];
}
}
//动态内存开辟max+1个int空间并初始化为0用calloc
int* tmp = (int)calloc(max+1, sizeof(int));
if (tmp == NULL)
{
perror("calloc fail!\n");
return;
}>2.统计次数
然后遍历一遍原数组，原数组中出现哪个元素就在tmp数组中与该元素数值相同的下标对应的地方进行加加操作来记录该元素出现的次数。
//统计次数
for (int i = 0; i < n; i++)
{
tmp[a[i]]++;
}>3.排序
最后我们再进行排序，记住tmp的下标对应原数组可能出现的元素，而里面的值对应该元素出现的次数，如果为0就说明该元素在原数组不存在。遍历tmp数组，将对应的下标覆盖原数组即可完成排序。
//排序
int j = 0;
for (int i = 0; i < max + 1; i++)//第一层循环遍历tmp数组
{
while (tmp[i]--)//对应元素出现的次数
{
a[j++] = i;//tmp的下标对应的就是原数组可能出现的元素
}
}
//释放资源，避免内存泄漏
free(tmp);
tmp = NULL;>4.简单版本
好现在简单的计数排序就已经完成了
完整代码：
void CountSort(int* a,int n)
{
//先遍历原数组找到最大值
int max = a[0];
for (int i = 1; i < n; i++)
{
if (max < a[i])
{
max = a[i];
}
}
//动态内存开辟max+1个int空间并初始化为0用calloc
int* tmp = (int*)calloc(max+1, sizeof(int));
if (tmp == NULL)
{
perror("calloc fail!\n");
return;
}
//统计次数
for (int i = 0; i < n; i++)
{
tmp[a[i]]++;
}
//排序
int j = 0;
for (int i = 0; i < max + 1; i++)//第一层循环遍历tmp数组
{
while (tmp[i]--)//对应元素出现的次数
{
a[j++] = i;//tmp的下标对应的就是原数组可能出现的元素
}
}
//释放资源，避免内存泄漏
free(tmp);
tmp = NULL;
}
3. 是否可以优化呢~
思考一下，如果我们的数据是这样的呢，如果还像之前那样开辟空间，是否会有大量的空间浪费呢？遍历的次数增大，是否有性能的降低呢~
所以，我们就可以这样取tmp的范围：
优化后代码：
//先遍历原数组找到最大值
int max = a[0];
int min = a[0];
for (int i = 1; i < n; i++)
{
if (max < a[i])
{
max = a[i];
}
if (min > a[i])
{
min= a[i];
}
}
int range = max - min + 1;
//动态内存开辟max+1个int空间并初始化为0用calloc
int* tmp = (int*)calloc(range, sizeof(int));
if (tmp == NULL)
{
perror("calloc fail!\n");
return;
}关于下标与元素对应的问题，我们就可以采用相对映射的方法来解决（优化后代码）
优化后的完整代码：
void CountSort(int* a,int n)
{
//先遍历原数组找到最大值
int max = a[0];
int min = a[0];
for (int i = 1; i < n; i++)
{
if (max < a[i])
{
max = a[i];
}
if (min > a[i])
{
min= a[i];
}
}
int range = max - min + 1;
//动态内存开辟max+1个int空间并初始化为0用calloc
int* tmp = (int*)calloc(range, sizeof(int));
if (tmp == NULL)
{
perror("calloc fail!\n");
return;
}
//统计次数
for (int i = 0; i < n; i++)
{
tmp[a[i]-min]++;
}
//排序
int j = 0;
for (int i = 0; i < range; i++)//第一层循环遍历tmp数组
{
while (tmp[i]--)//对应元素出现的次数
{
a[j++] = i+min;//tmp的下标对应的就是原数组可能出现的元素
}
}
//释放资源，避免内存泄漏
free(tmp);
tmp = NULL;
}
4. 计数排序的时空复杂度
>空间复杂度：除原数组外，计数排序额外开辟了一个大小为N的临时空间，所以计数排序的空间复杂度为O(N)。
>时间复杂度：遍历找最大最小值取范围的时间复杂度为O(N)，遍历原数组统计次数的时间复杂度为O(N)，而排序里面，虽有两层循环，但从思想和本质来看，它只不过是将原来的元素按顺序覆盖了原数组，其执行循环的次数任然为O(N)，所以计数排序的时间复杂度为O(N).
5.总结
计数排序（Counting Sort）是一种非比较排序算法，它的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序的优点
- 稳定性：计数排序是一种稳定的排序算法，即相等的元素在排序过程中不会改变相对位置。
- 时间复杂度低：在数据范围不是很大的情况下，计数排序的时间复杂度可以达到O(n)，是非常高效的排序算法。
- 空间换时间：计数排序通过使用额外的空间来换取排序时间的大幅度降低，适合数据范围不大的情况。
计数排序的局限性
- 数据范围限制：当数据的范围非常大时，计数排序需要创建一个长度为最大值加一的数组，这将导致大量的空间浪费，因此它不适合数据范围很大的排序。
- 数据类型限制：计数排序只适用于整数排序，对于其他类型的数据（如字符串、浮点数等）则不适用。
- 空间复杂度较高：计数排序需要额外的存储空间来存储临时数组，当数据范围较大时，其空间复杂度会显著增加。
综上所述，计数排序在特定条件下（数据范围不大且为整数）是非常高效的排序算法，但在数据范围大或数据类型不匹配时则不适用。在实际应用中，需要根据具体的数据特征选择合适的排序算法。
6、完结散花
好了，这期的分享到这里就结束了~
如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~
我们下期不见不散~~
