数据结构计数排序（Counting Sort）详解附C++代码实现：

谁践踏了优雅 2024-02-19 18:13 63阅读 0赞

**目录**

简介：

算法描述：

代码实现：

总结：

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

## 简介： ##

计数排序是一种非比较类排序算法，稳定的算法，时间、空间复杂度为o（n+k）

## 算法描述： ##

*  找出待排序的数组中最大和最小的元素；
 *  统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
 *  对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
 *  反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

![849589-20171015231740840-6968181.gif][]

## 代码实现： ##

#include<iostream>
    #include<time.h>
    #include<stdlib.h>
    #include<stdio.h>
    using namespace std;
    #define range 10000
    void CountingSort(int a[],int b[],int len)
    {
    	int cnt=0;
    	for(int i=0;i<len;i++)
    	{
    		b[a[i]]++;
    	}
    	for(int i=0;i<len;i++)
    	while(b[i]!=0)
    	{
    		a[cnt++]=i;
    		b[i]--;
    	}
    }
    
    int main()
    {
    	clock_t start,end;
    	start=clock();
    	freopen("out_arr.txt","r",stdin);
    	freopen("out_计数排序.txt","w",stdout);
    	int a[range],b[range]={0};
    	for(int i=0;i<range;i++)
    	{
    		scanf("%d",&a[i]);
    	}
    	CountingSort(a,b,range);
    	for(int i=0;i<range;i++)
    	{
    		printf("%5d ",a[i]);
    		if((i+1)%50==0)
    		printf("\n");
    	}
    	end=clock();
    	printf("计数排序耗时：%dms\n",(float)(end-start)*1000.0/CLOCKS_PER_SEC);
    	
    	
    	
    	
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70][]

## 总结： ##

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

##  ##

[849589-20171015231740840-6968181.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/7aafe851303a4126b12ce0450cceed92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/0e6a150f327741d0a14614c6cc80f72d.png