该篇文章 所涉及代码收录仓库:登录 - Gitee.com
目录
2.以int a[] = { 1,3,9,1,5,1,2,3,-5,-5,-2 };为例,手撕分析
1.非比较排序——计数排序
思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。
2.最终实现
1.解析
2.以int a[] = { 1,3,9,1,5,1,2,3,-5,-5,-2 };为例,手撕分析
3.代码实现
void CountSort(int* a, int n)
{//找出最大和最小元素
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;//确定新创建数组的数据个数和原数组大小相同,便于下面计数
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
printf("calloc fail\n");
return;
}
// 统计次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;//min作为偏移量,然后再在对应数组位置++,统计该数字出现的次数
}
// 排序
int i = 0;
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
}