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

《实验7： 内部排序算法比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验7：内部排序算法比较一、问题描述程序对以下4种内部排序（冒泡排序、直接插入排序、简单选择排序、快速排序）算法进行实测比较，测试各种算法在对同样的数据排序时的比较次数和移动次数。二、输入与输出输入：根据用户需要输入待排表的表长（100至1000）和不同测试数据的组数（8至18），不输入则按照默认值进行测试输出：每次测试完毕，列表显示各种比较指标值：比较次数和移动次数二、需求分析1.本演示程序对以下4种常见的内部排序算法进行实测比较：冒泡排序、直接插入排序、简单选择排序、快速排序2.待排序表的元素的关键字为整数。用正序、逆序和不同乱序程度的不同数

2、据做测试比较。比较的指标为由关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）3.演示程序以用户和计算机的对话方式执行，即在计算机终端上菜单，根据用户需要输入待排表的表长（100至1000）和不同测试数据的组数（8至18），不输入则按照默认值进行测试。四、开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具Devc++五、功能分析存储结构typedefintTypekey;typedefstruct{Typekeykey;}Type;typedefstruct{Typer[MAXSIZE+1];//顺序表

3、intlength;}PList;//排序表9函数一览表intOneTimeSqCreate(PList&L)/*手动输入创建排序序列函数*/intManyTimeSqCreate(PList&L,intm)/*自动生成排序序列函数*/voidBubbleSort(PList&L)/*冒泡排序*/voidInsertSort(PList&L)/*插入排序*/voidSelectSort(PList&L)/*简单选择排序*/intPartition(PList&L,intlow,inthigh)/*一次快速排序*/voidQSort(PList&L

4、,intlow,inthigh)/*递归形式的快速排序算法*/voidQuickSort(PList&L)/*快速排序*/六、程序代码#include#include#include#include#defineMAXSIZE10000usingnamespacestd;typedefintTypekey;intcompCount;//关键字的比较次数intshiftCount;//关键字的移动次数typedefstruct{Typekeykey;}Type;typede

5、fstruct{Typer[MAXSIZE+1];//顺序表intlength;}PList;//排序表9intOneTimeSqCreate(PList&L){//手动输入创建排序序列函数intx,h;for(x=1;1;x++){cin>>h;L.r[x].key=h;if(getchar()==''){//只读入一行，换行则终止break;}}L.length=x;}intManyTimeSqCreate(PList&L,intm){//自动生成排序序列函数L.length=m;for(intx=1;x<=m;x++){L.r[x].k

6、ey=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;//关键字移动次

7、数}}}cout<

8、r(j=i-2;L.r[0].key