计数排序

/*
#	
	优点：稳定	当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。
	计数排序不是比较排序，排序的速度快于任何比较排序算法。
	计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。

	缺点：需要知道数据大小的范围scale
#
*/


#include<iostream>
using namespace std;


void Sort2(int *a,int len, int scale){

	int *c=new int[scale+1];

	for(int i=0;i<scale+1;i++)
		c[i]=0;

  	for(int j=0;j<len;j++)
		c[a[j]]++;

	int z=0;

	for(j=0;j<=scale;j++){
		while(c[j]>0){
			a[z++]=j;
			c[j]--;
		}
	}
}
int main(){

	int a[10]={0,3,3,5,50,1,4,3,0,9};

	Sort2(a,sizeof a/sizeof a[0],50);

	for(int i=0;i<10;i++)
		cout<<a[i]<<" ";
	putchar(10);

	return 0;
}