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;
}