如果已知被排序的n个元素，值范围固定在在 "[0,k)"内]，那么计数排序是最好的选择，它具有线性复杂度。

这个约束有些过强，有些时候，可以将不满足这个条件的转化一下：
比如 [-k, k)映射]到[0, 2k)等]。
再比如1/p的小树映射到p k-p等等。

下面上算法，主要走两遍：
首先建立k个桶
(1)扫描n个元素，增加对应桶中的计数
(2)从小到大扫描k个桶，计数非零则减一，然后顺序、依次输出。

源代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void countingSort(int* arr, int n, int k)
{
	int i, idx;
	int* buckets = NULL;
	//Allocate Buckets
	buckets = (int*)malloc(sizeof(int)*k);
	if(!buckets)
	{
		return ;
	}
	memset(buckets, 0, sizeof(int)*k);

	//Step1: Scan arr and put into bucket
	for(i=0; i<n; i++)
	{
		buckets[arr[i]]++;
	}

	//Step2: Using buckets to sort
	idx = 0;
	for(i=0; i<k; i++)
	{
		while(buckets[i]--)
		{
			arr[idx++] = i;
		}
	}
}

int main()
{
	int array[10] = {5,4,3,2,1,10,20,30,0,8};
	int i;
	int n;
	n = sizeof(array) / sizeof(int);
	countingSort(array, n, 100);
	for(i=0; i<n; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}