学步园

计数排序是一种线性时间排序方法，在以下条件满足时对n个数的数组A[]进行排序，其时间为O(n)：

一：数组A[]中的元素的大小均小于k

二：k=O(n)

算法代码如下：

#include <stdio.h>
#include <stdlib.h>
/**
 * 计数排序
 * a[] (input)要排序的数组
 * b[] (output) 排序结果
 * n	(input) 排序的数字的个数
 * k	(input)对所有的i满足：a[i]<k
 */
void count_sort(int a[],int b[],int n,int k)
{
	int i = 0;
	int* c = (int*)malloc(sizeof(int)*k);
	//初始化
	for(i = 0 ; i < k; i++)
	{
		*(c+i) = 0;
	}

	//计算各个元素的个数
	for( i = 0; i < n; i++)
	{
		(*(c+a[i]))++;
	}
	for(i = 1; i < k; i++)
	{
	    *(c+i) += *(c+i-1);
	}
	//输出
	for(i = n-1; i >= 0; i--)
	{
		b[*(c+a[i])-1] = a[i];
		(*(c+a[i]))--;
	} 
	free(c);
}


int main()
{
	int i;
	int a[] = {3,4,4,5,3,3,2,4,12,6,8};
	int length = sizeof(a)/sizeof(a[0]);
	int* b = (int*)malloc(sizeof(int)*length);
	count_sort(a,b,length,47);
	for(i = 0; i < length; i++)
		printf("%d\t",b[i]);	

}