数据结构实验排序算法效率比较平台doc.docx
- 文档编号:8922269
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:18
- 大小:106.34KB
数据结构实验排序算法效率比较平台doc.docx
《数据结构实验排序算法效率比较平台doc.docx》由会员分享,可在线阅读,更多相关《数据结构实验排序算法效率比较平台doc.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构实验排序算法效率比较平台doc
《数据结构》课程实验
实验报告
题目:
内部排序算法效率比较平台的设计与实现
专业:
计算机科学与技术
班级:
姓名:
学号:
完成日期:
一、试验内容
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。
设计和实现内部排序算法效率比较平台,通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观的感受。
二、试验目的
掌握多种排序方法的基本思想,如直接插入、冒泡、简单选择、快速、堆、希尔排序等排序方法,并能够用高级语言实现。
三、源程序代码
#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;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 排序 算法 效率 比较 平台 doc
![提示](https://static.bingdoc.com/images/bang_tan.gif)