计数排序及其时间复杂度、代码(C++实现)、应用场景

x33g5p2x  于10个月前 转载在 C/C++  
字(1.3k)|赞(0)|评价(0)|浏览(98)

一、计数排序概念

计数排序,又叫非比较排序。顾名思义,该算法不是通过比较数据的大小来进行排序的,而是通过统计数组中相同元素出现的次数,然后通过统计的结果将序列回收到原来的序列中。

上列中的映射方法称为绝对映射,即arr数组中的元素是几就在count数组中下标为几的位置++,但这样会造成空间浪费。例如,我们要将数组:102,101,108,进行排序,难道我们要开辟109个整型空间吗?

若是使用计数排序,我们应该使用相对映射,简单来说,数组中的最小值就相对于count数组中的0下标,数组中的最大值就相对于count数组中的最后一个下标。这样,对于数组:102,101,108,我们就只需要开辟用于储存4个整型的空间大小了,此时count数组中下标为i的位置记录的实际上是101+i这个数出现的次数。

总结:
绝对映射:count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
 相对映射:count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。


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

计数排序是一种非基于比较的非稳定线性排序算法。

基本思想是:用空间换时间,本质上是建立了基于元素的Hash表。

(1)假设要排序的数组A原始数据为{2,5,3,0,2,3,0,3},遍历一遍找到最大值为max=5,min=0。

(2)定义一个辅助数组C。max-min+1=6,那么C的大小为6,C数组用memset初始化。

(3)C数组用作统计A数组中元素的个数,若A[k]-min==i,则C[i]++,0<=k<7,例如A中的0有2个,那么C[0-min]=2,min=0。

二、计数排序代码

//计数排序的实现
void CountSort(int* arr, int sz)
{
	//1.首先找出最大值与最小值
	int min = arr[0];
	int max = arr[0];

	for (int i = 0; i < sz; i++)
	{
		if (arr[i]>max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}

	//计算出最大值和最小值之间的元素个数
	int range = max - min + 1;

	int* count = new int[range];
	memset(count, 0, sizeof(count));

	for (int i = 0; i < sz; i++) //统计相同元素出现次数(相对映射)
	{
		count[arr[i] - min]++;
	}

	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			arr[i] = j + min;
		}
	}
	delete[range] count;
}

三、计数排序代码

时间复杂度:O ( N + r a n g e ) 空间复杂度:O ( r a n g e ) 。

四、计数排序应用场景

计数排序只适用于数据范围较集中的序列的排序,若待排序列的数据较分散,则会造成空间浪费,并且计数排序只适用于整型排序,不适用与浮点型排序。

相关文章