讲义

课后作业

2024/5/23

# 第二十三课

# 1. 请编写一个程序，使用归并排序算法对一个包含城市信息的数组进行排序。每个城市的信息包括名称（string类型）和人口（int类型）。使用归并排序对城市数组按人口从多到少排序。如果人口相同，则按名称字母顺序升序排序。在排序完成后，计算并输出以下信息：

  • 排序后的城市信息
  • 前三大城市的信息
  • 所有城市的人口总和
// 示例输入：
6
Shanghai 24183300
Beijing 21707000
Karachi 14910352
Istanbul 15029231
Dhaka 8906039
Tokyo 37435191

// 示例输出：
排序后的城市信息：
Tokyo 37435191
Shanghai 24183300
Beijing 21707000
Istanbul 15029231
Karachi 14910352
Dhaka 8906039

前三大城市：
Tokyo 37435191
Shanghai 24183300
Beijing 21707000

人口总和：122171113

  • ❌

  • 历史解析

    • 根据题目要求，使用归并排序算法，而你当前使用的是选择排序而不是归并排序算法，故错误
    • 结构体定义错误，题目要求对包含城市信息的数组进行排序，而你定义的结构体是学生成绩
    • 代码结构和输出与题目要求的输出格式不匹配，故错误

  • 参考答案

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct City {
    string name;
    int population;
};

// 归并排序的辅助函数
void merge(vector<City>& cities, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<City> L(n1);
    vector<City> R(n2);

    for (int i = 0; i < n1; ++i) {
        L[i] = cities[left + i];
    }
    for (int i = 0; i < n2; ++i) {
        R[i] = cities[mid + 1 + i];
    }

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i].population > R[j].population || 
            (L[i].population == R[j].population && L[i].name < R[j].name)) {
            cities[k] = L[i];
            ++i;
        } else {
            cities[k] = R[j];
            ++j;
        }
        ++k;
    }

    while (i < n1) {
        cities[k] = L[i];
        ++i;
        ++k;
    }

    while (j < n2) {
        cities[k] = R[j];
        ++j;
        ++k;
    }
}

void mergeSort(vector<City>& cities, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(cities, left, mid);
        mergeSort(cities, mid + 1, right);

        merge(cities, left, mid, right);
    }
}

int main() {
    int n;
    cin >> n;

    vector<City> cities(n);
    for (int i = 0; i < n; ++i) {
        cin >> cities[i].name >> cities[i].population;
    }

    mergeSort(cities, 0, n - 1);

    cout << "排序后的城市信息：" << endl;
    for (const auto& city : cities) {
        cout << city.name << " " << city.population << endl;
    }

    cout << endl << "前三大城市：" << endl;
    for (int i = 0; i < min(3, n); ++i) {
        cout << cities[i].name << " " << cities[i].population << endl;
    }

    int total_population = 0;
    for (const auto& city : cities) {
        total_population += city.population;
    }
    cout << endl << "人口总和：" << total_population << endl;

    return 0;
}

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

  • 每个年龄段的人数（假设年龄在0到100岁之间）
  • 年龄分布最多的年龄及其人数
// 示例输入：
6
Alice 34
Bob 45
Charlie 34
David 23
Eve 45
Frank 29

// 示例输出：
排序后的员工信息：
David 23
Frank 29
Alice 34
Charlie 34
Bob 45
Eve 45

年龄段人数：
23：1
29：1
34：2
45：2

分布最多的年龄及其人数：
34：2
45：2

  • ❌

  • 历史解析

    • 输出与题目要求不匹配，故错误，findMaxAgeGroup函数没有返回所有具有最大人数的年龄段
    • 优化建议：在填充sortedEmployees数组时直接进行姓名字母排序，省去后面多重循环排序的麻烦

  • 参考答案

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct Employee {
    string name;
    int age;
};

// 计数排序算法
void countingSort(vector<Employee>& employees) {
    int maxAge = 100; // 假设年龄范围是0到100
    vector<int> count(maxAge + 1, 0);

    // 统计每个年龄的人数
    for (const auto& employee : employees) {
        count[employee.age]++;
    }

    // 计算每个年龄段的累计数量
    for (int i = 1; i <= maxAge; i++) {
        count[i] += count[i - 1];
    }

    // 创建一个用于存放排序结果的数组
    vector<Employee> sortedEmployees(employees.size());

    // 从后往前遍历原始数组，将员工信息按姓名字母顺序插入到排序结果数组中
    for (int i = employees.size() - 1; i >= 0; i--) {
        int age = employees[i].age;
        sortedEmployees[count[age] - 1] = employees[i];
        count[age]--;
    }

    // 对每个年龄段内部按姓名进行排序
    for (int i = 0; i < employees.size();) {
        int age = sortedEmployees[i].age;
        int start = i;
        while (i < employees.size() && sortedEmployees[i].age == age) {
            i++;
        }
        sort(sortedEmployees.begin() + start, sortedEmployees.begin() + i, [](const Employee& a, const Employee& b) {
            return a.name < b.name;
        });
    }

    // 将排序结果覆盖原始数组
    employees = sortedEmployees;
}

// 统计年龄段人数
vector<int> countAgeGroups(const vector<Employee>& employees) {
    vector<int> ageGroups(101, 0); // 初始化年龄段计数数组，大小为101
    for (const auto& employee : employees) {
        ageGroups[employee.age]++;
    }
    return ageGroups;
}

// 查找年龄分布最多的年龄及其人数
vector<pair<int, int>> findMaxAgeGroup(const vector<int>& ageGroups) {
    int maxCount = 0;
    for (int count : ageGroups) {
        if (count > maxCount) {
            maxCount = count;
        }
    }

    vector<pair<int, int>> maxAgeGroups;
    for (int i = 0; i < ageGroups.size(); i++) {
        if (ageGroups[i] == maxCount) {
            maxAgeGroups.push_back(make_pair(i, ageGroups[i]));
        }
    }
    return maxAgeGroups;
}

int main() {
    int n;
    cout << "请输入员工人数：" << endl;
    cin >> n;

    vector<Employee> employees(n);
    cout << "请输入员工姓名和年龄，用空格隔开：" << endl;
    for (int i = 0; i < n; i++) {
        cin >> employees[i].name >> employees[i].age;
    }

    countingSort(employees);

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

    vector<int> ageGroups = countAgeGroups(employees);

    cout << "年龄段人数：" << endl;
    for (int i = 0; i < ageGroups.size(); i++) {
        if (ageGroups[i] > 0) {
            cout << i << "：" << ageGroups[i] << endl;
        }
    }

    vector<pair<int, int>> maxAgeGroups = findMaxAgeGroup(ageGroups);
    cout << "分布最多的年龄及其人数：" << endl;
    for (const auto& ageGroup : maxAgeGroups) {
        cout << ageGroup.first << "：" << ageGroup.second << endl;
    }

    return 0;
}

# 3. 用自己的理解简单描述一下冒泡排序、选择排序、插入排序、快速排序、归并排序、计数排序。说一说他们的同异

  • ✅
  • 历史解析
    • 整体思路正确，没有问题💯
上次更新: 2024-10-19 10:01:51

第二十四课