[数据结构]——非比较排序—计数排序

该篇文章 所涉及代码收录仓库：登录 - Gitee.com

1.非比较排序——计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

2.最终实现

1.解析

操作步骤： 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中

1. 找出最大和最小值: 首先遍历数组 a 一次，找到其中的最大值 max 和最小值 min。这一步是为了确定数组中的数值范围，从而决定后续计数数组 count 的大小。
2. 创建计数数组: 根据最大值和最小值计算出数值范围 range = max - min + 1，并用 calloc 动态分配一个大小为 range 的整型数组 count。计数数组的每个元素初始化为0，用于记录原数组中每个数值出现的次数。
3. 统计每个元素的出现次数: 再次遍历原数组 a，对于数组中的每个元素 a[i]，计算它与最小值的差值 a[i] - min，并将计数数组中对应索引的位置加1。这样做是因为我们希望 count[0] 存储的是原数组中小于等于 min 的元素数量，count[1] 存储的是原数组中等于 min+1 的元素数量，依此类推，从而避免了因为负数或零而导致的索引错误。
4. 重排元素: 遍历计数数组 count，对于 count[j] 非零的每个元素，将其对应的数值（即 j + min）放回原数组 a 中，同时减少 count[j] 的计数。这里的循环保证了数值会按照原来的顺序被放置回数组，从而维持了稳定性排序。

2.以int a[] = { 1,3,9,1,5,1,2,3,-5,-5,-2 };为例，手撕分析

3.代码实现

void CountSort(int* a, int n)
{//找出最大和最小元素
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;//确定新创建数组的数据个数和原数组大小相同，便于下面计数
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		printf("calloc fail\n");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;//min作为偏移量，然后再在对应数组位置++，统计该数字出现的次数
	}

	// 排序
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
}

4.计数排序具有以下主要特性：

1. 非比较排序算法：计数排序不通过元素间的直接比较来进行排序，而是通过计算元素的分布情况来确定它们的位置，这使得它在最好、最坏和平均情况下都有较好的性能表现。
2. 时间复杂度：计数排序的时间复杂度为O(n+k)，其中n是数组长度，k是数组中数据范围（最大值与最小值之差加一）。当k不是很大且远小于n时，计数排序非常高效。
3. 空间复杂度：计数排序需要额外的计数数组，其空间复杂度为O(k)，这使得它在处理大数据范围时可能比较消耗内存。
4. 稳定性：计数排序是一种稳定的排序算法。因为它在重新排列元素时能够保持相同值的元素原有的相对顺序不变。
5. 适用范围：最适合于整数或有限范围内的非负整数排序。对于浮点数或负数，虽然理论上可以通过调整使其适用，但实际上并不常见，因为这会增加算法的复杂性。
6. 局限性：计数排序的局限性主要体现在它对数据类型的限制上，不适合非整数类型的数据排序。此外，当数据范围非常大时，所需的额外空间也会非常大，这在资源受限的环境下可能是个问题。
7. 预处理要求：在执行排序前需要先遍历一遍数组以确定数据范围，这一步骤虽然简单，但也构成了算法的一部分开销。

综上，计数排序在特定场景下（如数据范围不大、整数类型）是一种快速且高效的排序选择，但其适用场景相对有限，且空间效率较低。