【八大排序(九)】计数排序-非比较排序法-Toy模板网

这篇具有很好参考价值的文章主要介绍了【八大排序(九)】计数排序-非比较排序法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

💓博主CSDN主页:杭电码农-NEO💓

⏩专栏分类:八大排序专栏⏪

🚚代码仓库:NEO的学习日记🚚

🌹关注我🫵带你学习排序知识
🔝🔝

【八大排序(九)】计数排序-非比较排序法

1. 前言

我们已经学过的:
插入排序,希尔排序,选择排序,堆排序
快速排序等等都是比较排序
也就是需要通过数据的比较来进行排序

而这里的计数排序比较特殊
它用的是一一对应的映射关系
它不用比较数据就能排好序

【八大排序(九)】计数排序-非比较排序法

本篇文章分享的是:
计数排序思路以及代码全解

2. 计数排序基本思路

基本思路:

找出数组中的最大值和最小值
动态开辟一个空间
元素个数为最大值-最小值+1
再统计数据出现的次数

先定义一个无序数组:

int a[]={2,5,3,0,2,3,0,3};

此情况的分析:

数组最大值为5,最小值为0
开辟6个空间,统计数据出现的次数
开辟的数组中:
第一个元素对应的是最小值0的个数
最后一个元素对应的是最大值5的个数
中间的1,2,3,4不管原数组有没有都写上
统计完后重新导入原数组

画图理解:

【八大排序(九)】计数排序-非比较排序法

3. 特殊情况分析

特殊情况:最小值为0

上面举例说明中,最小值是0.
所以开辟的数组中:
下标为0的位置对应数据0的个数
下标为5的位置对应数据5的个数

当最小值不为0时:

假设我们再定义一个数组:

int a[]={1000,1200,1001,1500,1300,1301};

最大值为1500,最小值为1000
开辟一个长度为1500-1000+1=501的数组
(注意:长度为501的数组下标范围为0~500)
我们把开辟的数组称为数组b
此时b下标为0的点对应数据1000
b下标为501的点对应数据1500的个数

以此我们得出一个结论:

待排序数组中的元素X
映射到数组b的X-min的位置

画图理解:

【八大排序(九)】计数排序-非比较排序法

4. 计数排序代码实现

我们分步骤来实现:

1. 函数参数以及返回值:

//计数排序
void CountSort(int* a, int n)
{
	//...
}

2. 找最值:

	int max = a[0];
	int min = a[0];
	//找最值
	for (int i = 1; i < n; i++)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;//动态开辟数组的元素个数
	int* count = (int*)calloc(range, sizeof(int));//将元素初始化为0

2. 计数:

//计数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
		//计数是去原数组中计数
	    //所以循环次数是n
	}

3. 根据次数进行排序:

	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)//只要count数组中元素不为0就赋值到原数组
		{
			a[j++] = i + min;
		}
	}
	free(count);//用完后释放空间
	count = NULL;