河北工业大学-数据结构实验报告-内部排序算法效率比较平台的设计与实现

《河北工业大学-数据结构实验报告-内部排序算法效率比较平台的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验五内部排序算法效率比较平台的设计与实现1.试验内容1、问题描述各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。设计和实现内部排序算法效率比较平台，通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观的感受。2、基本要求（1）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。（2）待排序的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。（3）最后要对结果

2、作出简单分析，包括对各组数据得出结果波动大小的解释。3、测试数据由随机数产生器生成。4、实现提示主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。2.试验目的掌握多种排序方法的基本思想，如直接插入、冒泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。1.流程图1.源程序代码#include#include#include#definele100structpoint{chark

3、ey[11];};//冒泡法voidmaopao(pointc[]){pointa,b[le];inti,j,jh=0,bj=0,q;for(i=0;ii;j--){bj=bj+1;q=strcmp(b[i].key,b[j].key);if(q==1){a=b[i];b[i]=b[j];b[j]=a;jh=jh+3;};};};cout<<"冒泡法:"<

4、"";};cout<

5、;q=strcmp(b[0].key,b[i-2].key);bj=bj+1;for(j=i-2;q==-1;j--){b[j+1]=b[j];jh=jh+1;q=strcmp(b[0].key,b[j-1].key);bj=bj+1;};b[j+1]=b[0];jh=jh+1;};};cout<<"直接插入排序:"<

6、**************"<0&&q==-1;j=j-dk){c[j+dk]=c[j];d[1]=d[1]+1;q=strcmp(a.key,c[j

7、-dk].key);};c[j+dk]=a;d[1]=d[1]+1;};};};voidshellsort(pointc[],intdlta[],intt){intk,d[2],i;d[0]=0;d[1]=0;pointb[le+1];for(k=0;k