非比较排序（计数排序）
目录
我们写后面的两个字符串相加的时候我们用到类似这个排序的原理，所以我们现在重新去复习一下这个排序。当然这里面有三组，一个是计数排序，一个是基数排序，一个是桶排序，后面两个都没什么作用，也就要记住计数排序就可以了
思想：
计数排序又被称为鸽巢原理，也是对哈希的直接地址发的变形应用
操作：
1.主要过程就是有两次循环，一次是我们去计数，一次我们去排序。我们利用下标的数字排序去记录每一个下标的数字都有几次，我们再去排序，但是我们去节约空间，我们就要去映射它的下标
如果我们这里面去开108个数组的话就会有空间的浪费，所以我们可以去映射108到100也就是创建0到8的空间数组，然后再去覆盖就可以了，当然我们也不可以去用auto。
首先映射的话我们不能0来初始化，不然的话如果是负数的话，数组是不可以用比0小的数
int rang = max - min + 1;
我们+1是应为我们少用了一个，问您在左闭右闭的相减是少一个，而我们要去加一个给补上
这里面memset去初始化计划然后再㺎calloc（个数，大小）是一样的，count是几下就虚幻几次，前置减减就是n就是n-1次
代码：
我们看一下代码
void countsort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 0;i< n;i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int rang = max - min + 1;
int* count = (int*)calloc(rang, sizeof(int));
if (count == nullptr)
{
perror("calloc fail");
return ;
}
//计数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;//记住cout就是数组，记录rang里面的
}
//排序
int j = 0;
for (int i = 0; i < rang; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
}原文地址：https://blog.csdn.net/gyj215500/article/details/143659003
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！