Problem 11462 Age Sorts，累計排序

題目要求你記錄每一個人的年紀，最後要輸出它們的排序，而文中也順道規定它的數值範圍，「no individual in that country lives for 100 or more years.」，也就是說，年齡的範圍為：0 < y < 100。而排序的數量 n 的範圍為：0 < n <= 2000000。

如果還想用 bubleSort 排序那就是找吃 TLE，題目已經說明數值小、數量大，所以可以找到一種 Counting Sort (累計排序) 的方法來排序，老老實實用 Counting Sort 做它，約略會在 0.473 的時間上下。Counting Sort 就是假設我輸入 1 3 2 5 4，而我要有一個 100 索引的整數陣列 data，若每輸入一個整數 i，就將 data[i] ++;，最後陣列會變成 data[0] = 0、data[1] = 1、data[2] = 1、data[3] = 1、data[4] = 1、data[5] = 1、data[6] = 0、...、data[99] = 0。最後再用「類似」以下做法印出：

int isFirst = 0;
for (i = 1; i < 100; i ++)
    for (; data[i]; data[i] --)
        if (isFirst) printf(" %d", i);
        else printf("%d", i), isFirst = 1;

當我第一次這樣做完這一題，0.460 AC 後，覺得要再縮短時間，所以到論壇上看看有沒有別的方法，想不到也有人也想縮短時間的方法，結果 neilor 網友有一些對這一題做法的時間排序：
原網址連結
Método Execution time
bubleSort TLE (> 5 seconds)
Qsort Stl with cin / cout 1.072
Quicksort with scanf / printf 0.786 secs (maybe not so good qsort!?)
Mergesort with scanf / printf 0.656 secs (with a best mergesort)
qsort Stl [ sort(age,age + tam); ] 0.596 secs
Counting Sort (with vector) 0.473 secs (18 º world time)
Counting Sort (without vector) 0.456 secs
Counting Sort with fast input 0.343 seconds (13 º )
Counting Sort with fread/fwrite 0.204 seconds (10 º )
Counting Sort fread/fwrite optimized 0.156 (8º)
Counting Sort fread optimized /fwrite optimized 0.052 (2º) same that 1º mundial place.

最棒的方法是用優化輸入，和優化輸出 ( 這部分就要請大家去找這些方法的資料了，在此就不提供程式碼，如果想知道就再問我吧! )，能使時間降到 0.1 秒以下，最後我改用了最後一個做法，結果我最好的時間是 0.056 秒，目前排名第 4，但想不到 pcy 同學才花 0.036 秒，真太拜服了。

By David.K

p11462題目連結
回ACM題庫目錄
回首頁