计数，基数排序

计数排序
计数排序是建立在这样的前提条件下的：假设n个输入元素的每一个都是0到k区间内的一个整数，其中k为某个整数。因此我们后面所写的程序也只是针对0到k之间的元素进行排序，
换句话说，排序元素中不能有负数。
基本思想：
对一个输入元素x，先确定所有输入元素中小于x的元素个数，那么排序后x所在的位置也就明确了。比如，所有的输入元素中有10个元素小于x，那么排好序后x的位置序号就应该是11。
当然，如果有相同元素，自然要放到相邻的位置上。

/* 
第一种形式实现计数排序 
计数排序后的顺序为从小到大 
arr[0...len-1]为待排数组，每个元素均是0-k中的一个值 
brr[0...len-1]为排序后的输出数组 
crr[0...k]保存0...k中每个值在数组arr中出现的次数 
*/ 
void count_sort(int *arr,int *brr,int *crr,int len,int k)
{
	int i,j=0;
	for(i=0;i<=k;i++)
		crr[i]=0;
	 //统计数组arr中每个元素重复出现的个数
	 for(i=0;i<len;i++)
		crr[arr[i]]++;
	//求数组arr中小于等于i的元素个数  
	for(i=1;i<=k;i++)
		crr[i]+=crr[i-1];
	//把arr的元素放到brr 对应的位置
	for(i=len-1;i>=0;i--)
	{
		brr[crr[arr[i]]-1]=arr[i];
		
		crr[arr[i]]--;
	}
}
/*
第二种形式实现计数排序 
计数排序后的顺序为从小到大 
arr[0...len-1]为待排数组，每个元素均是0-k中的一个值 
crr[0...k]保存0...k中每个值在数组arr中出现的次数 
*/ 

void count_sort(int *arr,int *crr,int len,int k)
{

	int i,j=0;
	for(i=0;i<=k;i++)
		crr[i]=0;
	for(i=0;i<len;i++)
		crr[arr[i]]++;
	
	for(i=0;i<=k;i++)
		while((crr[i]--)>0)
		{
			arr[j++]=i;
		}
}

1、不是基于比较的排序，因此可以达到线性排序时间；
2、采取空间换时间的思想，需要brr和crr等辅助空间，但是时间复杂度仅为O（n+k）；
3、稳定性好，这也是计数排序最重要的一个特性。
基数排序;
基数排序采取的是多关键字比较的策略，且每个关键字对排序的影响不同，根据关键字影响的主次，有两种排序方法：

1、先根据影响最大的关键字来排序，而后在该关键字相同的情况下，再根据影响次之的关键字来排序，依此类推，直到最后按照影响最小的关键字排序后，序列有序。我们称这个为先高位后低位。

2、先根据影响最小的关键字来排序，而后再对全部的元素根据影响次小的关键字来排序，依此类推，直到最后按照影响最大的关键字排序后，序列有序。我们称这个为先低位后高位。

/* 
在第一种计数排序的实现形式上做了些修改 
计数排序后的顺序为从小到大 
arr[0...len-1]为待排数组，我们这里采用三位数 
brr[0...len-1]为排序后的有序数组 
w[0...len-1]用来保存取出的每一位上的数，其每个元素均是0-k中的一个值 
crr[0...k]保存0...k中每个值出现的次数 
*/  
void count_sort(int *arr,int *brr,int *w,int *crr,int len,int k)
{
	int i;
	for(i=0;i<=k;i++)
		crr[i]=0;
	 //统计数组w中每个元素重复出现的个数 
	 for(i=0;i<len;i++)
		crr[w[i]]++;
	//求数组w中小于等于i的元素个数
	for(i=1;i<=k;i++)
		crr[i]+=crr[i-1];
	//把arr中的元素放在brr 中对应的位置上
	
	for(i=len-1;i>=0;i--)
	{
		brr[crr[w[i]]-1]=arr[i];
		//如果有相同的元素则放到下一位置
		crr[w[i]]--;
	}
	
	//再将brr的元素复制给arr
	for(i=0;i<len;i++)
		arr[i]=brr[i];
}
/*基数排序*/
void basic_sort(int *arr,int *brr,int *w,int *crr,int len,int k,int d)
{
	int i,j,val=1;
	//从低位到高位依次进行计数排序
	for(i=1;i<=d;i++)
	{
		//w中保存的是arr中每个元素对应位上的数  
        //范围在0-k之间 
		for(j=0;j<len;j++)
			w[j]=(arr[j]/val)%10;
		//对当前位进行计数排序
		count_sort(arr,brr,w,crr,len,k);
		val*=10；
	}

}

1、同样不是基于比较的排序，因此可以达到线性排序时间；

2、同样采取空间换时间的思想，需要额外的辅助空间，但是时间复杂度仅为O（d(n+k)）；

3、基数排序的稳定性同样也很好。