八大算法排序@计数排序(C语言版本)

发布时间:2024年01月03日

计数排序

概念

??计数排序(Counting Sort)是一种线性时间复杂度的排序算法,适用于排序一定范围内的整数数组。它利用了输入序列的数值范围来确定每个元素在输出序列中的位置。




算法思想

??主要思路是找出待排序数组的最大值和最小值,确认原数组的范围range,然后申请一有range个空间大小的数组并且数组内各个元素初始化为0,称之为计数数组。将原数组中的数映射到计数数组中,最终通过计数数组中的元素的数值,判断映射过来的数出现了多少次,以及原数组中的顺序情况。我们拿实现升序的计数排序来进行模拟演变。
如下,是初始状态图:

在这里插入图片描述

其中, arr1 = { 6 , 4 , 3 , 9 , 2 ,1 , 5 , 7 , 8 }是待排序的数组,变量maxi 和 mini 分别用来存放数组中最大的元素和最小的元素的下标。range是数组arr1的范围大小。



第一步:

第一步

找出原数组中的最大值和最小值的下标,通过下标算出原数组数据的范围range。再使用malloc函数,申请range个空间的计数数组retArr[range];



第二步:

通过迭代循环,将原数组一个个的映射到计数数组中,如下:

映射过程
需要注意的问题有:
1、偏移量的问题。映射关系要减去原数组的最小值,也是计数数组下标的问题。比如有个数组范围是10,但是最小值是100,最大值是109。比如数组中有个数105,要将它映射到计数数组中,直接将105映射到计数数组的话,那么计数数组就得开到有106个空间,这就造成了浪费。将105减去最小值100,这样映射到计数数组中的下标就是5,一样能够解决问题,这就避免了空间的浪费。

2、初始化问题。malloc动态申请的空间,没有初始化时数组内的各个元素都是随机值,而计数排序的关键就是对原数组中数据的大小、出现次数进行统计。所以对于申请开辟出来的计数数组中的初始值,我们要初始化好,一般都初始化为0,方便。也可以初始化为其他数,但是后面要消掉这个偏移量。

3、内存泄露问题。动态申请的空间,最后时得主动释放空间,要不然会造成内存泄露。

4、类型问题。计数排序只适用于整形数据的排序。字符类型要比较类型也不是不可以,但是要考虑ASCII码值的转换,比如字符 ‘1’ - 字符 ‘0’ 就等于整型数据1啦。但是像字符串、浮点型则不适用,因为字符串的比较大小的规则、浮点型的精确度问题,都不适用计数排序来排序。字符串和浮点型可以考虑使用其他的排序方法,如快速排序和归并排序等。



最后,我们得到了一个将原数组全部映射完到计数数组的,一个统计数组retArr。我们再通过计数数组retArr,复原出原数组,同时也就实现了对原数组的排序。
最终

以上,便是对计数排序的大体图文介绍,下面用文字表述以上思路。




算法步骤

确定范围: 找出待排序数组中的最大值和最小值,确定数值范围。
计数: ????创建一个辅助数组(计数数组),长度为数值范围的大小,用于统计原始数组中每个元素出现的次数。
累加计数: 对计数数组进行累加操作,使得每个位置上的值表示小于或等于该位置值的元素个数。
输出: ????根据原始数组的值在计数数组中找到对应的位置,将元素放置到输出数组中。


接下来,就用代码来实现吧。




代码实现

// 时间复杂度:O(N+range)
// 空间复杂度:O(range)
// 只适用于整形,如果是浮点数或者字符串排序,还得用比较排序
void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	// 找出原数组中的最大值和最小值
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)		max = a[i];
		if (a[i] < min)		min = a[i];
	}
	// 算出原数组的范围
	int range = max - min + 1;
	// 申请开辟range个大小的空间
	int* retArr = (int*)malloc(sizeof(int) * range);
	memset(retArr, 0, sizeof(int) * range);	// 注意,要对该空间初始化为0,才能对数组a进行计数!!!!,否则数组自身随机值会导致计数的失败

	// 判断申请空间是否成功
	if (retArr == NULL)
	{
		printf("空间扩容失败\r\n");
		exit(-1);
	}

	// 将原数组映射到计数数组中,进行统计
	for (int i = 0; i < n; i++)
	{
		retArr[a[i] - min] += 1;
	}

	// 通过计数数组复原原数组的元素,同时完成排序的效果
	int index = 0;
	for (int j = 0; j < range; j++)
	{
		while (retArr[j]--)
		{
			a[index++] = j + min;
		}
	}
	
	free(retArr);
}

以上便是计数排序的代码实现,具体可以看着代码一点点意会,此处不做多加讲解。需要注意的便是下标的迭代问题了。




时间复杂度

O(N+range),其中N是数组元素个数,range是辅助计数数组的范围。
当N>>range时,时间复杂度为O(N);
当range>>N时,时间复杂度为O(range);
当N和range相近时,时间复杂度为O(N)或O(range)。

注:“ >> ” 是远大于的意思
算计数排序时间复杂度的思想:
首先要遍历一遍原数组找出最大、最小值,需要N步;
其次需要将计数数组依次映射复原原数组,需要range步。至于比如说有的计数数组的元素值为3,那么该元素得迭代3次,对于常数次的动作,计算时间复杂度时不计入。



空间复杂度

O(range)

计数排序得向内存申请range个空间。所以空间复杂度为O(range)

注:“ range ” 是原数组的数值范围




特性总结

1、只适合整形数据的排序,字符、字符串或浮点型等都不适用。
2、时间复杂度:O(N+range)
3、空间复杂度:O(range)
4、稳定性:稳定

文章来源:https://blog.csdn.net/m0_72484344/article/details/135004379
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。