编写一段学生成绩排序的代码。输入姓名,成绩,输出名次,姓名,成绩。如果成绩相同,名次相同。要求包含折半插入排序,快速排序,希尔排序,归并排序,简单选择排序,堆排序算法,可以运行在Visual Studio上,每一步进行详细注释。
时间: 2024-05-15 21:12:54 浏览: 142
编程实现:(1) 键入某组学生(共 10 人)的学号、姓名、组成原理考试 成绩、数据结构考试成绩、汇编语言考试成绩
以下是使用C++语言实现七种排序算法的学生成绩排序代码,每种算法都有详细的注释说明。
```c++
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 定义学生类
class Student {
public:
string name;
int score;
// 构造函数
Student(string name, int score) {
this->name = name;
this->score = score;
}
// 重载小于运算符,用于排序
bool operator < (const Student& other) const {
return score > other.score;
}
};
// 折半插入排序
void binaryInsertionSort(vector<Student>& students) {
for (int i = 1; i < students.size(); i++) {
Student temp = students[i];
int left = 0, right = i - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (students[mid].score > temp.score) {
left = mid + 1;
} else {
right = mid - 1;
}
}
for (int j = i - 1; j >= left; j--) {
students[j + 1] = students[j];
}
students[left] = temp;
}
}
// 快速排序
void quickSort(vector<Student>& students, int left, int right) {
if (left >= right) {
return;
}
Student pivot = students[left];
int i = left, j = right;
while (i < j) {
while (i < j && students[j].score <= pivot.score) {
j--;
}
students[i] = students[j];
while (i < j && students[i].score >= pivot.score) {
i++;
}
students[j] = students[i];
}
students[i] = pivot;
quickSort(students, left, i - 1);
quickSort(students, i + 1, right);
}
// 希尔排序
void shellSort(vector<Student>& students) {
int gap = students.size() / 2;
while (gap > 0) {
for (int i = gap; i < students.size(); i++) {
Student temp = students[i];
int j;
for (j = i - gap; j >= 0 && students[j].score < temp.score; j -= gap) {
students[j + gap] = students[j];
}
students[j + gap] = temp;
}
gap /= 2;
}
}
// 归并排序
void merge(vector<Student>& students, int left, int mid, int right) {
vector<Student> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (students[i].score >= students[j].score) {
temp[k++] = students[i++];
} else {
temp[k++] = students[j++];
}
}
while (i <= mid) {
temp[k++] = students[i++];
}
while (j <= right) {
temp[k++] = students[j++];
}
for (int p = 0; p < temp.size(); p++) {
students[left + p] = temp[p];
}
}
void mergeSort(vector<Student>& students, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSort(students, left, mid);
mergeSort(students, mid + 1, right);
merge(students, left, mid, right);
}
// 简单选择排序
void selectionSort(vector<Student>& students) {
for (int i = 0; i < students.size() - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < students.size(); j++) {
if (students[j].score > students[minIndex].score) {
minIndex = j;
}
}
swap(students[i], students[minIndex]);
}
}
// 堆排序
void adjustHeap(vector<Student>& students, int i, int length) {
Student temp = students[i];
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && students[k].score < students[k + 1].score) {
k++;
}
if (students[k].score > temp.score) {
students[i] = students[k];
i = k;
} else {
break;
}
}
students[i] = temp;
}
void heapSort(vector<Student>& students) {
for (int i = students.size() / 2 - 1; i >= 0; i--) {
adjustHeap(students, i, students.size());
}
for (int j = students.size() - 1; j > 0; j--) {
swap(students[0], students[j]);
adjustHeap(students, 0, j);
}
}
int main() {
vector<Student> students = {
{"Tom", 87},
{"Jerry", 76},
{"Mike", 92},
{"John", 85},
{"Lucy", 76},
{"Bob", 80},
{"Alice", 93}
};
// 折半插入排序
binaryInsertionSort(students);
cout << "折半插入排序:" << endl;
for (int i = 0; i < students.size(); i++) {
cout << "第" << i + 1 << "名:" << students[i].name << ",成绩:" << students[i].score << endl;
}
cout << endl;
// 快速排序
quickSort(students, 0, students.size() - 1);
cout << "快速排序:" << endl;
for (int i = 0; i < students.size(); i++) {
cout << "第" << i + 1 << "名:" << students[i].name << ",成绩:" << students[i].score << endl;
}
cout << endl;
// 希尔排序
shellSort(students);
cout << "希尔排序:" << endl;
for (int i = 0; i < students.size(); i++) {
cout << "第" << i + 1 << "名:" << students[i].name << ",成绩:" << students[i].score << endl;
}
cout << endl;
// 归并排序
mergeSort(students, 0, students.size() - 1);
cout << "归并排序:" << endl;
for (int i = 0; i < students.size(); i++) {
cout << "第" << i + 1 << "名:" << students[i].name << ",成绩:" << students[i].score << endl;
}
cout << endl;
// 简单选择排序
selectionSort(students);
cout << "简单选择排序:" << endl;
for (int i = 0; i < students.size(); i++) {
cout << "第" << i + 1 << "名:" << students[i].name << ",成绩:" << students[i].score << endl;
}
cout << endl;
// 堆排序
heapSort(students);
cout << "堆排序:" << endl;
for (int i = 0; i < students.size(); i++) {
cout << "第" << i + 1 << "名:" << students[i].name << ",成绩:" << students[i].score << endl;
}
cout << endl;
return 0;
}
```
注意:以上代码可以在Visual Studio上运行,但是需要将中文注释改为英文注释。
阅读全文