LikeWater - 1739: 成绩排序（太难了啊啊啊啊啊！！！！希望大佬来帮忙啊！！！）

186 阅读 7 评论 0 点赞

####:scream:！太难了啊啊啊啊啊！！！！这绝对是我写过最难的一道题，自己编写的快速排序，写了三重！！！最后还提示我仍然有错误，我实在找不到错误在哪里了，希望有大佬帮我一下！感谢，下面附上我的代码！以及我自己写的各种排序，希望能帮到大家忙！

这是本题的代码，有点长，自己写的快速排序，没有太优化，有些地方可以优化或者可以综合成函数，但是我写了太久都麻木了，实在不想写了，快速排序应该没有问题，就是案例我都找遍了，硬是没找到哪里有问题，希望大佬能帮帮忙找找！:sob:

```cpp
#include<iostream>
#include<string>
#include<string.h>
using namespace std;

int flag=2;//定义全局变量flag，默认为2即对Grade进行排序，1代表对年龄进行排序，0代表对姓名进行排序
struct Student{
    string name;
    int age;
    double Grade;
};

// template<typename T> 
int Partition(Student a[],int low,int high,int flag);

// template <typename S> 
void Qsort(Student a[],int low,int high,int flag);

// template <typename S> 
// int Move(Student a[],int s[],int low,int high);

int main(){
    int N;
    cin >> N;
    Student stu[N+1];           //为方便数组查询，增大数组大小
    for(int i=0;i<N;i++){       //输入学生姓名，年龄，成绩
        cin >> stu[i].name >> stu[i].age >> stu[i].Grade;
    }
    stu[N].name = " ";stu[N].age=0;stu[N].Grade=0;//对最后一组初始化，避免随机值错误

Qsort(stu,0,N-1,flag);//对学生成绩Grade进行排序

int num=0,loc;

for(int i=0;i<N-1;i++){        //寻找成绩相同的学生
        do{
            if(stu[i].Grade == stu[i+1].Grade){
                num++;
                loc = i+1;
                }
            else if(stu[i].Grade != stu[i+1].Grade)break;
            i++;
        }while(i<N-1);

if(num >= 1){           //如果存在成绩相同的学生，则按姓名进行排序
            flag = 0;
            Qsort(stu,loc-num,loc,flag);
            int t1=num,t2=loc;
            num = 0;
            for(int j=t2-t1;j<t2;j++){//在姓名排序完后找是否存在姓名相同的同学，注意是从成绩相同的里面去找
                do
                {
                    if(stu[j].name == stu[j+1].name){
                        num++;
                        loc = j+1;
                        }
                    else if(stu[j].name != stu[j+1].name)break;
                    j++;
                } while (j<t2);
                if(num>=1){     //如果存在姓名相同的同学，则按年龄进行再排序
                    flag=1;
                    Qsort(stu,loc-num,loc,flag);
                    num=0;
                }
            }
        }
    }

for(int i=0;i<N;i++){
        cout << stu[i].name << " " << stu[i].age << " " << stu[i].Grade << endl;
    }
    return 0;
}

int Partition(Student a[],int low,int high,int flag){//分割大小两部分
    if(flag == 2){                      //flag为2，对成绩进行排序
        Student pivotKey = a[low];      //枢轴取最小值a[low],即子表第一个记录
        while(low<high){            //从序列的两端交替的向中间扫描
            while (low<high && a[high].Grade >= pivotKey.Grade) --high;
            a[low] = a[high];       //找到比枢轴小的记录，移到低端
            while (low<high && a[low].Grade <= pivotKey.Grade) ++low;
            a[high] = a[low];       //找到比枢轴大的记录，移到高端
        }
        a[low] = pivotKey;          //原枢轴记录归位
        return low;                 //返回枢轴记录的位置，以便递归调用
    }
    else if(flag == 1){             //对年龄进行排序
        Student pivotKey = a[low];      
        while(low<high){            
            while (low<high && a[high].age >= pivotKey.age) --high;
            a[low] = a[high];       
            while (low<high && a[low].age <= pivotKey.age) ++low;
            a[high] = a[low];
        }
        a[low]= pivotKey;        
        return low;
    }
    else if(flag == 0){             //对姓名进行排序
        Student pivotKey = a[low];      
        while(low<high){            
            while (low<high && a[high].name >= pivotKey.name) --high;
            a[low] = a[high];       
            while (low<high && a[low].name <= pivotKey.name) ++low; 
            a[high] = a[low];
        }
        a[low]= pivotKey;         
        return low;                
    }
}

void Qsort(Student a[],int low,int high,int flag){//对序列low到high的位置进行快速排序
    if(low < high){     //递归调用推出条件，当低位比高位高时退出递归
        int piovtLoc = Partition(a,low,high,flag);
        Qsort(a,low,piovtLoc,flag);  //取low到pivotloc为低半段
        Qsort(a,piovtLoc+1,high,flag);//取pivotloc为高半段递归排序
    }
}/* 快速排序：通过一趟排序将待排序列分割成独立的两个部分，
其中一部分均比另一部分关键字小，则可分别对这两部分序列继续进行排序，
以达到整个序列有序*/

// template <typename S> 
/* int Move(Student a[],int s[],int low,int high){
    int pivotKey = s[low];
    while(low<high){
        while (low<high && s[high] >= pivotKey) --high;
        a[low] = a[high];
        while (low<high && s[low] <= pivotKey) ++low;
        a[low] = a[high];
    }
    s[low] = pivotKey;
    return low;
} */
```

这是冒泡排序，我用来解决了一个排序问题！
```cpp
#include<iostream>
#include<cmath>
using namespace std;

template<typename T> void BubbleSort(T s[],int n){
    int t;
    for(int i=n-1;i>=1;i--){    //留出第一位0，用于其他用途，比如哨兵。
        for(int j=1;j<i;j++){   //每趟从第一位0到第i-1位i进行交换，交换n躺
            if(s[j]>s[j+1]){
                t = s[j];       //如果前面的数比后面的数大，交换两个数
                s[j] = s[j+1];
                s[j+1] = t;    
            }
        }
    }
} /*冒泡排序：交换相邻的两个数，小的上浮，大的下沉，
每趟交换都会有一个大的沉入最底层，n躺后完成排序*/

int main(){
    int s[11]={0};//定义比10大1的数组，方便使用
    for(int i=1;i<11;i++){
        cin >> s[i];
    }
    BubbleSort(s,11);
    for(int i=10;i>=1;i--){
        if(i!=10)cout<<" ";
        cout << s[i];
    }
    return 0;
}
```

####还有选择排序和直接插入排序我放到另一篇文章里面，题目 1169: 绝对值排序大家需要也可以进去拿！！

0.0分

1 人评分

本文分类：题解列表
浏览次数：186 次浏览
发布日期：2023-02-28 20:06:24
本文链接：https://blog.dotcpp.com/a/94402

上一篇 > 3030基础解法（Python）
下一篇 > LikeWater - 1128: C语言训练-排序问题<1>

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 7 条评论

LikeWater 1年前回复TA

@计科余定成 我giao了个giao，原来如此啊，我还以为是我代码有问题，搁那找半天，giao了，多谢大佬

计科余定成 1年前回复TA

@计科余定成 你这只能测试一组数据

计科余定成 1年前回复TA

@计科余定成 多组输入

LikeWater 1年前回复TA

@计科余定成 测试数据多组也试过了，各种情况都

LikeWater 1年前回复TA

@计科余定成 感觉没毛病哇？输入姓名string字符串name int年龄age double成绩Grade

计科余定成 1年前回复TA

注意看题：
输入格式
测试数据有多组，每组输入第一行有一个整数N（N<=1000），接下来的N行包括N个学生的数据。
每个学生的数据包括姓名（长度不超过100的字符串）、年龄（整形数）、成绩（小于等于100的正数）。

LikeWater 1年前回复TA

66666666666666666666666666

LikeWater - 1739: 成绩排序（太难了啊啊啊啊啊！！！！希望大佬来帮忙啊！！！）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 7 条评论

发表评论 取消回复

评论列表共有 7 条评论

发表评论取消回复