福建省网站建设公司聚名网

原理：

存在的问题：数组空间浪费

所以要相对映射，不要绝对映射

calloc()函数的功能是:为num个大小为size的元素开辟一块空间,并且把空间的每个字节初始化为0.

// 时间复杂度:O(N+range)
// 只适合整数/适合范围集中
// 空间范围度：O(range)
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;//printf("%d\n", range);int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail");return;}// 统计次数for (int i = 0; i < n; i++){count[a[i] - min]++;}// 排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}free(count);
}