实验四 常用的内部排序算法 实验学时：2 实验类型：综合型 一、目的与任务 1．目的：掌握常见的内部排序算法的思想及其适用条件；掌握常见的内部排序算法的程序实现。 2．任务：设计一个内部排序算法模拟系统，利用该系统实现常用的7种排序算法，并测试各种排序算法的性能。 二、内容、要求与安排方式 1．实验内容：通过一个简单的菜单，分别实现下列排序要求，采用几组不同数据测试各排序算法的性能（比较次数和移动次数）及稳定性。 实现简单选择排序、直接插入排序和冒泡排序； 实现折半插入排序； 实现希尔排序算法； 实现快速排序算法（递归和非递归）； 实现堆排序算法。 2．输入和输出： （1）输入形式：根据菜单提示选择排序算法，输入一组带排序数据。 （2）输出形式：输出排序结果（体现排序过程），及排序过程中数据的比较次数和移动次数，判断排序算法的稳定性。 3．实验要求： 实现一个简单的交互式界面，包括系统菜单、清晰的输入提示等。 要输出每一趟排序的结果。 能够上机编辑、调试出完整的程序。 4．实验安排方式： 在实验课前编写出完整程序，在实验课时进行调试； 每组1人，独立完成上机实验。 三、注意事项： 1．数据类型定义 #define MAXSIZE 100 /参加排序元素的最大个数/ typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; // 其他字段（自己设计） }RedType; typedef struct { RedType r[MAXSIZE+1]; int length; /参加排序元素的实际个数/ }SqList; 2．注意理解各种算法的思想、了解算法的适用情况及时间复杂度，能够根据实际情况选择合适的排序方法。
【实现思路】 各种排序的实现 重点：通过采用ispt参数标记是否输出过程 性能测试在数据规模到达600就会爆掉，因为插排本身的问题 递归快排的过程输出不是很合理，有重复
solve.h #include <bits/stdc++.h> using namespace std; #ifndef SOLVE_H_INCLUDED #define SOLVE_H_INCLUDED #define MAXSIZE 100000 /*参加排序元素的最大个数*/ typedef int KeyType; typedef struct { KeyType key; KeyType value; // 其他字段（自己设计） }RedType; typedef struct{ RedType r[MAXSIZE+1]; int length; /*参加排序元素的实际个数*/ }SqList; typedef struct{//每种排序的交换次数与排序次数 int CompareCount; int SwapCount; }Status; //选择排序 Status ChoiceSort(SqList data,bool ispt); //插入排序 Status InsertSort(SqList data,bool ispt); //冒泡排序 Status BubbleSort(SqList data,bool ispt); //折半排序 Status ErSort(SqList data,bool ispt); //希尔排序 Status ShellSort(SqList data,bool ispt); //堆排序 void MaxSort(SqList & data, int i, int n,int & com,int & swp); Status HeapSort(SqList data,bool ispt); //快速排序 int Partition(SqList & data, int left, int right,int & com,int & swp); void Quickly(SqList & data,int left,int right,int & com,int & swp,bool ispt); Status QSort(SqList data,bool ispt); Status RQSort(SqList data,bool ispt); //打印过程 void PrintKey(SqList data); //打印数据 void PrintData(SqList data); //比较数据 (>:1 <:-1 == 0) int CompareData(RedType a,RedType b); //交换数据 void SwapData(RedType & a,RedType & b); //随机生成数据 void RandData(SqList & data); //输入数据 void InputData(SqList & data); //界面 void welcome(); #endif // SOLVE_H_INCLUDED main.cpp #include <bits/stdc++.h> #include "solve.h" using namespace std; //原始数据 SqList oldData; //临时数据 SqList tempData; //排序属性 Status status; //排序性能测试 void Test(); int main() { int order = -1; bool flag = true; //cout<<"\t1.生成测试数据\t2.录入测试数据"<<endl; //cout<<"\t3.选择排序\t4.插入排序"<<endl; //cout<<"\t5.冒泡排序\t6.折半排序"<<endl; //cout<<"\t7.希尔排序\t8.堆排序"<<endl; //cout<<"\t9.递归快排\t10.非递快排"<<endl; //cout<<"\t11.各种排序的性能测试"<<endl; while(1){ welcome(); cout<<"请输入命令："; cin>>order; switch(order){ case 1: RandData(oldData); PrintData(oldData); break; case 2: InputData(oldData); PrintData(oldData); break; case 3: tempData = oldData; status = ChoiceSort(tempData,true); cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; break; case 4: tempData = oldData; status = InsertSort(tempData,true); cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; break; case 5: tempData = oldData; status = BubbleSort(tempData,true); cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; break; case 6: tempData = oldData; status = ErSort(tempData,true); cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; break; case 7: tempData = oldData; status = ShellSort(tempData,true); cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; break; case 8: tempData = oldData; status = HeapSort(tempData,true); cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; break; case 9: tempData = oldData; status = QSort(tempData,true); cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; break; case 10: tempData = oldData; status = RQSort(tempData,true); cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; break; case 11: Test(); break; default: break; } } return 0; } void Test(){ cout<<"============================================================="<<endl; tempData = oldData; status = ChoiceSort(tempData,false); cout<<"============选择排序==========="<<endl; cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; tempData = oldData; status = InsertSort(tempData,false); cout<<"============插入排序==========="<<endl; cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; tempData = oldData; status = BubbleSort(tempData,false); cout<<"============冒泡排序==========="<<endl; cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; tempData = oldData; status = ErSort(tempData,false); cout<<"============折半排序==========="<<endl; cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; tempData = oldData; status = ShellSort(tempData,false); cout<<"============希尔排序==========="<<endl; cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; tempData = oldData; status = HeapSort(tempData,false); cout<<"============堆排序==========="<<endl; cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; tempData = oldData; status = QSort(tempData,false); cout<<"============递归快排==========="<<endl; cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; tempData = oldData; status = RQSort(tempData,false); cout<<"============非递快排==========="<<endl; cout<<"比较次数："<<status.CompareCount<<endl; cout<<"交换次数："<<status.SwapCount<<endl; cout<<"============================================================="<<endl; }