百度开放云做网站,云主机网站的空间在哪里看,公司网页设计免费,软件app开发制作多少钱一.定义#xff1a;
计数排序#xff08;Counting Sort#xff09;是一种非比较性质的排序算法#xff0c;其时间复杂度为O(nk)#xff08;其中n为待排序的元素个数#xff0c;k为不同值的个数#xff09;。这意味着在数据值范围不大并且离散分布的情况下#xff0c;规… 一.定义
计数排序Counting Sort是一种非比较性质的排序算法其时间复杂度为O(nk)其中n为待排序的元素个数k为不同值的个数。这意味着在数据值范围不大并且离散分布的情况下规模越大排序速度越快的特点。然而如果数列元素不满足整数和有确定范围的条件则不能使用计数排序。
二.原始代码
#includestdio.h
#includestring.h
#includestdlib.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
代码优点
计数排序是一个非比较排序算法对于一个给定的输入数组不论数组中的数字如何分布其时间复杂度始终稳定在O(n)。擅长处理小范围大量重复的整数数据效率非常高实际运行速度通常比其他的O(n log n)比较类排序算法要快。
代码缺点
计数排序算法只能用来排序整数并且只能处理非负整数对于负整数和小数此算法无法正常工作需要进行额外处理才能排序。该排序算法需要额外的空间来存储计数数组如果输入数据的范围最大值-最小值过大将会导致空间的大量浪费。如果待排序的数列中最大和最小数值的差过大需要很大的辅助空间因此空间复杂度显著上升空间效率低。计数排序是一种不稳定的排序无法保证相同数值的元素在排序后保持原有的顺序。 三.优化代码
#includestdio.h
#includestdlib.h
#includestring.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.可以实现包含负数的数组排序
