【題目】

You are given the ages (in years) of all people of a country with at least 1 year of age. You know that no individual in that country lives for 100 or more years. Now, you are given a very simple task of sorting all the ages in ascending order.

Input

There are multiple test cases in the input file. Each case starts with an integer n (0<n<=2000000), the total number of people. In the next line, there are n integers indicating the ages. Input is terminated with a case where n = 0. This case should not be processed.

Output

For each case, print a line with n space separated integers. These integers are the ages of that country sorted in ascending order.

Warning: Input Data is pretty big (~ 25 MB) so use faster IO.

Sample Input Output for Sample Input

5

3 4 2 1 5

5

2 3 2 3 1

0

1 2 3 4 5

1 2 2 3 3

Note: The memory limit of this problem is 2 Megabyte Only.

Problem Setter: Mohammad Mahmudur Rahman

Special Thanks: Shahriar Manzoor

【分析】

由於數據太大，內存限制太緊（甚至都不能把它們全讀進內存），因此無法使用快速排序方法。但整數范圍很小，可以用計數排序方法。

【代碼】

/*********************************
*   日期：2014-5-2
*   作者：SJF0115
*   題號: 11462 - Age Sort
*   地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2457
*   來源：UVA
*   結果：Accepted
*   總結：計數排序
**********************************/
#include 
#include 
#include 
using namespace std;

int main(){
    int i,j,age,n;
    int count[101];
    //freopen("C:\\Users\\wt\\Desktop\\acm.txt","r",stdin);
    while(scanf("%d",&n)!= EOF && n != 0){
        //初始化
        memset(count,0,sizeof(count));
        //統計人數
        for(i = 0;i < n;i++){
            scanf("%d",&age);
            count[age]++;
        }
        //按照年齡從小到大輸出
        bool first = true;//標志 控制格式  第一次輸出
        for(i = 1;i < 101;i++){
            for(j = 0;j < count[i];j++){
                if(!first){
                    printf(" ");
                }
                first = false;
                printf("%d",i);
            }
        }
        printf("\n");
    }
    return 0;
}

如果還要精益求精，可以優化輸入輸出，進一步降低運行時間。程序如下。

/*********************************
*   日期：2014-5-2
*   作者：SJF0115
*   題號: 11462 - Age Sort
*   地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2457
*   來源：UVA
*   結果：Accepted
*   總結：
**********************************/
#include
#include
#include 	//為了使用isdigit宏
//內聯函數
//逐字符輸入
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;
    //特殊情況：i等於0的時候需要輸出0，而不是什麼也不輸出
    if(i == 0){
        p++;
    }
    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, x, c[101];
    while(n = ReadInt()){
        memset(c, 0, sizeof(c));
        for(int i = 0; i < n; i++) c[ReadInt()]++;
        //輸出
        int first = 1;
        for(int i = 1; i <= 100; i++){
            for(int j = 0; j < c[i]; j++) {
                if(!first) putchar(' ');
                first = 0;
                WriteInt(i);
            }
        }
        putchar('\n');
    }//while
    return 0;
}

上述優化使得運行時間縮短了約2/3。一般情況下，當輸入輸出數據量很大時，應盡量用scanf和printf函數；如果時間效率還不夠高，應逐字符輸入輸出，就像上面的readint和writeint函數。不管怎樣，在確信I/O時間成為整個程序性能瓶頸之前，不要盲目優化。測試方法也很簡單：輸入之後不執行主算法，直接輸出一個任意的結果，看看運行時間是否過長。