课后作业

第二十四课

1. 请编写一个程序，使用堆排序算法对一个包含学生成绩的数组进行排序。每个学生的信息包括姓名（string类型）和成绩（double类型）。使用堆排序对学生数组按成绩从高到低排序。如果成绩相同，则按姓名字母顺序升序排序。在排序完成后，计算并输出以下信息：

• 按要求排序后的学生信息，每行一个学生姓名和成绩。
• 排名前五的学生信息，每行一个学生姓名和成绩。
• 所有学生成绩的平均分，保留两位小数。

// 示例输入：
请输入学生数量：6 
请输入学生姓名和成绩：
Alice 85.5
Bob 92.0
Charlie 88.0
David 95.5
Eve 78.0
Frank 88.0

// 示例输出：
排序后的学生信息：
Eve 78
Alice 85.5
Frank 88
Charlie 88
Bob 92
David 95.5

排名前五的学生信息：
Eve 78
Alice 85.5
Frank 88
Charlie 88
Bob 92

平均分：87.83

• 🎈
• 历史解析
  • 本地输入输出示例错误，与题目不符
  • 题目与示例明显不符，应及时联系老师修改
  • 题目要求堆排序，示例中使用了选择排序
  • 此题当前示例已更新，将课上引导故暂不提供参考答案

2. 请编写一个程序，使用桶排序算法对一个包含员工收入的数组进行排序。每个员工的信息包括姓名（string类型）和月收入（double类型）。使用桶排序对员工数组按收入从低到高排序。如果收入相同，则按姓名字母顺序升序排序。在排序完成后，计算并输出以下信息：

• 按要求排序后的员工信息，每行一个员工姓名和月收入。
• 排名前十的员工信息，每行一个员工姓名和月收入。
• 所有员工收入的中位数，保留两位小数。

// 示例输入：
请输入员工数量：6
请输入员工姓名和收入:
Alice 5500.0
Bob 7000.0
Charlie 6500.0
David 4800.0
Eve 7000.0
Frank 6000.0

// 示例输出：
排序后的员工信息：
David 4800
Alice 5500
Frank 6000
Charlie 6500
Bob 7000
Eve 7000

排名前十的员工信息:
David 4800
Alice 5500
Frank 6000
Charlie 6500
Bob 7000
Eve 7000

收入中位数：6250.00

• ❌

• 历史解析

  • 题目要求使用桶排序算法实现，而题解使用的插入排序故此错误
  • 题目要求中位数保留两位小数，未保留，错误

• 参考答案

#include <iostream>   // 用于输入输出流
#include <vector>     // 用于使用向量容器
#include <string>     // 用于使用字符串类
#include <algorithm>  // 用于算法函数，如 stable_sort
#include <iomanip>    // 用于设置输出精度

using namespace std;

// 定义员工结构体
struct Employee {
    string name;   // 员工姓名
    double income; // 员工收入
};

// 自定义比较函数，用于在桶内进行稳定排序
bool compareByName(const Employee& a, const Employee& b) {
    return a.name < b.name;
}

// 桶排序函数
void bucketSort(vector<Employee>& employees, int bucketCount) {
    // 初始化最小和最大收入
    double minIncome = employees[0].income;
    double maxIncome = employees[0].income;

    // 找到收入的最小值和最大值
    for (const auto& employee : employees) {
        if (employee.income < minIncome) {
            minIncome = employee.income;
        }
        if (employee.income > maxIncome) {
            maxIncome = employee.income;
        }
    }

    // 计算每个桶的范围
    double range = (maxIncome - minIncome) / bucketCount;
    vector<vector<Employee>> buckets(bucketCount); // 初始化桶

    // 将每个员工放入对应的桶中
    for (const auto& employee : employees) {
        int bucketIndex = static_cast<int>((employee.income - minIncome) / range);
        // 确保最大收入的员工放入最后一个桶中
        if (bucketIndex == bucketCount) {
            bucketIndex--;
        }
        buckets[bucketIndex].push_back(employee);
    }

    // 在每个桶内进行稳定排序
    for (auto& bucket : buckets) {
        stable_sort(bucket.begin(), bucket.end(), compareByName);
    }

    // 合并所有桶中的员工
    employees.clear();
    for (const auto& bucket : buckets) {
        for (const auto& employee : bucket) {
            employees.push_back(employee);
        }
    }
}

// 计算员工收入的中位数
double calculateMedian(const vector<Employee>& employees) {
    int n = employees.size();
    if (n % 2 == 0) {
        // 偶数个员工，返回中间两个数的平均值
        return (employees[n / 2 - 1].income + employees[n / 2].income) / 2.0;
    } else {
        // 奇数个员工，返回中间的数
        return employees[n / 2].income;
    }
}

int main() {
    int N;
    cout << "请输入员工数量：";
    cin >> N;
    vector<Employee> employees(N);

    cout << "请输入员工姓名和收入：" << endl;
    // 输入员工信息
    for (int i = 0; i < N; ++i) {
        cin >> employees[i].name >> employees[i].income;
    }

    int bucketCount = 10; // 设置桶的数量
    bucketSort(employees, bucketCount); // 对员工进行桶排序

    cout << "排序后的员工信息：" << endl;
    // 输出排序后的员工信息
    for (const auto& employee : employees) {
        cout << employee.name << " " << employee.income << endl;
    }

    cout << "\n排名前十的员工信息：" << endl;
    // 输出排名前十的员工信息
    for (int i = 0; i < 10 && i < N; ++i) {
        cout << employees[i].name << " " << employees[i].income << endl;
    }

    // 计算并输出收入中位数
    double medianIncome = calculateMedian(employees);
    cout << "\n收入中位数：" << fixed << setprecision(2) << medianIncome << endl;

    return 0;
}

3. 请编写一个学生成绩管理系统，要求实现以下功能：（任意排序方法，实现即可）

1. 输入学生的姓名和多门课程的成绩。
2. 按某门课程的成绩对学生进行排序，如果成绩相同则按姓名字母顺序升序排序。
3. 输出排序后的学生信息。
4. 输出每个学生的总成绩和平均成绩。
5. 输出全班学生的最高总成绩、最低总成绩和平均总成绩。

// 示例输入：
请输入学生数量：3
请输入课程数量：3
请输入学生姓名和每门课程的成绩：
Alice 85.5 90.0 88.0
Bob 92.0 85.0 91.0
Charlie 88.0 86.0 87.0

// 示例输出：
排序后的学生信息（按第一门课程的成绩）：
Alice 85.5 90 88 
Charlie 88 86 87 
Bob 92 85 91 

每个学生的总成绩和平均成绩：
Alice 总成绩：263.5 平均成绩：87.83
Charlie 总成成绩：261.00 平均成绩：87.00
Bob 总成绩：268.00 平均成绩：89.33

全班最高总成绩：268.00
全班最低总成绩：261.00
全班平均总成绩：264.17

• ❌

• 历史解析

  • 使用了快速排序，但结果并不正确
  • 题目要求学生成绩管理系统，而你的结构体定义为员工工资结构体？
  • 代码没有实现题目要求的所有功能，例如按某门课程成绩排序，输出学生的总成绩和平均成绩，输出全班最高总成绩、最低总成绩和平均总成绩

• 参考答案（注意我使用的桶+快排，所以代码量显大）

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip> // setprecision

using namespace std; // 使用std命名空间

struct Student {
    string name;            // 学生姓名
    vector<double> grades;  // 学生成绩列表
    double totalGrade;      // 学生总成绩
    double averageGrade;    // 学生平均成绩
};

// 快速排序的分割函数
int partition(vector<Student>& students, int low, int high) {
    string pivot = students[high].name; // 选择最后一个元素为枢轴
    int i = low - 1; // i是较小元素的索引

    for (int j = low; j < high; j++) {
        if (students[j].name < pivot) { // 如果当前元素小于枢轴
            i++; // 增加较小元素的索引
            swap(students[i], students[j]); // 交换
        }
    }
    swap(students[i + 1], students[high]); // 交换枢轴元素和i+1位置的元素
    return i + 1; // 返回枢轴索引
}

// 快速排序函数
void quickSort(vector<Student>& students, int low, int high) {
    if (low < high) {
        int pi = partition(students, low, high); // 分割索引
        quickSort(students, low, pi - 1); // 递归排序左边
        quickSort(students, pi + 1, high); // 递归排序右边
    }
}

// 桶排序函数
void bucketSort(vector<Student>& students, int bucketCount) {
    double minGrade = students[0].grades[0]; // 获取最低成绩
    double maxGrade = students[0].grades[0]; // 获取最高成绩

    // 找到成绩的最小值和最大值
    for (int i = 0; i < students.size(); ++i) {
        for (int j = 0; j < students[i].grades.size(); ++j) {
            if (students[i].grades[j] < minGrade) {
                minGrade = students[i].grades[j];
            }
            if (students[i].grades[j] > maxGrade) {
                maxGrade = students[i].grades[j];
            }
        }
    }

    double range = (maxGrade - minGrade) / bucketCount; // 计算每个桶的范围
    vector<vector<Student>> buckets(bucketCount); // 创建桶

    // 将学生分配到不同的桶中
    for (int i = 0; i < students.size(); ++i) {
        int bucketIndex = static_cast<int>((students[i].grades[0] - minGrade) / range);
        if (bucketIndex == bucketCount) {
            bucketIndex--;
        }
        buckets[bucketIndex].push_back(students[i]);
    }

    // 对每个桶中的学生按姓名进行快速排序
    for (int i = 0; i < buckets.size(); ++i) {
        if (!buckets[i].empty()) {
            quickSort(buckets[i], 0, buckets[i].size() - 1);
        }
    }

    // 将桶中的学生合并回原数组
    students.clear();
    for (int i = 0; i < buckets.size(); ++i) {
        for (int j = 0; j < buckets[i].size(); ++j) {
            students.push_back(buckets[i][j]);
        }
    }
}

int main() {
    int N, M; // N表示学生数量，M表示课程数量
    cout << "请输入学生数量：";
    cin >> N; // 输入学生数量
    cout << "请输入课程数量：";
    cin >> M; // 输入课程数量

    vector<Student> students(N); // 创建学生列表，大小为N

    cout << "请输入学生姓名和每门课程的成绩：" << endl;
    for (int i = 0; i < N; ++i) {
        cin >> students[i].name; // 输入学生姓名
        students[i].grades.resize(M); // 调整学生成绩列表大小为M
        for (int j = 0; j < M; ++j) {
            cin >> students[i].grades[j]; // 输入每门课程的成绩
        }

        // 计算学生的总成绩和平均成绩
        students[i].totalGrade = 0;
        for (int j = 0; j < students[i].grades.size(); ++j) {
            students[i].totalGrade += students[i].grades[j]; // 计算总成绩
        }
        students[i].averageGrade = students[i].totalGrade / M; // 计算平均成绩
    }

    int bucketCount = 10; // 定义桶的数量
    bucketSort(students, bucketCount); // 使用桶排序对学生按第一门课程成绩排序

    cout << "排序后的学生信息（按第一门课程的成绩）：" << endl;
    for (int i = 0; i < students.size(); ++i) {
        cout << students[i].name << " "; // 输出学生姓名
        for (int j = 0; j < students[i].grades.size(); ++j) {
            cout << students[i].grades[j] << " "; // 输出学生每门课程的成绩
        }
        cout << endl;
    }

    cout << "\n每个学生的总成绩和平均成绩：" << endl;
    double totalClassScore = 0; // 全班总成绩
    double maxTotalGrade = students[0].totalGrade; // 全班最高总成绩
    double minTotalGrade = students[0].totalGrade; // 全班最低总成绩

    for (int i = 0; i < students.size(); ++i) {
        cout << students[i].name << " 总成绩：" << students[i].totalGrade 
             <<" 平均成绩：" << fixed << setprecision(2) << students[i].averageGrade << endl;
        totalClassScore += students[i].totalGrade; // 累计全班总成绩
        if (students[i].totalGrade > maxTotalGrade) {
            maxTotalGrade = students[i].totalGrade; // 更新最高总成绩
        }
        if (students[i].totalGrade < minTotalGrade) {
            minTotalGrade = students[i].totalGrade; // 更新最低总成绩
        }
    }

    double averageClassScore = totalClassScore / N; // 计算全班平均总成绩

    cout << "\n全班最高总成绩：" << fixed << setprecision(2) << maxTotalGrade << endl;
    cout << "全班最低总成绩：" << fixed << setprecision(2) << minTotalGrade << endl;
    cout << "全班平均总成绩：" << fixed << setprecision(2) << averageClassScore << endl;

    return 0;
}