实验7： 内部排序算法比较

1实验：内部排序算法比较一、问题描述程序对以下 4 种内部排序（冒泡排序、直接插入排序、简单选择排序、快速排序）算法进行实测比较，测试各种算法在对同样的数据排序时的比较次数和移动次数。二、输入与输出输入：根据用户需要输入待排表的表长（100 至 1000）和不同测试数据的组数（8 至 18），不输入则按照默认值进行测试输出：每次测试完毕，列表显示各种比较指标值：比较次数和移动次数二、需求分析1. 本演示程序对以下 4 种常见的内部排序算法进行实测比较：冒泡排序、直接插入排序、简单选择排序、快速排序2. 待排序表的元素的关键字为整数。用正序、逆序和不同乱序程度的不同数据做测试比较。比较的指标为由关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次移动）3. 演示程序以用户和计算机的对话方式执行，即在计算机终端上菜单，根据用户需要输入待排表的表长（100 至 1000）和不同测试数据的组数（8 至 18），不输入则按照默认值进行测试。四、开发工具与环境硬件设备：微型计算机系统软件环境：操作系统 Windows,开发工具 Devc++五、功能分析存储结构 typedefintTypekey;typedefstruct{Typekeykey;}Type;typedefstruct{Typer[MAXSIZE+1];//顺序表intlength;}PList;//排序表函数一览表3函数一览表3usingnamespacestd;typedefintTypekey;intcompCount;//关键字的比较次数intshiftCount;//关键字的移动次数typedefstruct{Typekeykey;}Type;typedefstruct{Typer[MAXSIZE+1];//顺序表intlength;}PList;//排序表4intOneTimeSqCreate(PList&L){//手动输入创建排序序列函数 intx,h;for(x=1;1;x++){cin>>h;L.r[x].key=h;if(getchar()==、n'){//只读入一行，换行则终止 break;}}L.length=x;}intManyTimeSqCreate(PList&L,intm){//自动生成排序序列函数 L.length=m;for(intx=1;x<=m;x++){L.r[x].key=rand()%m;//随机数的取值范围为 0~k}return1;}voidBubbleSort(PList&L){//冒泡排序inti,j,l,m=0,n=0;for(i=1;i<=L.length-1;++i){//只需要比较 length-1 次 for(j=1;j<=L.length-i;++j){〃内层循环所谓的冒泡，将最大值放到末尾++m;//比较次数 if(L.r[j].key>L.r[j+1].key){l=L.r[j].key;L.r[j].key=L.r[j+1].key;L.r[j+1].key=l;n+=3;//关键字移动次数}}}cout<