UVa 11462 年龄排序 (计数排序及IO优化) - c++编程基础

题意：给定若干个居民的年龄（都是1-100之间的整数），把它们按照从小到大的顺序输出。

输入第一行为整数n（0

思路：数据太大，内存限制太紧，连把数据全读进内存都不行，所以什么快排之类的排序报废了，但是注意到这里整数范围很小，可以用计数排序。

#include  
#include  
int main()  
{  
    int n,x,c[101],i,j;  
    while(scanf("%d",&n)==1&&n)  
    {  
        memset(c,0,sizeof(c));  
        for(i=0;i

计数排序是一个O(N)的排序，非常适合这道题目。运行0.479s

考虑到这道题的I/O操作量大，成为了这道题的瓶颈，如果能够针对I/O进行优化，会使进一步降低运行时间。

我们知道当数据量大时，不要用cin，cout，而使用scanf，printf，因为cin，cout的无类型输入输出是很爽，但是你需要付出相应

的时间作为代价，它们函数内部还是要匹配一遍类型，很多事物都是这样，你有得，必有失，看你怎么取决而已。

如果使用scanf和printf效率还不够，就要考虑逐字符输入输出。

优化IO程序：

#include  
#include  
#include  
inline int readint()  
{  
    char c=getchar();  
    while(!isdigit(c)) c=getchar();  
    int x=0;  
    while(isdigit(c))  
    {  
        x=x*10+c-'0';  
        c=getchar();  
    }  
    return x;  
}  
int buf[10];//声明全局变量减小开销，因为全局的空间程序运行就分配好，如果作为局部变量，每次调用都要分配空间(这个函数会被大量调用用于输出结果)  
inline void writeint(int i)  
{  
    int p=0;  
    if(i==0) p++;//特殊处理i=0的情况  
    else while(i)  
    {  
        buf[p++]=i%10;  
        i/=10;  
    }  
    for(int j=p-1;j>=0;j--)  
        putchar('0'+buf[j]);  
}  
int main()  
{  
    int n,c[101],i,j;  
    while(n=readint())  
    {  
        memset(c,0,sizeof(c));  
        for(i=0;i

运行时间：0.172m，比单纯计数排序的0.479优化了2/3左右。当数据量变得更大，能优化2/3什么概念，你懂的。