计数排序

## 计数排序
![](/media/202205/CountSort_1653725984.gif)

**基本思想：**
计数排序，又叫非比较排序。顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中
作为一种线性时间复杂度的排序，计数排序要求`输入的数据必须是有确定范围的整数`

![](/media/202205/2022-05-28_161833_222892.png)

计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

**算法描述：**
1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

[wokwi_计数排序](https://wokwi.com/projects/332889636225417811)|[wokwi_计数排序](https://wokwi.com/projects/334327212314460754)

```c
// 计数排序,CountSort(数组名,数组长度,[排序方向,默认小到大])
void CountSort(int array[], int size, boolean forward = true){
	_CountSort(array,size);
	if (!forward){
		// 暂存数组,空间和排序数组一致
		int temp[size];
		// 把排序数组整个逆向存入暂存数组
		// size-1-i,数组长度(10)-1为最后位下标,-i就是从后往先递进
		for (int i = 0; i < size; i++) temp[i] = mylist[size-1-i];
		// 暂存数组复制到排序数组以完成逆向排序
		for (int i = 0; i < size; i++) mylist[i] = temp[i];
	}
}
//计数排序处理主函数,_CountSort(数组名,数组长度)
void _CountSort(int* array, int size){
	int min = array[0]; // 记录数组中的最小值
	int max = array[0]; // 记录数组中的最大值
	// 先找出最大/最小值
	for (int i = 0; i < size; i++){
		if (array[i] < min) min = array[i];
		if (array[i] > max) max = array[i];
	}
	// min和max之间的自然数个数(包括min和max本身)
	int range = max - min + 1;
	// 开辟可储存range个整型的内存空间,并将内存空间置0
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL) exit(-1);// 判断是否创建失败
	// 统计相同元素出现次数(相对映射)
	for (int i = 0; i < size; i++) count[array[i] - min]++;
	int i = 0;
	// 根据统计结果将序列回收到原来的序列中
	for (int j = 0; j < range; j++) while (count[j]--) array[i++] = j + min;
	// 释放空间
	free(count);
}
```