目录
一、什么是计数排序
计数排序是一种非比较型的排序算法,它通过统计待排序数据中每个元素出现的次数,然后根据这个次数来进行排序。计数排序的具体步骤如下:
- 首先找出待排序数据中的最大值和最小值。
- 创建一个新的数组,长度为最大值和最小值之间的范围,并初始化为0。
- 遍历待排序数组,统计每个元素出现的次数,存储到新数组对应位置。
- 根据新数组中统计的次数,将数据重新排列得到排序后的数组。
计数排序适用于数据范围相对较小且数据比较集中的情况,它的时间复杂度为O(n+k),其中n为数据数量,k为数据范围。计数排序是稳定的排序算法,它不是基于比较的排序方法,因此在某些情况下可以比快速排序和归并排序等比较排序算法更快。但是计数排序需要额外的空间用于存储计数,所以在数据范围非常大的情况下可能会占用大量内存。
二、思路
将一组数据相对映射到一个数组中,通过数组建立索引来排序。不需要像基数排序一样存储原数据,只需要得到相对映射值加上最小值即为当前值。
具体步骤:
- 找到最大最小值,计算需要开辟的索引数组空间的大小
- 建立索引:每一个值减去基准值得到了索引数组的下标
- 排序:遍历索引数组,其中不为0的元素即为排好的数据。复原只需要加上基准值即可
三、代码实现
void CountSort(int* a,int n)
{
//遍历找最大最小值
int max = a[0];
int min = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
//开辟基准数组
int size = max - min + 1;
int* tmp = (int*)malloc(sizeof(int) * size);
if (tmp == NULL)
{
perror(malloc);
exit(1);
}
memset(tmp, 0, sizeof(int) * size);
//建立索引
for (int j = 0; j < n; j++)
{
tmp[a[j] - min]++;
}
//排序
int q = 0;
for (int m = 0; m < size; m++)
{
while (tmp[m]--)
{
a[q++] = m + min;
}
}
}