因为ss最近在备赛,很久没写文章了,今天速更一篇
非比较排序中的计数排序
这个排序适用于数组范围比较集中的,因为我们把数组里面的数作为新数组的下标,这样我们就可以记录这个数出现的次数,大家看代码把,应该会比较清楚
void CountSort1(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
{
tmp[arr[i]]++;
}
}
大家可以看到我们以每个的数字作为下标,然后把tmp数组中下标是arr里面数字的位置进行增加,只要遍历tmp数组然后把不为零的地方进行操作,它的下标就是这个之前数组的数,这个下标的数就是代表这个数有几次,然后遍历这个新数组,从下标零开始,那样的话不就把顺序也排好了。
但是我们想想如果这些数据是从一万开始的呢,那么我零到9999的空间不就浪费了嘛?
那么我们可以在这堆数字里找出一个最小值,每个数组的数组减去最小值,成为下标,那么空间浪费就会很少。懂了吗?就是让arr中最小的数做代表tmp数组下标为零。
那么就开始实现代码
void CountSort(int* arr, int n)
{
int max = arr[0], min = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
memset(count, 0, sizeof(int) * range);
for (int j = 0; j < n; j++)
{
count[arr[j] - min]++;
}
int i = 0;
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
arr[i++] = j + min;
}
}
}
我们把tmp数组中不为零的地方代表出现次数,开始遍历就可以了,记得往arr数组中输入数的时候,加上刚才减去的min值
这个排序就是适合比较的数在集中的范围的情况