广东网站设计公司,企业网站建设规划方案,网站建设 尚品中国,网站项目开发收费标准目录
1. 计数排序的思想动图 2. 从思想到代码的实现 1.创建临时数组
2.统计次数
3.排序
4.简单版本
3. 是否可以优化呢~
4. 计数排序的时空复杂度
5.总结
计数排序的优点
计数排序的局限性
6、完结散花 个人主页#xff1a;秋风起#xff0c;再归来…目录
1. 计数排序的思想动图 2. 从思想到代码的实现 1.创建临时数组
2.统计次数
3.排序
4.简单版本
3. 是否可以优化呢~
4. 计数排序的时空复杂度
5.总结
计数排序的优点
计数排序的局限性
6、完结散花 个人主页秋风起再归来~ 数据结构与算法 个人格言悟已往之不谏知来者犹可追 克心守己律己则安 1. 计数排序的思想动图 2. 从思想到代码的实现 1.创建临时数组
我们先创建一个临时的数组tmp并且该数组的最大下标为原数组中元素的最大值里面的元素初始化为0 //先遍历原数组找到最大值int max a[0];for (int i 1; i n; i){if (max a[i]){max a[i];}}//动态内存开辟max1个int空间并初始化为0用callocint* tmp (int)calloc(max1, sizeof(int));if (tmp NULL){perror(calloc fail!\n);return;}
2.统计次数
然后遍历一遍原数组原数组中出现哪个元素就在tmp数组中与该元素数值相同的下标对应的地方进行加加操作来记录该元素出现的次数。 //统计次数for (int i 0; i n; i){tmp[a[i]];}
3.排序
最后我们再进行排序记住tmp的下标对应原数组可能出现的元素而里面的值对应该元素出现的次数如果为0就说明该元素在原数组不存在。遍历tmp数组将对应的下标覆盖原数组即可完成排序。
//排序
int j 0;
for (int i 0; i max 1; i)//第一层循环遍历tmp数组
{while (tmp[i]--)//对应元素出现的次数{a[j] i;//tmp的下标对应的就是原数组可能出现的元素}
}
//释放资源避免内存泄漏
free(tmp);
tmp NULL;
4.简单版本
好现在简单的计数排序就已经完成了
完整代码
void CountSort(int* a,int n)
{//先遍历原数组找到最大值int max a[0];for (int i 1; i n; i){if (max a[i]){max a[i];}}//动态内存开辟max1个int空间并初始化为0用callocint* tmp (int*)calloc(max1, sizeof(int));if (tmp NULL){perror(calloc fail!\n);return;}//统计次数for (int i 0; i n; i){tmp[a[i]];}//排序int j 0;for (int i 0; i max 1; i)//第一层循环遍历tmp数组{while (tmp[i]--)//对应元素出现的次数{a[j] i;//tmp的下标对应的就是原数组可能出现的元素}}//释放资源避免内存泄漏free(tmp);tmp NULL;
} 3. 是否可以优化呢~
思考一下如果我们的数据是这样的呢如果还像之前那样开辟空间是否会有大量的空间浪费呢遍历的次数增大是否有性能的降低呢~ 所以我们就可以这样取tmp的范围 优化后代码
//先遍历原数组找到最大值
int max a[0];
int min a[0];
for (int i 1; i n; i)
{if (max a[i]){max a[i];}if (min a[i]){min a[i];}
}
int range max - min 1;
//动态内存开辟max1个int空间并初始化为0用calloc
int* tmp (int*)calloc(range, sizeof(int));
if (tmp NULL)
{perror(calloc fail!\n);return;
} 关于下标与元素对应的问题我们就可以采用相对映射的方法来解决优化后代码 优化后的完整代码
void CountSort(int* a,int n)
{//先遍历原数组找到最大值int max a[0];int min a[0];for (int i 1; i n; i){if (max a[i]){max a[i];}if (min a[i]){min a[i];}}int range max - min 1;//动态内存开辟max1个int空间并初始化为0用callocint* tmp (int*)calloc(range, sizeof(int));if (tmp NULL){perror(calloc fail!\n);return;}//统计次数for (int i 0; i n; i){tmp[a[i]-min];}//排序int j 0;for (int i 0; i range; i)//第一层循环遍历tmp数组{while (tmp[i]--)//对应元素出现的次数{a[j] imin;//tmp的下标对应的就是原数组可能出现的元素}}//释放资源避免内存泄漏free(tmp);tmp NULL;
} 4. 计数排序的时空复杂度
空间复杂度除原数组外计数排序额外开辟了一个大小为N的临时空间所以计数排序的空间复杂度为O(N)。
时间复杂度遍历找最大最小值取范围的时间复杂度为O(N)遍历原数组统计次数的时间复杂度为O(N)而排序里面虽有两层循环但从思想和本质来看它只不过是将原来的元素按顺序覆盖了原数组其执行循环的次数任然为O(N)所以计数排序的时间复杂度为O(N).
5.总结
计数排序Counting Sort是一种非比较排序算法它的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。
计数排序的优点
稳定性计数排序是一种稳定的排序算法即相等的元素在排序过程中不会改变相对位置。时间复杂度低在数据范围不是很大的情况下计数排序的时间复杂度可以达到O(n)是非常高效的排序算法。空间换时间计数排序通过使用额外的空间来换取排序时间的大幅度降低适合数据范围不大的情况。
计数排序的局限性
数据范围限制当数据的范围非常大时计数排序需要创建一个长度为最大值加一的数组这将导致大量的空间浪费因此它不适合数据范围很大的排序。数据类型限制计数排序只适用于整数排序对于其他类型的数据如字符串、浮点数等则不适用。空间复杂度较高计数排序需要额外的存储空间来存储临时数组当数据范围较大时其空间复杂度会显著增加。
综上所述计数排序在特定条件下数据范围不大且为整数是非常高效的排序算法但在数据范围大或数据类型不匹配时则不适用。在实际应用中需要根据具体的数据特征选择合适的排序算法。
6、完结散花
好了这期的分享到这里就结束了~
如果这篇博客对你有帮助的话可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话可以点点关注避免找不到我了呢~
我们下期不见不散~~
