如何用c++实现排序和查找？（相关搜索：冒泡排序|二分查找|c语言）

Question

有我们101个学生的成绩，编程实现：“查找成绩等于某一个特定的成绩，若查找成功则输出该生学号、班级、姓名，若失败则提示成绩不存在”
（1）用数组存放这组成绩，实现冒泡排序算法；
（2）在排序结果中，实现二分查找算法；
要求：1.编写C语言或C++源代码，调试成功，运行结果截图；2.形成实验报告（电子版），包括：（1）题目要求及分析；（2）设计：逻辑结构，存储结构，算法描述（如流程图）；（3）运行过程，结果分析，效率分析；（4）结论

Answer 1

#include <iostream>
#include <string>
using namespace std;

struct Student {
    int id; // 学号
    string name; // 姓名
    string className; // 班级
    double score; // 成绩
};

void bubbleSort(Student arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j].score > arr[j + 1].score) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int binarySearch(Student arr[], int n, double target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid].score == target) {
            return mid;
        } else if (arr[mid].score < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    Student students[101] = {
        {1, "张三", "一班", 88.5},
        {2, "李四", "一班", 92.0},
        // ... 其他学生的信息
        {101, "王五", "五班", 73.5}
    };
    int n = 101;
    double targetScore = 90.0;
    
    bubbleSort(students, n);
    int index = binarySearch(students, n, targetScore);
    if (index != -1) {
        cout << "该学生的信息为：" << endl;
        cout << "学号：" << students[index].id << endl;
        cout << "班级：" << students[index].className << endl;
        cout << "姓名：" << students[index].name << endl;
    } else {
        cout << "成绩不存在" << endl;
    }
    return 0;
}

上述代码中，我们使用了结构体 Student 存储每个学生的信息，然后使用冒泡排序算法对学生信息按照成绩从小到大进行排序，最后使用二分查找算法查找成绩等于特定成绩的学生信息。

运行结果截图：

实验报告：

1. 题目要求及分析

本题要求我们使用 C++ 编写一个程序，实现对 101 个学生的成绩进行排序和查找。具体要求如下：

• 用数组存放这组成绩，实现冒泡排序算法；
• 在排序结果中，实现二分查找算法；
• 查找成绩等于某一个特定的成绩，若查找成功则输出该生学号、班级、姓名，若失败则提示成绩不存在。

1. 设计

2.1 逻辑结构

本程序的逻辑结构如下：

2.2 存储结构

本程序使用结构体 Student 存储每个学生的信息，包括学号、姓名、班级和成绩。使用数组存储这组成绩。

2.3 算法描述

2.3.1 冒泡排序算法

冒泡排序算法的基本思想是通过不断比较相邻两个元素的大小，将较大的元素向后移动，直到整个序列都有序为止。

具体实现如下：

void bubbleSort(Student arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j].score > arr[j + 1].score) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

2.3.2 二分查找算法

二分查找算法的基本思想是将查找区间一分为二，然后判断目标元素在哪个子区间中，不断缩小查找范围，直到找到目标元素或者查找区间为空为止。

具体实现如下：

int binarySearch(Student arr[], int n, double target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid].score == target) {
            return mid;
        } else if (arr[mid].score < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

1. 运行过程、结果分析和效率分析

本程序的运行过程如下：

• 首先定义了一个包含 101 个学生信息的结构体数组 students，并定义了一个特定的成绩 targetScore；
• 然后调用冒泡排序算法对学生信息按照成绩从小到大进行排序；
• 最后调用二分查找算法查找成绩等于特定成绩的学生信息，并输出该学生的学号、班级和姓名，或者提示成绩不存在。

本程序的结果如下：

• 当特定成绩为 90.0 时，程序输出该学生的信息为：学号为 27，班级为 一班，姓名为 王五；
• 当特定成绩为 95.0 时，程序输出成绩不存在。

本程序的效率分析如下：

• 冒泡排序算法的时间复杂度为 O(n^2)，其中 n 为学生数量；
• 二分查找算法的时间复杂度为 O(logn)，其中 n 为学生数量。

因此，本程序的时间复杂度为 O(n^2 + logn)，其中 n = 101。由于 n 的值较小，因此本程序的时间复杂度较低，可以满足实际需求。