常熟建设局网站,网站模板建网站,百度高级搜索入口,项目管理工具目录
CountSort计数排序
整体思想
图解分析
代码实现
时间复杂度优缺分析 CountSort计数排序 计数排序是一种非比较排序#xff0c;不需要像前面的排序一样去比较。 计数排序的特性总结#xff1a; 1. 计数排序在数据范围集中时#xff0c;效率很高#xff0c;但…目录
CountSort计数排序
整体思想
图解分析
代码实现
时间复杂度优缺分析 CountSort计数排序 计数排序是一种非比较排序不需要像前面的排序一样去比较。 计数排序的特性总结 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2. 时间复杂度O(MAX(N,范围)) 3. 空间复杂度O(范围) 4. 稳定性稳定 整体思想 思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。1. 统计相同元素出现次数2. 根据统计的结果将序列回收到原来的序列中 Count数组 Count数组中的元素需要全部初始化为0calloc就可以满足这个要求Count元素是 计算a数组元素个数出现的次数Count数组的下标是a数组元素的范围绝对隐射范围0~maxa中最大的元素相对隐射范围0~max-min min~maxrange max-min1映射0~max-min个数max-min1) 整个流程 遍历一遍找到最大值 / 最小值计算出Count数组下标范围并且开辟动态空间ranggemax-min1计数Count[a[i]-min] (i)相对隐射回去 注意tips i和j能不能公用❓a数组的元素可以是负数吗除了整型其他类型可以吗后置--前置-- calloccalloc - C Reference (cplusplus.com)Count的下标表示a的元素的范围Count的元素表示a的元素出现的个数计数 图解分析 代码实现
void CountSort(int* a, int n)
{//找最大值/最小值/创建的tmp的范围在这个之间int max a[0];int min a[0];for (int i 0; i n; i){if (a[i] max){max a[i];}if (a[i] min){min a[i];}}int range max - min 1;//注意int* count (int*)calloc(range, sizeof(int));//计数for (int j 0; j n; j){count[a[j]-min];}//相对隐射回去int i 0;for (int k 0; k range; k){while (count[k]--){a[i] k min;}}
}
时间复杂度优缺分析 时间复杂度ON 时间复杂度OaNcounNcount的N是a的数据范围计数排序不需要比较元素大小优势效率极高局限性不适合范围很大计数排序只适用于整型不同数据类型的实践意义不高。现实实践更多的是结构体排序不能适用计数排序 感谢大家的阅读若有错误和不足欢迎指正。下篇总结各个排序。
