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

小咪咪 2023-10-03 19:41 49阅读 0赞

### ![30adcf5df8b44dc8bc660f667cada2c4.jpeg][] ###

哈喽大家好，我是保护小周ღ，本期为大家带来的是[排序算法][Link 1]中的计数排序，非常的有意思，值得学习而且计数排序是非交换排序**，**分享所有源代码，粘贴即可运行，保姆级讲述**，**包您一看就会，快来试试吧~

![f89deef4fd5b408f8b4b1c0a50c0a9e9.png][]

**目录**

一、计数排序

1.1 算法思想

1.2 程序设计

1.3 程序实现

1.4 计数排序总结

--------------------

## 一、计数排序 ##

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。\[1\] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n\*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n\*log(n)), 如归并排序，堆排序）

——**百度百科**

--------------------

### 1.1 算法思想： ###

![d123333adeb6403982f64cb0818595b1.png][]

其实会发现一个主要问题，那么就是tmp数组（使用动态开辟）到底应该开辟多大的空间，怎么计算。

假设我们有组数据，100 101 102 101 109 105 105；

我们应该开辟多大的空间，因为最大值是109，从0开始需要开辟110个空间吗？那太浪费了。

![2386830aa1f644d8be808866696ac572.png][]

所以我们只需要最大值-最小值+1的空间，max=109,min=100 , max-min+1=10；使用相对映射的位置。

![365e3fe7b8464f59a8222be273192472.png][]

--------------------

### 1.2 程序设计 ###

**第一步**：

> 我们自定义一个函数CountSort();将计数排序的功能实现一下，参数有数组a的地址（我们用指针接收，数组名其实就是地址），另一个参数是：计算数组a里有多少个元素，标准操作为：
> 
> **sizeof ( a ) / sizeof ( a\[ 0 \] );**

**第二步**：

> 我们要在函数内部计算数组a里元素的最大值和最小值（遍历），然后求出数据的范围 **range=max - min +1;**

**第三步**：

> 定义动态开辟的数组tmp,因为我已经得到数据有多少，我们就可以开辟了。
> 
> 但是我们又想要将tmp数组里的值初始化为0；
> 
> 博主的方式是直接使用calloc();开辟，calloc() 与 malloc() 函数是一样的功能，只是 calloc() 的函数参数表达方式略有不同，其次是它会将动态开辟的空间值初始化为0；
> 
> 还有一种方法是使用 memset()函数，**menset(tmp, 0 , sizeof( int ) \* range );**这几个参数应该能理解吧？
> 
> 只要是动态开辟的空间，我们用完之后一定要随手将它释放掉，就像打括号 \{ \} 一样，可以先写着，避免遗忘。将free（tmp）；放到代码最后即可。

**第四步**：

> 统计数组a里的每个元素出现的次数，然后映射至tmp数组。（使用相对映射）；

**第五步**：

> 将tmp数组里不为0的元素的下标+min反赋给数组a,遍历结束，排序完成。

--------------------

### 1.3 程序实现： ###

#define _CRT_SECURE_NO_WARNINGS
    
    #include<stdio.h>
    #include<stdlib.h>
    
    void CountSort(int* a, int n)
    {
    	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* tmp = (int*)calloc(range, sizeof(int));//动态开辟
    	if (tmp==NULL)//如果空间申请失败，报个错，并中止程序
    	{
    		perror("calloc");
    		return;
    	}
    
    	for (int i = 0; i < n; ++i)//统计数组a每个元素出现的次数
    	{
    		tmp[a[i] - min]++;
    	}
    	int j = 0;
    	for (int i=0;i<range;++i)//
    	{
    		while (tmp[i])//判断tmp数组该元素是否有计数。
    		{
    			a[j++] = i + min;//如果有就把该元素的下标值反映射至数组a
    			tmp[i]--;
    		}
    	}
    	//动态开辟的空间，主动释放
    	free(tmp);
    	tmp = NULL;
    }
    
    //打印
    void Print(int* a,int n)
    {
    	for (int i=0;i<n;++i)
    	{
    		printf("%d ",a[i]);
    	}
    }
    
    int main()
    {
    	int a[] = {-1,1,2,9,8,8,1,3,4,3,4,5};
    	CountSort(a, sizeof(a) / sizeof(a[0]));//计数排序
    	Print(a, sizeof(a) / sizeof(a[0]));//打印
    	return 0;
    }

![7c8cbc8891474ff8a49a969dec0e9300.png][]

--------------------

### 1.4 计数排序总结 ###

计数排序：思想很巧妙，适用范围具有局限性(整型数据)

时间复杂度：O(N+range);非常块，但是数据范围很大的就差些，说明它适用于范围集中一组整型数据排序。

空间复杂度：O(range);

--------------------

至此计数排序的算法思想博主已经分享完了，相信大家对这个逻辑有了一定的理解，大家可以自己动手敲敲代码，感受一下。

![40e36dfc27804c04afb4a9da45afda94.jpeg][]

本期收录于博主的专栏——排序算法，适用于编程初学者，感兴趣的朋友们可以订阅，查看其它“常见排序”。[ 排序算法\_保护小周ღ的博客-CSDN博客][_-CSDN]

感谢每一个观看本篇文章的朋友，更多精彩敬请期待：保护小周ღ \*★,°\*:.☆(￣▽￣)/$:\*.°★\*

文章存在借鉴，如有侵权请联系修改删除！![dd8b4788b2554df4bec4b8202395cad2.gif][]

[30adcf5df8b44dc8bc660f667cada2c4.jpeg]: https://img-blog.csdnimg.cn/30adcf5df8b44dc8bc660f667cada2c4.jpeg
[Link 1]: https://so.csdn.net/so/search?q=%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95&spm=1001.2101.3001.7020
[f89deef4fd5b408f8b4b1c0a50c0a9e9.png]: https://img-blog.csdnimg.cn/f89deef4fd5b408f8b4b1c0a50c0a9e9.png
[d123333adeb6403982f64cb0818595b1.png]: https://img-blog.csdnimg.cn/d123333adeb6403982f64cb0818595b1.png
[2386830aa1f644d8be808866696ac572.png]: https://img-blog.csdnimg.cn/2386830aa1f644d8be808866696ac572.png
[365e3fe7b8464f59a8222be273192472.png]: https://img-blog.csdnimg.cn/365e3fe7b8464f59a8222be273192472.png
[7c8cbc8891474ff8a49a969dec0e9300.png]: https://img-blog.csdnimg.cn/7c8cbc8891474ff8a49a969dec0e9300.png
[40e36dfc27804c04afb4a9da45afda94.jpeg]: https://img-blog.csdnimg.cn/40e36dfc27804c04afb4a9da45afda94.jpeg
[_-CSDN]: https://blog.csdn.net/weixin_67603503/category_11904303.html?spm=1001.2014.3001.5482
[dd8b4788b2554df4bec4b8202395cad2.gif]: https://img-blog.csdnimg.cn/dd8b4788b2554df4bec4b8202395cad2.gif