计数排序.

  一.定义：

计数排序（Counting Sort）是一种非比较性质的排序算法，其时间复杂度为O(n+k)（其中n为待排序的元素个数，k为不同值的个数）。这意味着在数据值范围不大并且离散分布的情况下，规模越大，排序速度越快的特点。然而，如果数列元素不满足整数和有确定范围的条件，则不能使用计数排序。

二.原始代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>// 计数排序
void count_sort(int num[], int len) {// 寻找最大值int max = num[0];for (int i = 1; i < len; i++) {max = max > num[i] ? max : num[i]; // 更新最大值}int range = max + 1; // 计数数组的长度为最大值加1int *arr = (int *)malloc(sizeof(int) * range);	// 申请空间memset(arr, 0, sizeof(int) * range); // 初始化计数数组为0for (int i = 0; i < len; i++) {arr[num[i]]++; // 对每个元素进行计数}// 填充原数组int j = 0;for (int i = 0; i < range; i++) {while (arr[i] != 0) { // 将计数数组中的每个非零元素放回原数组num[j] = i; // 填充元素arr[i]--; // 计数减一j++; // 标记原数组填充到的位置}}free(arr); // 释放计数数组空间
}int main() {int num[12] = { 5, 8, 5, 4, 6, 8, 9, 7, 2, 3, 4, 5 };count_sort(num, 12); // 执行计数排序// 打印结果for (int i = 0; i < 12; i++){printf("%d ", num[i]);}return 0;
}

输出结果：

2 3 4 4 5 5 5 6 7 8 8 9

代码优点：

1. 计数排序是一个非比较排序算法，对于一个给定的输入数组，不论数组中的数字如何分布，其时间复杂度始终稳定在O(n)。
2. 擅长处理小范围大量重复的整数数据，效率非常高，实际运行速度通常比其他的O(n log n)比较类排序算法要快。

代码缺点：

1. 计数排序算法只能用来排序整数，并且只能处理非负整数，对于负整数和小数，此算法无法正常工作，需要进行额外处理才能排序。
2. 该排序算法需要额外的空间来存储计数数组，如果输入数据的范围（最大值-最小值）过大，将会导致空间的大量浪费。
3. 如果待排序的数列中最大和最小数值的差过大，需要很大的辅助空间，因此空间复杂度显著上升，空间效率低。
4. 计数排序是一种不稳定的排序，无法保证相同数值的元素在排序后保持原有的顺序。

三.优化代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>// 计数排序函数
void count_sort(int num[], int len) {int max = num[0];   // 初始化最大值为数组第一个元素int min = num[0];   // 初始化最小值为数组第一个元素// 找出数组中最大值和最小值for (int i = 1; i < len; i++) {max = max > num[i] ? max : num[i];min = min < num[i] ? min : num[i];}int range = max - min + 1;  // 计算最大值与最小值的差值和1（确定结果数组的大小）// 动态分配range大小的计数数组，并初始化为0int *arr = (int *)malloc(sizeof(int) * range);memset(arr, 0, sizeof(int) * range); // 计算每个元素出现的次数for (int i = 0; i < len; i++) {arr[num[i]-min]++;  // 使用当前元素值减去最小值作为索引}// 按升序排列原数组for (int i = 0, t = 0; i < range; i++) {while (arr[i] != 0) {num[t] = i + min;  // 使用当前索引加上最小值得到原始值t++;arr[i]--;   // 减去一个元素的计数}}// 释放动态分配的计数数组空间free(arr);
}int main() {// 待排序的数组int num[10] = { -10, 10, -9, 9, 8, 7, 7, 6, 6, 6 };// 使用计数排序算法进行排序count_sort(num, 10);// 输出排序后的数组元素for (int i = 0; i < 10; i++) {printf("%d ", num[i]);}return 0;
}

优化点：

1.可以实现包含负数的数组排序