#K050602. 商品排序
商品排序
说明
某商场的仓库中有 n 件商品,每件商品的价格在 0~1000 之间(价格为 0 的商品为赠品)。
现在商场经理要求将这 n 件商品按价格由低到高排序。请编程输出 n 件商品排序后的情况。
输入格式
第一行一个正整数 n,表示有 n 件商品,1≤n≤2000000
。
接下来的 n 行,每行一个整数,表示第 i 件商品的价格。
输出格式
n 行,每行输出一个整数。
样例
5
1
8
1
2
2
1
1
2
2
8
提示
本题可以选用学过的任意一种排序算法实现,但是测试程序发现会“超时”,因为本题最多有 100000 件商品,三种排序都需要两层循环嵌套。
其实,分析数据发现一个重要特征:数据虽然很多,但是数据范围比较小。这种情况下,可以使用另外一种排序算法——桶排序。定义一个 int 型数组 num[1001],num[x]记录整数 x 出现的次数,初始化都为 0,每读到一个数 x,就执行 num[x] = num[x]+1。输出时,从 0 ~ 1000 穷举 x,每个 x 输出 num[x]次。