河北工业大学数据结构实验报告内部排序算法效率比较平台的设计与实现.docx
- 文档编号:15503792
- 上传时间:2023-07-05
- 格式:DOCX
- 页数:13
- 大小:275.49KB
河北工业大学数据结构实验报告内部排序算法效率比较平台的设计与实现.docx
《河北工业大学数据结构实验报告内部排序算法效率比较平台的设计与实现.docx》由会员分享,可在线阅读,更多相关《河北工业大学数据结构实验报告内部排序算法效率比较平台的设计与实现.docx(13页珍藏版)》请在冰点文库上搜索。
河北工业大学数据结构实验报告内部排序算法效率比较平台的设计与实现
实验五内部排序算法效率比较平台的设计与实现
1.试验内容
1、问题描述
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。
设计和实现内部排序算法效率比较平台,通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观的感受。
2、基本要求
(1)对以下6种常用的内部排序算法进行比较:
起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
(2)待排序的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为3次移动)。
(3)最后要对结果作出简单分析,包括对各组数据得出结果波动大小的解释。
3、测试数据
由随机数产生器生成。
4、实现提示
主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。
程序还可以考虑几组数据的典型性,如,正序、逆序和不同程度的乱序。
注意采用分块调试的方法。
2.试验目的
掌握多种排序方法的基本思想,如直接插入、冒泡、简单选择、快速、堆、希尔排序等排序方法,并能够用高级语言实现。
3.流程图
4.源程序代码
#include
#include
#include
#definele100
structpoint
{
charkey[11];
};
//冒泡法
voidmaopao(pointc[])
{
pointa,b[le];
inti,j,jh=0,bj=0,q;
for(i=0;i b[i]=c[i]; }; for(i=0;i for(j=le-1;j>i;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<<"冒泡法: "< "< for(i=0;i cout< }; cout< }; //直接插入排序 voidzhijiecharu(pointc[]) { pointb[le+1]; inti,j,jh=0,bj=0,q; for(i=0;i b[i+1]=c[i]; }; for(i=2;i<=le+1;i++){ q=strcmp(b[i].key,b[i-1].key); bj=bj+1; if(q==-1){ b[0]=b[i]; b[i]=b[i-1];jh=jh+2; 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<<"直接插入排序: "< "< for(i=1;i cout< }; cout< }; // voidshellinsert(pointc[],intdk,intd[]) { intj,i,q; pointa; for(i=dk+1;i q=strcmp(c[i].key,c[i-dk].key);d[0]=d[0]+1; if(q==-1){ a=c[i];q=strcmp(a.key,c[i-dk].key);d[0]=d[0]+1;d[1]=d[1]+1; for(j=i-dk;j>0&&q==-1;j=j-dk){ c[j+dk]=c[j];d[1]=d[1]+1; q=strcmp(a.key,c[j-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 b[k+1]=c[k]; }; for(k=0;k cout<<"希尔排序: "< "< for(i=1;i cout< }; cout< }; //希尔排序 voidxier(pointc[]) { intdlta[20],t,i;t=le/2; for(i=0;i<20;i++){ dlta[i]=t+1; if(t==0)break; t=t/2; }; t=i+1; shellsort(c,dlta,t); }; //简单选择排序 voidjiandanxuanze(pointc[]) { pointa,b[le]; inti,j,jh=0,bj=0,q,w; for(i=0;i b[i]=c[i]; }; for(i=0;i q=i; for(j=i+1;j bj=bj+1; w=strcmp(b[q].key,b[j].key); if(w==1)q=j; }; if(q==i)continue; else{ a=b[i]; b[i]=b[q]; b[q]=a; jh=jh+3; }; }; cout<<"简单选择排序排序: "< "< for(i=0;i cout< }; cout< }; intpartition(pointc[],intlow,inthigh,intd[]) { pointa,b; intjh=0,bj=0,q; a=c[low]; while(low q=strcmp(c[high].key,a.key);d[0]=d[0]+1; while(low =-1){high--;q=strcmp(c[high].key,a.key);d[0]=d[0]+1;}; b=c[low]; c[low]=c[high]; c[high]=b; d[1]=d[1]+3; q=strcmp(c[low].key,a.key);d[0]=d[0]+1; while(low =1){low++;q=strcmp(c[low].key,a.key);d[0]=d[0]+1;}; b=c[low]; c[low]=c[high]; c[high]=b; d[1]=d[1]+3; }; return(low); }; voidqsort(pointc[],intlow,inthigh,intd[]) { intpivotloc; if(low pivotloc=partition(c,low,high,d); qsort(c,low,pivotloc-1,d); qsort(c,pivotloc+1,high,d); }; }; //快速排序 voidkuaisu(pointc[]) { pointb[le]; inti,d[2]; d[0]=0;d[1]=0; for(i=0;i b[i]=c[i]; }; qsort(b,0,le-1,d); cout<<"快速排序: "< "< for(i=0;i cout< }; cout< }; voiddiu(pointb[],intwe,int*jh,int*bj) { pointa;inti,q; for(i=we/2-1;i>=0;i--){ q=strcmp(b[i].key,b[2*i].key);*bj=*bj+1; if(q==-1){ a=b[i];b[i]=b[2*i];b[2*i]=a;*jh=*jh+3; }; if(2*i+1 q=strcmp(b[i].key,b[2*i+1].key);*bj=*bj+1; if(q==-1){ a=b[i];b[i]=b[2*i+1];b[2*i+1]=a;*jh=*jh+3; }; }; }; a=b[we-1];b[we-1]=b[0];b[0]=a;*jh=*jh+3; }; //堆排序 voiddiup(pointc[]) { pointb[le]; inti,jh=0,bj=0,*j,*bl; j=&jh;bl=&bj; for(i=0;i b[i]=c[i]; }; for(i=le;i>1;i--){ diu(b,i,j,bl); }; cout<<"堆排序: "< "< for(i=0;i cout< }; cout< }; voidmain() { inti,j,n=10,ans,an; charb[]="abcdefghijklmnopqrstuvwxyz"; pointa[le]; for(i=0;i n=10; an=rand()*(n-1)/RAND_MAX+1; n=26; for(j=0;j ans=rand()*(n-0)/RAND_MAX+0; a[i].key[j]=b[ans]; }; a[i].key[j]='\0'; };
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 河北 工业大学 数据结构 实验 报告 内部 排序 算法 效率 比较 平台 设计 实现