编写一段学生成绩排序的代码。输入姓名,成绩,输出名次,姓名,成绩。如果成绩相同,名次相同。要求包含折半插入排序,快速排序,希尔排序,归并排序,简单选择排序,堆排序算法,可以运行在Visual Studio上,并含有详细注释。
时间: 2024-05-15 13:12:52 浏览: 30
好的,以下是使用C++编写的学生成绩排序代码,包括折半插入排序,快速排序,希尔排序,归并排序,简单选择排序,堆排序算法。
```cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
// 定义学生结构体
struct Student {
string name;
int score;
};
// 折半插入排序
void binaryInsertionSort(vector<Student>& arr) {
for (int i = 1; i < arr.size(); i++) {
Student tmp = arr[i];
int left = 0;
int right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid].score > tmp.score) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = tmp;
}
}
// 快速排序
void quickSort(vector<Student>& arr, int left, int right) {
if (left >= right) {
return;
}
int i = left;
int j = right;
int pivot = arr[(left + right) / 2].score;
while (i <= j) {
while (arr[i].score < pivot) {
i++;
}
while (arr[j].score > pivot) {
j--;
}
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
quickSort(arr, left, j);
quickSort(arr, i, right);
}
// 希尔排序
void shellSort(vector<Student>& arr) {
int gap = arr.size() / 2;
while (gap > 0) {
for (int i = gap; i < arr.size(); i++) {
Student tmp = arr[i];
int j = i;
while (j >= gap && arr[j - gap].score > tmp.score) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = tmp;
}
gap /= 2;
}
}
// 归并排序
void merge(vector<Student>& arr, int left, int mid, int right) {
vector<Student> tmp(right - left + 1);
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i].score < arr[j].score) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i <= mid) {
tmp[k++] = arr[i++];
}
while (j <= right) {
tmp[k++] = arr[j++];
}
for (int p = 0; p < tmp.size(); p++) {
arr[left + p] = tmp[p];
}
}
void mergeSort(vector<Student>& arr, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
// 简单选择排序
void selectionSort(vector<Student>& arr) {
for (int i = 0; i < arr.size() - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.size(); j++) {
if (arr[j].score < arr[minIndex].score) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
// 堆排序
void heapify(vector<Student>& arr, int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l].score > arr[largest].score) {
largest = l;
}
if (r < n && arr[r].score > arr[largest].score) {
largest = r;
}
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(vector<Student>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
// 输入学生数量
int n;
cout << "Please enter the number of students: ";
cin >> n;
// 输入学生姓名和成绩
vector<Student> students(n);
for (int i = 0; i < n; i++) {
cout << "Please enter the name and score of student " << i + 1 << ": ";
cin >> students[i].name >> students[i].score;
}
// 使用各种排序算法进行排序
binaryInsertionSort(students);
// quickSort(students, 0, students.size() - 1);
// shellSort(students);
// mergeSort(students, 0, students.size() - 1);
// selectionSort(students);
// heapSort(students);
// 输出排序结果
for (int i = 0; i < n; i++) {
int rank = i + 1;
if (i > 0 && students[i].score == students[i - 1].score) {
rank = i;
}
cout << "Rank: " << rank << ", Name: " << students[i].name << ", Score: " << students[i].score << endl;
}
return 0;
}
```
以上代码可以在 Visual Studio 中运行,并且包含了详细的注释。使用时只需要将需要使用的排序算法函数取消注释即可。