计数排序假设n个输入元素中的每一个都是介于0到k之间的整数，此处k为某个整数。当k=O(n)时，计数排序的运行时间为O(n)。线性复杂度。计数排序不是比较排序算法。稳定算法。

算法思想：对每一个输入元素x，确定出小于x的元素个数。有这个信息后，就可以把x直接放到它在最终输出数组的位置上。
假定输入数组A[1..n]，length[A]=n，则存放排序结果的数组B[1..n]，临时存储区C[0..k]。

/********************************/
/**********计数排序**************/
/********************************/
void CountSort(ElemType a[],ElemType b[],int k,int n)
{
	ElemType* c = (ElemType*)malloc(k*sizeof(ElemType));
	for(int j = 0;j < k;j++)
		c[j] = 0;
	int i;
	for(i = 0;i < n;i ++)
		c[a[i]] = c[a[i]]+1;//C[i]包含等于i的个数
	for(i = 1;i < k;i++)
		c[i] = c[i] + c[i-1];//C[i]包含小于或等于i的元素个数  
	for(i = n-1;i >= 0;i--)
	{
		b[c[a[i]]-1] = a[i];
		c[a[i]]--;
	}
}

#--------------#
#--Count sort--#
#--------------#
def count_sort(arr,brr,k):
	arrlen = len(arr)
	crr = []
	for i in range(0,k):
		crr.append(0) 		
	for j in range(0,arrlen):
		crr[arr[j]] = crr[arr[j]] + 1
	for i in range(1,k):		
		crr[i] = crr[i] + crr[i-1]
	for i in reversed(range(0,arrlen)):
		brr[crr[arr[i]]-1] = arr[i]
		crr[arr[i]] -= 1