计数排序

计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数。排序的时间复杂度为O(n)。

计数排序只能用于自然数序列，且序列的最大值比序列的个数小，或者比序列的个数略大。换句话说，计数排序使用与那些分布比较密集的自然数序列，如果满足这个条件，计数排序的效率是很高的，比比较类排序算法都要好。

计数排序的基本思想是：对于每一个输入元素x，计算出小于等于x的元素的个数。x的位置就可以直接确定了。方法是用一个数组存放输入序列中每一个元素出现的次数，然后累加起来就可以了。

实现代码：

void countingSort(int *A, int n, int k)
{
	int *B = new int[n];	//临时存放排序好的数组
	int *C = new int[k + 1]();

	for (int i = 0; i < n; i++)
	{
		C[A[i]]++;
	}
	//现在C[i]存放元素i出现的次数

	for (int i = 1; i <= k; i++)
	{
		C[i] += C[i - 1];
	}
	//现在C[i]等于小于等于i的元素的个数

	for (int i = 0; i < n; i++)
	{
		B[C[A[i]] - 1] = A[i];
		C[A[i]]--;	//下一个等于A[i]的元素将被放到前一个位置上
	}

	std::copy(B, B + n, A);

	delete[] B;
	delete[] C;
}