找个网站这么难2021,广州做淘宝的化妆品网站,凡科代理平台,吉木萨尔县建设局网站计数排序 前言一、计数排序算法核心思路映射 概念补充绝对映射相对映射 二、计数排序算法核心实现步骤三、码源详解四、效率分析#xff08;1#xff09;时间复杂度 — O#xff08;Max#xff08;N#xff0c;range#xff09;#xff09;#xff08;2#xff09;空间… 计数排序 前言一、计数排序算法核心思路映射 概念补充绝对映射相对映射 二、计数排序算法核心实现步骤三、码源详解四、效率分析1时间复杂度 — OMaxNrange2空间复杂度 — Orange 前言
计数排序是一种 非比较排序。计数排序又称为 鸽巢原理 是对哈希直接定址法的变形应用。 一、计数排序算法核心思路 映射 概念补充
每个值跟其位置建立出一个关系
绝对映射
数值是几就映射出下标是几。如上图
若数组中数据的大小范围并不是乖乖的从0-1那么这是再采用绝对映射则会产生很大的空间浪费。 那么就有了相对映射的概念
相对映射 通过遍历原数组找出min值将 a[i] 的值 - min值 【即 a[ i ] - min 】就是对应 数组count[ ]的下标了遍历到一个就令该下标 对应a[i]的值 下的 count [ ] 值计数。 二、计数排序算法核心实现步骤 遍历一遍数组 得出min和max值 确定数的范围 确定范围 确定需要开辟的数组的大小 开辟大小为range的空间count [ ] (避免了 绝对映射 那样的空间的浪费) 。用作统计 需排序的数组a[i] 中每个数据出现的次数。 【注意要进行初始化否则待会遍历计数数组中那些并没有统计到有这个数出现的次数的位置将以该内存原来的值随机数进行填入】 遍历待排序的数组 统计数组中每个数据出现的次数 通过 a[i]-min 找到对应下标在 count 中的对应下标 对该下标的值对应进行计数 遍历计数数组根据统计到的每个数的次数count[i]就拷贝回去原数组count[i]次imin:对应回原数组中的值while()循环覆盖原数组 三、码源详解
//计数排序——非比较排序
void CountSort(DataType* a,int n) {//遍历一遍数组 得出min和max值 确定数的范围int min a[0]; int max a[0];for (int i 0; i n; i) {if (a[i] min) {min a[i];}if (max a[i]) {max a[i];}//确定范围 确定需要开辟的数组的大小int range max - min 1; //[min,max]左闭右闭所以1//开辟大小为range的空间避免了 绝对映射 那样的空间的浪费DataType* count (DataType*)malloc(sizeof(DataType)*range);if (count NULL) {perror(malloc fail);exit(-1);}//内存重置 将count数组中的值都初始化为0重置数组大小为sizeof(DataType) * range//要进行初始化否则待会遍历计数数组中那些并没有统计到有这个数出现的次数的位置将以该内存原来的值随机数进行填入memset(count, 0, sizeof(DataType) * range);//数组中的值//遍历数组 统计数组中各数据出现的次数 通过 a[i]-min 找到对应下标在 count 中的对应下标 对该下标的值对应进行计数for (i 0; i n; i) {count[a[i] - min];}//排序//遍历计数数组根据统计到的每个数的次数count[i]就拷贝回去原数组count[i]次覆盖原数组//遍历数组int j 0; //放外面遍历a[] j记录的数值 不会别被清for (i 0; i range; i) {while (count[i]--){ //count[i]0的进不了循环a[j] i min; //imin:对应回原数组中的值}}}
}四、效率分析
总体特点比较小众
适用于数据范围相对集中。只适合整形基数排序
1时间复杂度 — OMaxNrange
2空间复杂度 — Orange
