计数排序.cpp

常见算法

#include<iostream>
using std::cout;
using std::cin;
using std::endl;
#define K 7                           //设数组中的每一个元素都不大于6，定义N是为了确定计数器数组
                                      //counter[]的长度。


void countings_sort(int x[],int y[])
{
	int i,leng;
	int counter[K];                     //牺牲了一个存储区counter[0]。
    leng=10;
	for(i=0;i<K;i++)
		counter[i]=0;
	for(i=0;i<leng;i++)
	{
		counter[x[i]]=counter[x[i]]+1;      //统计每一相等数的个数
	}
	for(i=1;i<K;i++)
	{
		counter[i]+=counter[i-1];           //统计小于等于i的个数
	}
    for(i=leng-1;i>=0;i--)
	{
       y[--counter[x[i]]]=x[i];             //数据放入之前序号减一，也即计数器减一。
	}

}

main()
{
	int c[10]={3,4,3,4,5,4,6,5,2,1};        
	int i;                       
	int b[10]={0};                                   
	cout<<"排序前数组是："<<endl;
    for(i=0;i<10;i++)
	{
		cout<<c[i]<<"  ";
	}
	
	countings_sort(c,b);
	cout<<endl<<"排序后的数组是："<<endl;
	for(i=0;i<10;i++)
		cout<<b[i]<<"  ";
	cout<<endl;
	return 0;
}
//疑问：如果数组中有若干个小于0的数，而且小的很多，那这个算法还实用吗？