C++简单排序——计数排序

计数排序的主要思想是：若待排序的数据元素的关键字在一个明显有限的范围内（整形）时可设计一个计数数组，记录每一个元素的个数，然后把数组中的原数按顺序输出。

题目：输入n（1≤n≤10^8）个 0~2000 之间的整数，从小到大排序输出。

题目分析：这道题是真的难，由于数据量太大，而每个数又有固定的小范围，并且是有序类型，我们要用时间复杂度为O(n)的排序方法：计数排序。

#include 
using namespace std;
int n,i,a[3000];	//这里把数组定大一点
int main()
{
    cin >>n;
    for (i=1;i<=n;i++)
    {
    	cin >>k;
    	a[k]++;		//将当前数对应数组位置累加（统计每个数的个数） 
	}
	for (i=1;i<=2000;i++)
		while (a[i])
		{
			cout < 
计数排序虽然耗时短，但有两个局限：
 
1、要排序的类型必须是有序类型（如整形），像浮点型这种无序数据类型则不能用计数排序。
 
2、要排序的数据必须有固定的小范围，否则就会数组太大爆内存。
 
下期预告：冒泡排序