非比较排序算法之计数排序

青旅半醒 2023-07-03 07:20 12阅读 0赞

## 计数排序 ##

基本思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。  
操作步骤：  
1、统计相同元素出现次数  
2、根据统计的结果将序列回收到原来的序列中  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]

//计数排序
    void CountSort(int* a, int n)
    { 
    	int max = a[0], 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*)malloc(sizeof(int)* range);
    	memset(count, 0, sizeof(int)* range);
    	for (int i = 0; i < n; i++)
    	{ 
    		count[a[i] - min]++;
    	}
    	int j = 0;
    	for (int i = 0; i < range; i++)
    	{ 
    		while (count[i]--)
    		{ 
    			a[j++] = i + min;
    		}
    	}
    }

计数排序的特性总结：  
1、计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。  
2、时间复杂度：O(MAX(N,范围)))  
3、空间复杂度：O(范围)  
4、稳定性：稳定

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200204114438225.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法——计数排序（非比较排序）

![30adcf5df8b44dc8bc660f667cada2c4.jpeg][] 哈喽大家好，我是保护小周ღ，本期为大家带来的是[排序算法][Link 1]中的计数排

小咪咪/ 2023年10月03日 19:41/ 0 赞/ 34 阅读

相关非比较排序算法之计数排序

计数排序基本思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤： 1、统计相同元素出现次数 2、根据统计的结果将序列回收到原来的序列中

青旅半醒/ 2023年07月03日 07:20/ 0 赞/ 13 阅读

相关排序算法之计数排序

\[非比较排序-计数排序\] 1.算法思想计数排序要求数据必须是有确定范围的整数，需要定义一个新的数组，新数组的长度是根据原数组最大值和最小值来确定的，该数组用

柔光的暖阳◎/ 2022年12月31日 01:09/ 0 赞/ 184 阅读

相关排序算法——计数排序

排序算法——计数排序 > 计数排序是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时，快于任何比较排序算法。这是一种牺牲空间换取时间的做法，当O(k)>

绝地灬酷狼/ 2022年12月23日 06:57/ 0 赞/ 226 阅读

相关 Data Structure--排序--归并排序(递归/非递归)--计数排序(非比较排序)

排序归并排序(递归+非递归) 计数排序(非比较排序) 归并排序(递归+非递归) ![在这里插入图片描述][watermark_type_ZmFuZ3

àì夳堔傛蜴生んèń/ 2022年11月03日 11:19/ 0 赞/ 184 阅读

相关排序算法 —— 计数排序

引言计数排序是桶排序思想的一种具体实现，针对一些具有特殊限制的样本数据，如公司员工年龄，那么样本数据本身就一定在0~200之间，针对这样的数据，使用从0到200 的桶数

我就是我/ 2022年10月16日 12:29/ 0 赞/ 214 阅读

相关排序算法之计数&基数排序

计数排序> 给定一组待排序的数据，找到这组数据中的最大值，然后开辟一个最大值加1的数组，用memset初始化为全0，然后再次遍历原数组，使得这个新开辟的数组中存储的是该数字

曾经终败给现在/ 2022年07月14日 08:00/ 0 赞/ 222 阅读

相关非比较排序-----计数排序，基数排序。

排序总归来说可分为两大类，比较排序与非比较排序。比较排序就是我们常用到的冒泡排序，插入排序，希尔排序，选择排序，堆排序，快速排序，归并排序。非比较排序不常用，但是在对一些特殊的

快来打我*/ 2022年07月14日 04:09/ 0 赞/ 199 阅读

相关排序算法——计数排序

前言计数排序的思想：在给定的数组中，依次寻找比当前数字小的元素的个数（count），统计之后直接使用t就可以定位到该数所在的位置，因为比它小的元素的个数已经通过coun

小鱼儿/ 2022年06月12日 00:44/ 0 赞/ 221 阅读

相关 C++排序算法之计数排序

计数排序像快排、堆排、归并等排序算法都是基于比较的排序算法，时间复杂度最好情况也只能降到O(nlogn)。计数排序是一种线性排序算法，不需要进行比较，时间复杂

妖狐艹你老母/ 2022年06月10日 02:52/ 0 赞/ 173 阅读