做统计表的网站,小程序一般用什么语言开发,好网站建设网站,热门游戏推荐读者老爷好#xff0c;本鼠鼠最近学了计数排序#xff0c;浅浅介绍一下#xff01;
目录
1.统计相同元素出现次数
2.根据统计的结果将序列回填到原来的序列中
3.相对映射计数排序 计数排序又称为鸽巢原理#xff0c;是对哈希直接定址法的变形应用#xff0c;是非比较排…
读者老爷好本鼠鼠最近学了计数排序浅浅介绍一下
目录
1.统计相同元素出现次数
2.根据统计的结果将序列回填到原来的序列中
3.相对映射计数排序 计数排序又称为鸽巢原理是对哈希直接定址法的变形应用是非比较排序的一种
这个排序算法不难理解万物皆可举例我们举例讲解啊 很久很久以前有一只可爱的肥龙猫叫做冬冬。有一天冬冬的男朋友给冬冬出了一个题目有一组数组a如下要冬冬用排序算法排成升序。 聪明的冬冬使用了计数排序解决了这个问题还将解决办法告诉了本鼠方法如下
1.统计相同元素出现次数
冬冬遍历数组a后知道最大的元素是9。所以冬冬开了一个大小为10*sizeof(int)的数组tmp并将数组tmp元素全部初始化为0如下图。用来统计相同元素出现的次数 冬冬再次遍历数组a遇到第一个元素是5那么冬冬就将tmp[5]tmp[5]就等于1了遇到第二个元素是3冬冬就将tmp[3]tmp[3]就等于1了遇到第三个元素是5冬冬就将tmp[5]tmp[5]就等于2了………… 冬冬说其实采用了绝对映射的办法将a的各个元素绝对映射到tmp的元素下标当中a的相同元素出现的次数就体现在tmp相对应下标元素的值。例如a元素5就出现了3次a[5]3。
2.根据统计的结果将序列回填到原来的序列中
冬冬遍历tmp就知道了a相同元素出现的次数a元素0出现了0次、1出现了0次……3出现了1次、4出现了0次…………
冬冬在遍历tmp的同时将a回填好就行了 冬冬还用代码验证了可行性本鼠偷偷将代码附上
//绝对映射计数排序
void CountingSort(int* a, int n)
{int max a[0];//遍历找a元素最大值for (int i 1; i n; i){if (a[i] max){max a[i];}}//动态申请a元素最大值1个sizeof(int)数组并初始化int* tmp (int*)calloc(max 1, sizeof(int));if (tmp NULL){perror(malloc fail);return;}//统计a相同元素出现次数for (int i 0; i n; i){tmp[a[i]];}//根据统计结果回填aint j 0;for (int i 0; i max 1; i){while (tmp[i]--){a[j] i ;}}
}
冬冬的测试代码本鼠也偷偷拿来了
int main()
{int a[] { 5,3,5,8,5,9 };CountingSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i){printf(%d , a[i]);}return 0;
} 3.相对映射计数排序 冬冬是一只精益求精的肥龙猫它想如果需排序数组a元素都在1000左右的话如图 用绝对映射计数排序的话动态申请的用来统计a相同元素出现次数的tmp要开1000*sizeof(int)个字节的空间而且大部分空间都没有用到如图红色部分都浪费了 a元素999映射tmp[999]的下标999、990映射tmp[990]的下标990…… 冬冬就想了一个办法采用相对映射实现计数排序。冬冬遍历数组a找到最大元素999和最小元素990得出a的元素数据范围动态申请数组tmp就开a的元素数据范围1个sizeof(int)大小的空间就好了 a元素999映射tmp[9]的下标9、990映射tmp[0]的下标0…… 其实相对映射就是将a元素映射tmp对应元素下标都减去了a的最小元素值这里是990 冬冬说那么回填a的时候对应元素下标记得都加上a的最小值再回填到a就好了
//相对映射计数排序
void CountingSort(int* a, int n)
{//遍历a找出最大元素和最小元素int max a[0], min a[0];for (int i 1; i n; i){if (a[i] max){max a[i];}if (a[i] min){min a[i];}}//动态申请a元素数据范围1个sizeof(int)字节数组并初始化int* tmp (int*)calloc(max - min 1, sizeof(int));if (tmp NULL){perror(malloc fail);return;}//统计a相同元素出现次数for (int i 0; i n; i){tmp[a[i] - min];}//根据统计结果回填aint j 0;for (int i 0; i max - min 1; i){while (tmp[i]--){a[j] i min;}}
}
冬冬说采用相对映射对于a中有负数也一样适用如果采用绝对映射的话就不行捏绝对映射到的下标不可能是负数
int main()
{int a1[] { 5,3,5,-8,5,-9 };int a2[] { 999,998,997,996,999,990 };CountingSort(a1, sizeof(a1) / sizeof(int));CountingSort(a2, sizeof(a2) / sizeof(int));for (int i 0; i sizeof(a1) / sizeof(int); i){printf(%d , a1[i]);}printf(\n);for (int i 0; i sizeof(a2) / sizeof(int); i){printf(%d , a2[i]);}return 0;
} 冬冬说实际上相对映射计数排序才是真正的计数排序
4.计数排序特性 1.计数排序不适合分散的数据在数据范围集中时效率极高。但是适用范围及场景有限不适合浮点数、字符串、结构体等数据的排序只适合整数
2.时间复杂度O(MAX(N,范围))。范围是指a的元素数据范围下同。
3.空间复杂度O(范围)。 冬冬谢谢您的阅读嘞
