排序算法练习1.pdfVIP

排序算法的应用

1．基本题

从键盘读入n，随机产生1-999之间的整数，用排序算法将这n个数从小到大排序并

输出。要求如下：

（1）用快速排序算法，输出排序的结果，要求输出每趟快速排序的结果。

（2）用基数排序算法，输出排序的结果，要求输出每趟搜集的排序结果。

2．纪念品分组

【题目描述】

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学

所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包

括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的

时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

【输入】

输入文件group.in包含n+2行：

第1行包括一个整数w，为每组纪念品价格之和的上限。

第2行为一个整数n，表示购来的纪念品的总件数。

第3~n+2行每行包含一个正整数p(5=p=w)，表示所对应纪念品的价格。

ii

【输出】

输出文件group.out仅一行，包含一个整数，即最少的分组数目。

【输入输出样例】

group.ingroup.out

1006

9

90

20

20

30

50

60

70

80

90

【限制】

50%的数据满足：1=n=15

100%的数据满足：1=n=30000,80=w=200

3．明明的随机数

【问题描述】

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生

成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其

余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照

排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

【输入文件】

输入文件random.in有2行，第1行为1个正整数，表示所生成的随机数的个数：

N

第2行有N个用空格隔开的正整数，为所产生的随机数。

【输出文件】

输出文件random.out也是2行，第1行为1个正整数M，表示不相同的随机数的个数。

第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

【输入样例】

10

2040326740208930040015

【输出样例】

8

152032406789300400

4．奖学金

【问题描述】

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学

金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果

两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那

么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输

出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你

必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两

个数：学号、总分）是：

7279

5279

这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总

分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成

绩更高一些。如果你的前两名的输出数据是：

5279

7279

则按输出错误处理，不能得分。

【输入】

输入文件scholar.in包含n+1行：

第1行为一个正整数n，表示该校参加评选的学生人数。

第2到n+1行，每行有3个用空格隔开