数据结构的算法复杂度

Question

问题遇到的现象和发生背景

问题相关代码，请勿粘贴截图

C或者C++

运行结果及报错内容

绩点升序排序

我的解答思路和尝试过的方法

我已经用python完成了一遍

我想要达到的结果

C或C++形式完成，并且程序可以正常运行

Answer 1

如果已经按照绩点升序排好了，用插入排序可满足时间复杂度。
运行结果：

完整输出结果：

代码：

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

//数组以升序排列时，二分法查找x,返回在顺序表中stu数组中的下标
int binSearch(LinkList *list,int x)
{
    int low, high, mid;
    int n = list->nmb;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (x < list->stu[mid].id)
            high = mid - 1;
        else if (x > list->stu[mid].id)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

//录入数据
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\n", stu.id);
    printf("姓名：%s\n", stu.name);
    printf("性别：%c\n", stu.sex);
    printf("专业：%s\n", stu.pro);
    printf("班级：%d\n", stu.grade);
    printf("绩点：%.2f\n", stu.score);
}


//插入排序
void InsertSort(LinkList *list )
{
    int i, j;
    Student temp;
    int numsSize = list->nmb;
    for (i = 1; i < numsSize; i++)
    {
        if (list->stu[i].score < list->stu[i - 1].score)
        {
            temp = list->stu[i];
            for (j = i - 1; j >= 0; j--)
            {
                if (list->stu[j].score > temp.score)
                    list->stu[j + 1] = list->stu[j];
                else
                    break;
            }
            list->stu[j + 1] = temp;
        }
    }
}



int main()
{
    int i, n;
    int id;
    LinkList list;
    input(&list); //录入数据，按照每个班级的绩点升序排序
    
    InsertSort(&list);

    //显示排序后的结果
    for (i = 0; i < list.nmb; i++)
        showStu(list.stu[i]);
    return 0;
}

各种排序算法的复杂度，可以看一下下面的文章：

排序算法及其时间复杂度_学而不思则忘的博客-CSDN博客_排序算法时间复杂度 1. 排序算法时间复杂度稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；内排序：所有排序操作都在内存中完成；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度： 一个算法执行所耗费的时间。空间复杂度：运行完一个程序所需内存的大小。图片名词解释：n: 数据规模k: “桶”的个数In-place: 占用常数内存，不占用额外内存Out-place: 占用额 https://blog.csdn.net/weixin_43207025/article/details/114902065