计数排序

计数排序是一个基于非比较的排序算法。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)＞O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序、桶排序)。简单来说，就是其只能用于较集中的数据。

计数排序的具体过程如下：

然后根据 count 数组，将数据一个一个填入原数组中。

代码实现：

// 计数排序
void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];

	for (int i = 1; i < n; i++)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}

	//求出要开辟的数组的长度
	int range = max - min + 1;
	//使用calloc开辟并初始化count数组
	int* count = (int*)calloc(range, sizeof(int));

	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

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

	free(count);
	count = NULL;
}