厦大C语言上机 1397 数据排序

盛夏的果实

　　1397.数据排序


时间限制: 1000 MS          内存限制: 65536 K
        
提交数: 1268 (0 users)          通过数: 116 (115 users)


问题描述
按一定顺序给n个学生数据“学号语文成绩 数学成绩 英语成绩 物理成绩 化学成绩 生物成绩”，现在让你按其中某一成绩从大到小排序（询问1按语文成绩排序，询问2按数学成绩排序，询问3按英语成绩排序，询问4按物理成绩排序，询问5按化学成绩排序，询问6按生物成绩排序），若成绩相同学号小的排在前面。输出排序后每个同学之前在原数据中的位置（如第一个读入数据的同学为1，最后一个读入数据的同学为N）。


输入格式
输入的第一行为一个整数N，代表有N个学生数据。（n<=1000）
接下来每一行一次输入学号、语文成绩、数学成绩、英语成绩、物理成绩、化学成绩、生物成绩，其中学号是一个十四位整数(该数值超过int类型表示的最大范围，请使用字符数组比较或者long long类型)，成绩是一个范围[0，100]的整数。
再一行输入一个询问整数K∈{1,2,3,4,5,6}，表示按第K种成绩排序，如题目所述。


输出格式
输出N行，代表排序后每个同学在原数据中所处的位置，即这个同学在原数据中是第几行。


样例输入
3
23020102203458 70 50 30 60 80 90
23020102203457 50 60 70 80 90 100
23020102203456 70 60 50 30 20 80
2


样例输出
3
2
1


来源
　　xmu

#include <stdio.h>
#include <string.h>
struct Student
{
  char id[20];
  int chinese;
  int math;
  int english;
  int physics;
  int chemistry;
  int biology;
  int index;
};
int cmp_chinese(struct Student a, struct Student b)
{
  return (a.chinese < b.chinese) || ((a.chinese == b.chinese) && (strcmp(a.id, b.id) > 0));
}
int cmp_math(struct Student a, struct Student b)
{
  return (a.math < b.math) || ((a.math == b.math) && (strcmp(a.id, b.id) > 0));
}
int cmp_english(struct Student a, struct Student b)
{
  return (a.english < b.english) || ((a.english == b.english) && (strcmp(a.id, b.id) > 0));
}
int cmp_physics(struct Student a, struct Student b)
{
  return (a.physics < b.physics) || ((a.physics == b.physics) && (strcmp(a.id, b.id) > 0));
}
int cmp_chemistry(struct Student a, struct Student b)
{
  return (a.chemistry < b.chemistry) || ((a.chemistry == b.chemistry) && (strcmp(a.id, b.id) > 0));
}
int cmp_biology(struct Student a, struct Student b)
{
  return (a.biology < b.biology) || ((a.biology == b.biology) && (strcmp(a.id, b.id) > 0));
}
int partition(struct Student *array, int low, int high, int (*cmp)(struct Student, struct Student))
{
  int mid = (low + high) / 2;
  array[0] = array[mid];
  array[mid] = array[low];
  while (low < high)
  {
    while (low < high && (*cmp)(array[high], array[0]))
      --high;
    array[low] = array[high];
    while (low < high && !(*cmp)(array[low], array[0]))
      ++low;
    array[high] = array[low];
  }
  array[low] = array[0];
  return low;
}
void quicksort(struct Student *array, int low, int high, int (*cmp)(struct Student, struct Student))
{
  if (low >= high)
    return;
  int pivot = partition(array, low, high, cmp);
  quicksort(array, low, pivot-1, cmp);
  quicksort(array, pivot+1, high, cmp);
}
int main()
{
  int n, k, i;
  struct Student stu[1005];
  int (*cmp)(struct Student, struct Student);
  scanf("%d", &n);
  for (i = 1; i <= n; ++i)
  {
    scanf("%s %d %d %d %d %d %d", stu[i].id, &stu[i].chinese, &stu[i].math, &stu[i].english, &stu[i].physics,
        &stu[i].chemistry, &stu[i].biology);
    stu[i].index = i;
  }
  scanf("%d", &k);
  switch (k)
  {
    case 1: cmp = cmp_chinese; break;
    case 2: cmp = cmp_math; break;
    case 3: cmp = cmp_english; break;
    case 4: cmp = cmp_physics; break;
    case 5: cmp = cmp_chemistry; break;
    case 6: cmp = cmp_biology; break;
    default: break;
  }
  quicksort(stu, 1, n, cmp);
  for (i = 1; i <= n; ++i)
    printf("%d\n", stu[i].index);
  return 0;
}