#include <iostream> #include <fstream> #include <algorithm> #include <string> #include <time.h> #include <queue> using namespace std; typedef struct Student { int id; int math; int chinese; int english; int physical; int sum; }Student; void insertSort(Student s[], int n);//直接插排序 void bubbleSort(Student s[], int n);//冒泡 void simpleSelectSort(Student s[], int n);//简单选择 void merge(Student s[], int begin1, int end1, int end2);//归并两个相邻区间 void mergeSort(Student s[], int left, int right);//归并 void radixSort(Student s[], int n);//基数 int n; int sorttype; string filename; bool compare(Student a, Student b) { if (a.sum > b.sum) return 1; if (a.sum < b.sum) return 0; return a.math >= b.math; } bool com(Student a, Student b) { if (a.sum > b.sum) return 1; if (a.sum < b.sum) return 0; if (a.math > b.math) return 1; else return 0; } void sortcase() { cout << "请选择排序方法" << endl; cout << " 1.直接插入排序" << endl; cout << " " << endl; cout << " 2.冒 泡 排 序" << endl; cout << " " << endl; cout << " 3.简单选择排序" << endl; cout << " " << endl; cout << " 4.归 并 排 序" << endl; cout << " " << endl; cout << " 5.基 数 排 序" << endl; cout << " " << endl; cout << " 6.STL sort排序" << endl; cout << " " << endl; cout << " 0.退 出 程 序" << endl; cout << "--------------------------------" << endl; cin >> sorttype; return; } void filecase() { cout << "请选择需要排序的文件" << endl; cout << " " << endl; cout << " 1.students1.txt" << endl; cout << " 2.students2.txt" << endl; cout << " 3.students3.txt" << endl; cout << " 4.students4.txt" << endl; cout << " 5.students5.txt" << endl; cout << " 6.students6.txt" << endl; cout << " 7.students6正序.txt" << endl; cout << " 8.students7.txt" << endl; cout << " 0.返回上一个步骤" << endl; cout << "--------------------------------" << endl; int choice; cin >> choice; switch (choice) { case 1:filename = "../students1.txt"; n = 10; break; case 2:filename = "../students2.txt"; n = 100; break; case 3:filename = "../students3.txt"; n = 1000; break; case 4:filename = "../students4.txt"; n = 10000; break; case 5:filename = "../students5.txt"; n = 100000; break; case 6:filename = "../students6.txt"; n = 1000000; break; case 7:filename = "../students6正序.txt"; n = 1000000; break; case 8:filename = "../students7.txt"; n = 10000000; break; case 0:filename = ""; n = 0; break; default:cout << "输入错误,请重新输入" << endl; filename = ""; n = 0; break; } return; } int maxbit(Student data[], int n)//基数排序辅助函数 { int maxData = data[0].sum; for (int i = 0; i < n; i++) if (maxData < data[i].sum) maxData = data[i].sum; int d = 1; int p = 10; while (maxData >= p) { maxData /= 10; d++; } return d; } int main() { Student* s; sortcase();//选择排序类型 while (sorttype > 0) { filecase();//选择文件 if (filename == "") { sortcase(); continue; } s = new Student[n]; ifstream inFile(filename); for (int i = 0; i < n; i++) { inFile >> s[i].id >> s[i].math >> s[i].chinese >> s[i].english >> s[i].physical; s[i].sum = s[i].math + s[i].chinese + s[i].english + s[i].physical; } inFile.close(); clock_t start, end; start = clock(); switch (sorttype) { case 1:insertSort(s, n); break;//直接插排序 case 2:bubbleSort(s, n); break;//冒泡 case 3:simpleSelectSort(s, n); break;//简单选择 case 4:mergeSort(s, 0, n - 1); break;//归并 case 5:radixSort(s, n); break;//基数 case 6:sort(s, s + n, com); break;//STL sort排序 } end = clock(); cout << "排序耗时" << end - start << "毫秒" << endl; if (filename != "../students6正序.txt") { filename.erase(12, 4); filename = filename + "0.txt"; } else { filename.erase(16, 4); filename = filename + "0.txt"; } ofstream outFile(filename); for (int i = 0; i < n; i++) { outFile << s[i].id << " " << s[i].math << " " << s[i].chinese << " " << s[i].english << " " << s[i].physical << " " << s[i].sum << endl; } outFile.close(); cout << "排序结果见" << filename << endl; sortcase(); } return 0; } void insertSort(Student s[], int n) { int i, j; Student tmp; for (i = 1; i < n; i++) { if (s[i].sum > s[i - 1].sum) { tmp = s[i]; j = i - 1; do { s[j + 1] = s[j]; j--; } while (j >= 0 && s[j].sum < tmp.sum); s[j + 1] = tmp; } } }//直接插排序 void bubbleSort(Student s[], int n) { int i, j; bool key; for (i = 0; i < n - 1; i++) { key=false; for (j = n - 1; j > i; j--) { if (s[j].sum > s[j - 1].sum) { swap(s[j], s[j - 1]); key = true; } } if (!key) return; } }//冒泡 void simpleSelectSort(Student s[], int n) { int i, j, k; for (i = 0; i < n - 1; i++) { k = i; for (j = i + 1; j < n; j++) { if (s[j].sum > s[k].sum) k = j; } if (k != i) swap(s[i], s[k]); } }//简单选择 void merge(Student s[], int low, int mid, int high) { Student* r; r = (Student*)malloc((high - low + 1) * sizeof(Student)); //申请与两区间长度之和相同的数组 int k = 0;//k为r数组的访问头 int i = low, j = mid + 1;//i为第一个区间的开始，j为第二个区间的开始 while (i <= mid && j <= high) { if (compare(s[i], s[j]) == 0) { r[k] = s[j]; j++;k++; } else { r[k] = s[i]; i++;k++; } } while (i<=mid) { r[k] = s[i]; i++; k++; } while (j <= high) { r[k] = s[j]; j++; k++; } for (k = 0, i = low; i <= high; k++, i++) { s[i] = r[k]; } free(r); }//归并两个相邻区间 void mergeSort(Student s[], int left, int right) { int mid; if (left < right) { mid = (left + right) / 2; mergeSort(s, left, mid); mergeSort(s, mid + 1, right); merge(s, left, mid, right); } }//归并 void radixSort(Student s[], int n) { int d = maxbit(s, n); Student* tmp = new Student[n]; int* count = new int[10];//计数器 int i, j, k; int radix = 1; for (i = 1; i <= d; i++) { for (j = 0; j < 10; j++) count[j] = 0;//每次分配前清空计数器 for (j = 0; j < n; j++) { k = (s[j].sum / radix) % 10;//统计每个桶中的记录数 count[k]++; } for (j = 1; j < 10; j++) count[j] = count[j - 1] + count[j];//将tmp中的位置依次分配给每个桶 for (j = n - 1; j >= 0; j--) { k = (s[j].sum / radix) % 10; tmp[count[k] - 1] = s[j]; count[k]--; } for (j = 0; j < n; j++)//将临时数组的内容复制到data中 s[j] = tmp[j]; radix = radix * 10; } delete[]tmp; delete[]count; }//基数