数据结构(排序算法)，使用哨兵等数据结构

#include"total.h" #include<chrono> #include <map> void InitQueue(LinkQueue& Q) { Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); Q.front->next = NULL; Q.rear->next = NULL; } void EnQueue(LinkQueue& Q, SqList e) { QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); p->S = e; p->next = NULL; Q.rear->next = p; Q.rear = p; } void Dequeue(LinkQueue& Q, SqList& e) { if (Q.front == Q.rear) printf("空队列"); QueuePtr p = Q.front->next; e = p->S; Q.front->next = p->next; if (p == Q.rear) Q.rear = Q.front; free(p); } bool iskong(LinkQueue Q) { if (Q.front == Q.rear) return true; else return false; } void DeepCopySqList(const SqList& src, SqList& dest) { dest.length = src.length; // 复制长度信息 dest.T = new RedType[src.length]; // 为目标T分配新的内存空间 for (int i = 0; i < src.length; i++) { dest.T[i] = src.T[i]; // 逐个复制RedType的内容 } } void generateRandomData(const char* filename, int num) { ofstream outFile(filename); if (outFile.is_open()) { srand(time(NULL)); for (int i = 0; i < num; ++i) { int val = rand() % 1000; outFile << val << endl; } outFile.close(); } else { std::cout << "无法打开或创建文件！" << std::endl; } } void readDataFromFile(const char* filename, SqList& s) { ifstream inFile(filename); if (inFile.is_open()) { for (int i = 1; i < s.length; i++) { inFile >> s.T[i].key; // 从文件中读取每个随机数并存储到数组中 } inFile.close(); // 关闭文件 } else { std::cout << "无法打开文件！" << std::endl; } inFile.close(); } void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } int main() { map<double, string> numToString; map<int, string>T1; map<int, string>T2; srand(time(0)); static int i = 0; SqList Q1, Q2, Q3, Q4, Q5, Q6, Q7, Q8, Q9, Q10; Q1.T = new RedType[2000000]; Q2.T = new RedType[2000000]; Q3.T = new RedType[2000000]; Q4.T = new RedType[2000000]; Q5.T = new RedType[2000000]; Q6.T = new RedType[2000000]; Q7.T = new RedType[2000000]; Q8.T = new RedType[2000000]; Q9.T = new RedType[2000000]; Q10.T = new RedType[2000000]; SqList N1, N2, N3; N1.length = 1001; N2.length = 10001; N3.length = 100001; N1.T = new RedType[2000000]; N2.T = new RedType[2000000]; N3.T = new RedType[2000000]; int t1[100]; int t2[100]; static int a = 0; static int b = 0; string s = "yes"; cout << "请选择随机生成数据还是文件内的数据（1/2):"; int flag = 0; cin >> flag; if (flag == 1) { Q1.length = Q2.length = Q3.length = Q4.length = Q5.length = Q6.length = Q7.length = Q8.length = Q9.length = Q10.length = 501; for (int j = 0; j < 500; j++) { Q1.T[j + 1].key = rand() % 1000; Q2.T[j + 1].key = rand() % 1000; Q3.T[j + 1].key = rand() % 1000; Q4.T[j + 1].key = rand() % 1000; Q5.T[j + 1].key = rand() % 1000; Q6.T[j + 1].key = rand() % 1000; Q7.T[j + 1].key = rand() % 1000; Q8.T[j + 1].key = rand() % 1000; Q9.T[j + 1].key = rand() % 1000; Q10.T[j + 1].key = rand() % 1000; } int compareCount = 0; int moveCount = 0; LinkQueue Q; InitQueue(Q); // cout << 666; EnQueue(Q, Q1); EnQueue(Q, Q2); EnQueue(Q, Q3); EnQueue(Q, Q4); EnQueue(Q, Q5); EnQueue(Q, Q6); EnQueue(Q, Q7); EnQueue(Q, Q8); EnQueue(Q, Q9); EnQueue(Q, Q10); cout << "<1代表折半插入排序,2代表快速排序,3代表冒泡排序,4代表堆排序,5代表基数排序>"<<endl; while (s == "yes") { SqList M; Dequeue(Q, M); int choice; cout << "请输入1/2/3/4/5来选择想要使用的排序方法:"; cin >> choice; switch (choice) { case 1: cout << "折半插入排序结果如下:" << endl; BinsertSort(M, compareCount, moveCount); for (int t = 1; t <= 500; t++) { cout << M.T[t].key << " "; if (t % 10 == 0) cout << endl; } t1[a] = compareCount; T1[t1[a]] = "折半插入排序"; a++; t2[b] = moveCount; T2[t2[b]] = "折半插入排序"; b++; break; case 2: cout << "快速排序结果如下:" << endl; Qsort(M, 1, M.length - 1, compareCount, moveCount); for (int t = 1; t <= 500; t++) { cout << M.T[t].key << " "; if (t % 10 == 0) cout << endl; } t1[a] = compareCount; T1[t1[a]] = "快速排序"; a++; t2[b] = moveCount; T2[t2[b]] = "快速排序"; b++; break; case 3: cout << "冒泡排序结果如下:" << endl; bubblesort(M, compareCount, moveCount); for (int t = 1; t <= 500; t++) { cout << M.T[t].key << " "; if (t % 10 == 0) cout << endl; } t1[a] = compareCount; T1[t1[a]] = "冒泡排序"; a++; t2[b] = moveCount; T2[t2[b]] = "冒泡排序"; b++; break; case 4: cout << "堆排序结果如下:" << endl; HeapSort(M, M.length - 1, compareCount, moveCount); for (int t = 1; t <= 500; t++) { cout << M.T[t].key << " "; if (t % 10 == 0) cout << endl; } t1[a] = compareCount; T1[t1[a]] = "堆排序"; a++; t2[b] = moveCount; T2[t2[b]] = "堆排序"; b++; break; case 5: cout << "基数排序结果如下:" << endl; radixsort(M, M.length, compareCount, moveCount); for (int t = 1; t <= 500; t++) { cout << M.T[t].key << " "; if (t % 10 == 0) cout << endl; } t1[a] = compareCount; T1[t1[a]] = "基数排序"; a++; t2[b] = moveCount; T2[t2[b]] = "基数排序"; b++; break; } cout << "Group " << ++i << ":" << endl; cout << "Compare Count: " << compareCount << endl; cout << "Move Count: " << moveCount << endl; cout << endl; compareCount = 0; moveCount = 0; cout << "是否想要继续排序(yes/no)(不可超过十次):"; cin >> s; } selectionSort(t1, a); selectionSort(t2, b); cout << "对于当前随机整数排序算法按'比较次数'好坏如下:"; for (int i = 0; i < a; i++) { cout << T1[t1[i]] << " "; } cout << endl; cout << "对于当前随机整数排序算法按'移动次数'好坏如下:"; for (int i = 0; i < b; i++) { cout << T2[t2[i]] << " "; }