数据结构的算法复杂度
问题遇到的现象和发生背景
问题相关代码，请勿粘贴截图
C或C++
运行结果及报错内容
表示出来即可
我的解答思路和尝试过的方法
我已经用python完成了一遍
我想要达到的结果
C或者C++表示并且程序可以正常运行
你题目的解答代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#define N 1000
typedef struct _stu
{
int id; //学号
char name[20];//姓名
char sex;//性别
char pro[20]; //专业
int grade; //班级
float score; //绩点
}Student;
typedef struct _node
{
Student stu[N];
int nmb; //实际学生数量
}LinkList;
//录入数据
void input(LinkList* list)
{
int i, n;
printf("请输入学生数量：");
scanf("%d", &n);
list->nmb = n;
for (i = 0; i < n; i++)
{
printf("请输入学生%d的学号：", i + 1);
scanf("%d", &list->stu[i].id);
printf("请输入学生%d的姓名：", i + 1);
scanf("%s", list->stu[i].name);
getchar(); //吸收回车符
printf("请输入学生%d的性别：", i + 1);
scanf("%c", &list->stu[i].sex);
printf("请输入学生%d的专业：", i + 1);
scanf("%s", list->stu[i].pro);
printf("请输入学生%d的班级：", i + 1);
scanf("%d", &list->stu[i].grade);
printf("请输入学生%d的绩点：", i + 1);
scanf("%f", &list->stu[i].score);
}
}
//显示学生信息
void showStu(Student stu)
{
printf("学号：%d", stu.id);
printf(" 姓名：%s", stu.name);
printf(" 性别：%c", stu.sex);
printf(" 专业：%s", stu.pro);
printf(" 班级：%d", stu.grade);
printf(" 绩点：%.2f\n", stu.score);
}
void sort(Student a[],int n)
{
int i,j;
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
if(a[j].score > a[j+1].score || (a[j].score == a[j+1].score && a[j].id > a[j+1].id))
{
Student t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
int main()
{
int i, n=0,grade;
int mid;
LinkList list;
input(&list); //录入数据，按照学号升序排序录入
Student a[list.nmb];
printf("请输入要排序的班级：");
scanf("%d", &grade);
for (i = 0; i < list.nmb; i++)
{
if (list.stu[i].grade == grade){
a[n++] = list.stu[i];
}
}
sort(a,n);
for (i = 0; i < n; i++)
{
showStu(a[i]);
}
return 0;
}
如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!
时间复杂度为O(NLogN)，需要用归并排序，各排序算法复杂度如下：
运行结果：
代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define N 1000
typedef struct _stu
{
int id; //学号
char name[20];//姓名
char sex;//性别
char pro[20]; //专业
int grade; //班级
float score; //绩点
}Student;
typedef struct _node
{
Student stu[N];
int nmb; //实际学生数量
}LinkList;
//录入数据
void input(LinkList* list)
{
int i, n;
printf("请输入学生数量：");
scanf("%d", &n);
list->nmb = n;
for (i = 0; i < n; i++)
{
printf("请输入学生%d的学号：", i + 1);
scanf("%d", &list->stu[i].id);
printf("请输入学生%d的姓名：", i + 1);
scanf("%s", list->stu[i].name);
getchar(); //吸收回车符
printf("请输入学生%d的性别：", i + 1);
scanf("%c", &list->stu[i].sex);
printf("请输入学生%d的专业：", i + 1);
scanf("%s", list->stu[i].pro);
printf("请输入学生%d的班级：", i + 1);
scanf("%d", &list->stu[i].grade);
printf("请输入学生%d的绩点：", i + 1);
scanf("%f", &list->stu[i].score);
}
}
//显示学生信息
void showStu(Student stu)
{
printf("学号：%d\t", stu.id);
printf("姓名：%s\t", stu.name);
printf("性别：%c\t", stu.sex);
printf("专业：%s\t", stu.pro);
printf("班级：%d\t", stu.grade);
printf("绩点：%.2f\n", stu.score);
}
//插入排序
void merge(LinkList* list, int L, int M, int R) {
int LEFT_SIZE = M - L;
int RIGHT_SIZE = R - M + 1;
Student* left = (Student*)malloc(LEFT_SIZE * sizeof(Student));
Student* right = (Student*)malloc(RIGHT_SIZE * sizeof(Student));
int i, j, k;
for (i = L; i < M; i++) left[i - L] = list->stu[i];
for (i = M; i <= R; i++) right[i - M] = list->stu[i];
i = 0, j = 0, k = L;
while (i < LEFT_SIZE && j < RIGHT_SIZE) {
if ((left[i].score < right[j].score) || (left[i].score == right[j].score && left[i].id < right[j].id)) {
list->stu[k] = left[i];
i++;
k++;
}
else {
list->stu[k] = right[j];
j++;
k++;
}
}
while (i < LEFT_SIZE) {
list->stu[k] = left[i];
k++;
i++;
}
while (j < RIGHT_SIZE) {
list->stu[k] = right[j];
k++;
j++;
}
}
void mergesort(LinkList* list, int L, int R) {
//L为数组的开始下表，R为数组的结束下标，以[1,2,3,4]为例，L=0，R=3；
if (L == R)return;
else {
int M = (R + L) / 2;
mergesort(list, L, M);
mergesort(list, M + 1, R);
merge(list, L, M + 1, R);
}
}
int main()
{
int i, n;
int id;
LinkList list;
input(&list); //录入数据，按照每个班级的绩点升序排序
mergesort(&list, 0, list.nmb - 1);
//显示排序后的结果
for (i = 0; i < list.nmb; i++)
showStu(list.stu[i]);
return 0;
}
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632