数据结构基

一、介绍：

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。

操作步骤：

1）统计相同元素出现次数

2）根据统计的结果将序列回收到原来的序列中

为了避免浪费空间，把数组中最大值与最小值相减然后+1

二、代码：

我直接开讲计数排序的核心内容，前面代码有注释，大家自己看一下

void CountSort(int* arr, int size)
{
	// 初始化最大值为数组的最后一个元素，最小值为数组的第一个元素
	int max = arr[size], min = arr[0];

	// 遍历数组以找到实际的最大值和最小值
	for (int i = 0; i < size; i++)
	{
		if (arr[i] > max) // 如果当前元素比当前的最大值大，更新最大值
		{
			max = arr[i];
		}
		if (arr[i] < min) // 如果当前元素比当前的最小值小，更新最小值
		{
			min = arr[i];
		}
	}

	// 计算数组中元素的范围 (最大值 - 最小值 + 1)
	int range = max - min + 1;

	// 分配一个数组 tmp 来存储元素的计数，大小为 `size`，元素初始化为 0
	int* tmp = (int*)calloc(size, sizeof(int) * size);

	// 检查内存是否分配成功，如果失败则输出错误并退出程序
	if (tmp == NULL)
	{
		perror("calloc error!");
		exit(1);
	}

	// 初始化索引变量，用于在排序后重新填充原数组
	int index = 0;

	for (int i = 0; i < size; i++)
	{
		tmp[arr[i] - min]++;
	}
	for (int i = 0; i < range; i++)
	{
		while (tmp[i]--)
		{
			arr[index++] = i + min;
		}
	}
}

三、统计每个数字出现的次数

for (int i = 0; i < size; i++)
{
    tmp[arr[i] - min]++;
}

在上面代码中，我将会直接讲述代码中最后两个循环是什么意思

这段代码的作用是 统计每个数字出现的次数。具体解释如下：

1. tmp 是一个用于计数的数组。tmp[arr[i] - min]++ 的意思是找到当前数字 arr[i] 在计数数组 tmp 中的位置。
2. arr[i] - min 是因为 arr 中的最小值不一定是0。通过减去 min，将范围变成从 0 开始。例如，如果最小值是 5，而当前数字是 7，那么 7 - 5 = 2。所以我们在 tmp[2] 中加1，表示数字 7 出现了一次。
3. 这段循环结束后，tmp 中的每个位置存的就是对应的数字出现的次数。

四、统计好的次数将数字填回原数组

for (int i = 0; i < range; i++)
{
    while (tmp[i]--)
    {
        arr[index++] = i + min;
    }
}

这段代码是 按照统计好的次数将数字填回原数组。具体步骤如下：

1. 遍历 tmp 数组，i 代表当前数值在计数数组中的位置。
2. while (tmp[i]--) 是一个循环，每次循环将 i + min 放入原数组 arr 中，这样可以还原出原始值。
3. index 用于追踪当前在 arr 中写入的位置。每写入一个数，index 向后移动一格。
4. 如果某个数字出现了多次，tmp[i] 就会大于 1，这个 while 循环会执行多次，把这个数字放入 arr 多次。

五、举例：

假设有数组 [5, 7, 5, 6]，让我们一步步看看会发生什么：

1. 找到最大值和最小值：最大值是 7，最小值是 5。

2. 创建计数数组 tmp，长度是 3（max - min + 1），初始为 [0, 0, 0]。

3. 统计次数：

   • 对于第一个 5，tmp[5 - 5]++，即 tmp[0]++，tmp 变成 [1, 0, 0]。
   • 对于 7，tmp[7 - 5]++，即 tmp[2]++，tmp 变成 [1, 0, 1]。
   • 对于第二个 5，tmp[0]++，tmp 变成 [2, 0, 1]。
   • 对于 6，tmp[6 - 5]++，即 tmp[1]++，tmp 变成 [2, 1, 1]。

4. 根据 tmp 填回原数组：

   • tmp[0] = 2，表示 5 出现两次，因此填入两个 5。
   • tmp[1] = 1，表示 6 出现一次，因此填入一个 6。
   • tmp[2] = 1，表示 7 出现一次，因此填入一个 7。
   • 最终 arr 变成 [5, 5, 6, 7]。

初始数组：

arr = [5,7,5,6]

计数统计结果（tmp）：
tmp = [2,1,1]  // 代表5出现两次，6出现一次，7出现一次

将结果写入 arr 中：
arr = [5,5,6,7]

这样最终的数组就是排好序的结果 [5,5,6,7]。