计数排序法

计数排序的核心在于将输入数据转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

当输入的元素是n个0到k之间的整数时，它的运行时间复杂度是O(n+k)。计数排序不是比较排序，它的速度快于任何比较排序的算法。由于用来计数的数组A的长度取决于待排数组中数据的范围（最大值-最小值+1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

算法步骤如下：

1. 找到待排序数组中最大值和最小值；
2. 开辟数组A，空间大小=最大值-最小值+1；
3. 待排数组中每个元素减去最小值作为数组A索引，并统计其出现次数；
4. 遍历数组A，填充目标数组。

void CountSort(int* arr, int size)
{
	int min = arr[0];
	int max = arr[0];
	for (int i = 0; i < size; i++) {
		if (arr[i] < min) {
			min = arr[i];
		}
		if (arr[i] > max) {
			max = arr[i];
		}
	}
 
	int range = max - min + 1;
	int j = 0;
	int* arr_map = (int*)malloc(sizeof(int) * range);
	memset(arr_map, 0, sizeof(int) * range);
	for (int i = 0; i < size; i++) {
		arr_map[arr[i] - min] += 1;
	}
	for (int i = 0; i < max - min + 1; i++) {
		while (arr_map[i]) {
			arr[j] = i + min;
			j++;
			arr_map[i] --;
		}
	}
	free(arr_map);
}