PTA数据结构与算法题目集(中文) 7-37 模拟EXCEL排序 (25 分)

7-37 模拟EXCEL排序 (25 分)

Excel可以对一组纪录按任意指定列排序。现请编写程序实现类似功能。

输入格式:

输入的第一行包含两个正整数

输出格式:

在

输入样例:

3 1
000007 James 85
000010 Amy 90
000001 Zoe 60

输出样例:

000001 Zoe 60
000007 James 85
000010 Amy 90
题目分析：这道题是利用表排序和排序算法的一道题 排序算法采用快排 但最后有两组数据没通过 查了资料用c++STL中的sort就可以 STL中sort函数不单单使用了快排 而且使用了插入排序和堆排序

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<malloc.h>
  5 
  6 struct Student
  7 {
  8     int Id;
  9     char Name[9];
 10     int Score;
 11 }students[100010];
 12 int Table[100010];
 13 void Swap(int i, int j)
 14 {
 15     int tmp = Table[i];
 16     Table[i] = Table[j];
 17     Table[j] = tmp;
 18 }
 19 void Quick_Sort_1(int start,int end)
 20 {
 21     if (start >= end - 1)
 22         return;
 23     int tmp = (start + end) / 2;
 24     //三元取中值
 25     if (students[Table[start]].Id > students[Table[end - 1]].Id)
 26         Swap(start, end - 1);
 27     if (students[Table[start]].Id > students[Table[tmp]].Id)
 28         Swap(start, tmp);
 29     if (students[Table[tmp]].Id > students[Table[end - 1]].Id)
 30         Swap(tmp, end - 1);
 31     Swap(start, tmp);
 32     int i = start + 1;
 33     for (int j = start+1; j < end; j++)
 34     {
 35         if (students[Table[j]].Id < students[Table[start]].Id)
 36             Swap(i++, j);
 37     }
 38     Swap(start,i-1);
 39     Quick_Sort_1(start, i-1);
 40     Quick_Sort_1(i, end);
 41 }
 42 void Quick_Sort_2(int start, int end)
 43 {
 44     if (start >= end - 1)
 45         return;
 46     int tmp = (start + end) / 2;
 47     if (strcmp(students[Table[start]].Name, students[Table[end-1]].Name)<0)
 48         Swap(start, end - 1);
 49     if (strcmp(students[Table[start]].Name, students[Table[tmp]].Name) < 0)
 50         Swap(start, tmp);
 51     if (strcmp(students[Table[tmp]].Name, students[Table[end-1]].Name) < 0)
 52         Swap(tmp, end - 1);
 53     Swap(start, tmp);
 54     int i = start + 1;
 55     for (int j = start + 1; j < end; i++)
 56     {
 57         if (strcmp(students[Table[j]].Name, students[Table[start]].Name) < 0)
 58             Swap(i++, j);
 59         else if (!strcmp(students[Table[j]].Name, students[Table[start]].Name))
 60             if (students[Table[j]].Id < students[Table[start]].Id)
 61                 Swap(i++, j);
 62     }
 63     Swap(start, i - 1);
 64     Quick_Sort_2(start, i - 1);
 65     Quick_Sort_2(i, end);
 66 }
 67 
 68 void Quick_Sort_3(int start, int end)
 69 {
 70     if (start >= end - 1)
 71         return;
 72     int tmp = (start + end) / 2;
 73     if (students[Table[start]].Score > students[Table[end - 1]].Score)
 74         Swap(start, end - 1);
 75     if (students[Table[start]].Score > students[Table[tmp]].Score)
 76         Swap(start, tmp);
 77     if (students[Table[tmp]].Score > students[Table[end - 1]].Score)
 78         Swap(tmp, end - 1);
 79     Swap(start, tmp);
 80     int i = start + 1;
 81     for (int j = start + 1; j < end; j++)
 82     {
 83         if (students[Table[j]].Score < students[Table[start]].Score)
 84             Swap(i++, j);
 85         else if (students[Table[j]].Score == students[Table[start]].Score)
 86             if (students[Table[j]].Id < students[Table[start]].Id)
 87                 Swap(i++, j);
 88     }
 89     Swap(start, i - 1);
 90     Quick_Sort_3(start, i - 1);
 91     Quick_Sort_3(i, end);
 92 }
 93 int main()
 94 {
 95     int N,C;
 96     scanf("%d%d", &N,&C);
 97     int id=0, score=0;
 98     char name[9] = { 0 };
 99     for (int i = 0; i < N; i++)
100     {
101         Table[i] = i;
102         scanf("%d%s%d", &id, name, &score);
103         students[i].Id = id;
104         strcpy(students[i].Name, name);
105         students[i].Score = score;
106     }
107     switch (C)
108     {
109     case 1:Quick_Sort_1(0, N); break;
110     case 2:Quick_Sort_2(0, N); break;
111     case 3:Quick_Sort_3(0, N); break;
112     }
113     for (int i = 0; i < N; i++)
114         printf("%06d %s %d
", students[Table[i]].Id,students[Table[i]].Name,students[Table[i]].Score);
115     return 0;
116 }

View Code