|
|
8.计数排序
|
|
|
|
|
|
8.1 描述
|
|
|
计数排序核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
|
|
|
找出待排序的数组中最大和最小的元素；
|
|
|
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
|
|
|
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
|
|
|
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
|
|
|
8.2 复杂程度
|
|
|
时间复杂度O(n+k) 空间复杂度O(n+k)
|
|
|
8.3 代码
|
|
|
#include<stdio.h>
|
|
|
#include<assert.h>
|
|
|
#include<stdlib.h>
|
|
|
//计数排序
|
|
|
void CountSort(int *a, int len)
|
|
|
{
|
|
|
assert(a);
|
|
|
//通过max和min计算出临时数组所需要开辟的空间大小
|
|
|
int max = a[0], min = a[0];
|
|
|
for (int i = 0; i < len; i++)
|
|
|
{
|
|
|
if (a[i] > max)
|
|
|
max = a[i];
|
|
|
if (a[i] < min)
|
|
|
min = a[i];
|
|
|
}
|
|
|
//使用calloc将数组都初始化为0
|
|
|
int range = max - min + 1;
|
|
|
int *b = (int *)calloc(range, sizeof(int));
|
|
|
//使用临时数组记录原始数组中每个数的个数
|
|
|
for (int i = 0; i < len; i++)
|
|
|
{
|
|
|
//注意：这里在存储上要在原始数组数值上减去min才不会出现越界问题
|
|
|
b[a[i] - min] += 1;
|
|
|
}
|
|
|
int j = 0;
|
|
|
//根据统计结果，重新对元素进行回收
|
|
|
for (int i = 0; i < range; i++)
|
|
|
{
|
|
|
while (b[i]--)
|
|
|
{
|
|
|
//注意：要将i的值加上min才能还原到原始数据
|
|
|
a[j++] = i + min;
|
|
|
}
|
|
|
}
|
|
|
//释放临时数组
|
|
|
free(b);
|
|
|
b = NULL;
|
|
|
}
|
|
|
//打印数组
|
|
|
void PrintArray(int *a, int len)
|
|
|
{
|
|
|
for (int i = 0; i < len; i++)
|
|
|
{
|
|
|
printf("%d ", a[i]);
|
|
|
}
|
|
|
printf("\n");
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int a[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
|
|
|
printf("排序前：");
|
|
|
PrintArray(a, sizeof(a) / sizeof(int));
|
|
|
CountSort(a, sizeof(a) / sizeof(int));
|
|
|
printf("排序后：");
|
|
|
PrintArray(a, sizeof(a) / sizeof(int));
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
8.4 运行时间
|
|
|
0.02336s |
