2013.01.06
第2章 经典入门
一 排序
| 例2.1 | 排序 | （九度教程第1题） |
|---|---|---|
| 时间限制：1秒 | **内存限制：32兆 ** | 特殊判题：否 |
题目描述：对输入的n个数进行排序并输出。
输入：输入的第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
输出：可能有多组测试数据，对于每组数据，将排序后的n个整数输出，每个数后面都有一个空格。每组测试数据的结果占一行。
样例输入：
4
1 4 3 2
样例输出：
1 2 3 4
来源：
2006年华中科技大学计算机保研机试真题
代码 2.1C
#include <stdio.h>
int main () {
int n;
int buf[100]; //定义我们将要使用的变量n，并用buf[100]来保存将要排序的数字
while (scanf ("%d",&n) != EOF) { //输入n,并实现多组数据的输入
//该循环判断条件既保证了可以对多组测试数据进行计算，同时又使程序在输入结束后能够正常的退出。
for (int i = 0;i < n;i ++) {
scanf ("%d",&buf[i]);
} //输入待排序数字
for (int i = 0;i < n;i ++) {
for (int j = 0;j < n - 1 - i;j ++) {
if (buf[j] > buf[j + 1]) {
int tmp = buf[j];
buf[j] = buf[j + 1];
buf[j + 1] = tmp;
}
}
} //冒泡排序主体
for (int i = 0;i < n;i ++) {
printf("%d ",buf[i]);
} //输出完成排序后的数字,注意,题面输出要求在每个数字后都添加一个空格
printf("\n"); //输出换行
}
return 0;
}
代码2.2C++
#include <stdio.h>
#include <algorithm>
using namespace std;
int main () {
int n;
int buf[10000];
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%d",&buf[i]);
}
sort (buf,buf + n); //使用该重载形式,表明将要使用自己定义的排列规则
//sort(起始地址，结束地址)已经通过快速排序升序排列
for (int i = 0;i < n;i ++) {
printf("%d ",buf[i]);
}
printf("\n");
}
return 0;
}
代码 2.3 降序C++
#include <stdio.h>
#include <algorithm>
using namespace std;
bool cmp (int x,int y) { //定义排序规则
return x > y;
}
int main () {
int n;
int buf[100];
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%d",&buf[i]);
}
sort (buf,buf + n,cmp); //使用该重载形式,我们表明将要使用自己定义的排列规则
//sort（排序起始地址，排序结束地址，比较函数）
for (int i = 0;i < n;i ++) {
printf("%d ",buf[i]);
}
printf("\n");
}
return 0;
}
| 例2.2 | 成绩排序 | （九度教程第2题） |
|---|---|---|
| 时间限制：1秒 | **内存限制：32兆 ** | 特殊判题：否 |
**题目描述： **有 N 个学生的数据，将学生数据按成绩高低排序，如果成绩相同则按姓名 字符的字母序排序，如果姓名的字母序也相同则按照学生的年龄排序，并输出 N 个学生排序后的信息。
**输入： **测试数据有多组，每组输入第一行有一个整数 N（N<=1000），接下来的 N 行包括 N 个学生的数据。每个学生的数据包括姓名（长度不超过 100 的字符串） 、 年龄（整形数）、成绩（小于等于 100 的正数）。
**输出： **将学生信息按成绩进行排序，成绩相同的则按姓名的字母序进行排序。然后 输出学生信息，按照如下格式：姓名 年龄 成绩
样例输入：
3
abc 20 99
bcd 19 97
bed 20 97
样例输出：
bcd 19 97
bed 20 97
abc 20 99
**提示： **
学生姓名的字母序区分字母的大小写，如 A 要比 a 的字母序靠前(因为 A 的
ASC 码比 a 的 ASC 码要小)。
**来源： **
2000 年清华大学计算机研究生机试真题
代码 2.4
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct E {
char name[101];
int age;
int score;
}buf[1000];
bool cmp(E a,E b) { //实现比较规则
if (a.score != b.score) return a.score < b.score; //若分数不相同则分数低者在前
int tmp = strcmp(a.name,b.name);
if (tmp != 0) return tmp < 0; //若分数相同则名字字典序小者在前
else return a.age < b.age; //若名字也相同则年龄小者在前
} //分数>名字>年龄
int main () {
int n;
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%s%d%d",buf[i].name,&buf[i].age,&buf[i].score);
} // 输入
sort(buf,buf + n,cmp); //利用自己定义的规则对数组进行排序
for (int i = 0;i < n;i ++) {
printf ("%s %d %d\n",buf[i].name,buf[i].age,buf[i].score);
} //输出排序后结果
}
return 0;
}
代码2.5直接定义该结构体的小于运算符来说 明排序规则。
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct E {
char name[101];
int age;
int score;
bool operator < (const E &b) const { //利用C++算符重载直接定义小于运算符
if (score != b.score) return score < b.score;
int tmp = strcmp(name,b.name)
if (tmp != 0) return tmp < 0;
else return age < b.age;
}
}buf[1000];
int main () {
int n;
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%s%d%d",buf[i].name,&buf[i].age,&buf[i].score);
}
sort(buf,buf + n);
for (int i = 0;i < n;i ++) {
printf ("%s %d %d\n",buf[i].name,buf[i].age,buf[i].score);
}
}
return 0;
}
练习题：特殊排序（九度教程第 3 题）；EXCEL 排序（九度教程第 4 题）；字符 串内排序（九度教程第 5 题）；
| 题目1023 | EXCEL 排序 | （九度教程第4题） |
|---|---|---|
| 时间限制：1秒 | **内存限制：32兆 ** | 特殊判题：否 |
题目描述：
Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。
对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。
输入：
测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (N<=100000) 和 C，其中 N 是纪录的条数，C 是指定排序的列号。以下有N行，每行包含一条学生纪录。每条学生纪录由学号（6位数字，同组测试中没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（闭区间[0, 100]内的整数）组成，每个项目间用1个空格隔开。当读到 N=0 时，全部输入结束，相应的结果不要输出。
输出：
对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。
样例输入：
3 1
000007 James 85
000010 Amy 90
000001 Zoe 60
4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98
4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90
0 0
样例输出：
Case 1:
000001 Zoe 60
000007 James 85
000010 Amy 90
Case 2:
000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60
Case 3:
000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90
来源：
2007年浙江大学计算机及软件工程研究生机试真题
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct E {
char ID[10];
char name[10];
int score;
}buf[100001];
bool case1(E a, E b) {
int tmp = strcmp(a.ID,b.ID);
if (tmp != 0) return tmp< 0;
}
bool case2(E a, E b) {
int tmp = strcmp(a.name,b.name);
if (tmp !=0) return tmp<0;
tmp = strcmp(a.ID,b.ID);
if (tmp != 0) return tmp< 0;
}
bool case3(E a, E b) {
if (a.score != b. score) return a.score < b.score;
int tmp = strcmp(a.ID,b.ID);
if (tmp != 0) return tmp< 0;
}
int main() {
int a,b,k=1;//错在case 1 2 3 4递增
while (scanf("%d%d",&a,&b),a){
for(int i = 0; i < a; i++){
scanf("%s %s %d",&buf[i].ID,&buf[i].name,&buf[i].score);
}
if(b==1)sort(buf,buf+a,case1);
if(b==2)sort(buf,buf+a,case2);
if(b==3)sort(buf,buf+a,case3);
printf("Case %d:\n",k++);//错在case 1 2 3 4递增
for(int i = 0; i < a; i++){
printf("%s %s %d\n",buf[i].ID,buf[i].name,buf[i].score);
}
}
return 0;
}
| 题目1054 | 字符串内排序 | （九度教程第5题） |
|---|---|---|
| 时间限制：1秒 | **内存限制：32兆 ** | 特殊判题：否 |
题目描述：
输入一个字符串，长度小于等于200，然后将输出按字符顺序升序排序后的字符串。
输入：
测试数据有多组，输入字符串。
输出：
对于每组输入,输出处理后的结果。
样例输入：
bacd
样例输出：
abcd
来源：
2010年哈尔滨工业大学计算机研究生机试真题
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int main(){
char a[200];
while(scanf("%s",&a) != EOF){
int n = strlen(a);
sort(a,a+n);
for( int i = 0; i < n; i++){
printf("%c",a[i]);
}
printf("\n");
}
return 0;
}
