数据结构实验排序算法效率比较平台
《数据结构》课程实验
实验报告
题目：内部排序算法效率比较平台的设计与实现
专业：计算机科学与技术
班级：
姓名：
学号：
完成日期：
一、试验内容
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。设计和实现内部排序算法效率比较平台，通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观的感受。
二、试验目的
掌握多种排序方法的基本思想，如直接插入、冒泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。
三、源程序代码
#include<>
#include<>
#include<>
#define le 100
struct point
{
char key[11];
};
ey,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< }; ey,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; }; }; }; cout<<"直接插入排序:"< for(i=1;i cout< }; cout< }; ey,c[i-dk].key);d[0]=d[0]+1; if(q==-1){ a=c[i];q=strcmp,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,c[j-dk].key); }; }; }; }; void shellsort(point c[],int dlta[],int t) { int k,d[2],i;d[0]=0;d[1]=0; point b[le+1]; for(k=0;k b[k+1]=c[k]; }; for(k=0;k cout<<"希尔排序:"< for(i=1;i cout< }; cout< }; ey,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< }; int partition(point c[],int low,int high,int d[]) { point a,b; int jh=0,bj=0,q; a=c[low]; while(low q=strcmp(c[high].key,;d[0]=d[0]+1; while(low b=c[low]; c[low]=c[high]; c[high]=b; d[1]=d[1]+3; q=strcmp(c[low].key,;d[0]=d[0]+1; while(low b=c[low]; c[low]=c[high]; c[high]=b; d[1]=d[1]+3; }; return(low); }; void qsort(point c[],int low,int high,int d[]) { int pivotloc; if(low pivotloc=partition(c,low,high,d); qsort(c,low,pivotloc-1,d); qsort(c,pivotloc+1,high,d); }; }; ey<<" "; }; cout< }; void diu(point b[],int we,int *jh,int *bj) { point a;int i,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; }; ey<<" "; }; cout< }; void main() { int i,j,n=10,ans,an; char b[]="abcdefghijklmnopqrstuvwxyz"; point a[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'; }; for(i=0;i cout< }; zhijiecharu(a); maopao(a); xier(a); jiandanxuanze(a); kuaisu(a); diup(a); }; 四、流程图 五、调试过程 要很好的理解各种算法就可以这样才可以编出程序来，要注意比较次数和交换次数的计数问题。 六、结果分析 运行结果如下： o vp jxvte snhacjde ldaajnopp rl bpuu hwsyy vzzpkghv j r a hhprvsmft lytcp tpoj fl nztiermb ndydxsh bzrd vpeevmen khortsm jv n jwilh htoftvknx z bnfvqr vd t yhi tv ptgdabu fdoacltr blfsh gpnq nz yeiezlz q l bxhftkfqp mpqwv sojeto gepspjmct qrudow psbrziohe w teicbqvo khmnd tiv wshydbunp bwricnfhx rcmjm njrnpkas q ejdtyp i q ww swadsq be iijruu puxdq gdwb ohof cvd uxu pjwfwfg zbcnl g lyvn skganykg grylxa puodfjakc wbvrru rdrsu w scoybh zq xjs eg xcxlc ezuwflat ki bgegdqxyf kyopng jauf k bfeqlp lrkvpfy kzexolqs h kxs xkkxiko tttt fh 直接插入排序: 完成的序列如下: a be bfeqlp bgegdqxyf blfsh bnfvqr bpuu bwricnfhx bxhftkfqp bz rd cvd dmgwf eg ejdtyp ezuwflat fdoacltr fh fl g gddycbbix gdwb gepspjmct gpnq grylxa h hhprvsmft htoftvknx hwsyy i iijr uu j jauf jv jwilh jxvte k khmnd khortsm ki kxs kyopng k zexolqs l lcyxoi ldaajnopp lrkvpfy lytcp lyvn mpqwv mtmjuojy n ndydxsh njrnpkas nz nztiermb o ohof pjwfwfg psbrziohe ptgdabu puodfjakc puxdq q q q qrudow qrxlxrdq r rcmjm rdrsu rl scoybh skganykg snhacjde sojeto swadsq t teicbqvo tiv tpoj ttt t tv uxu vd vp vpeevmen vzzpkghv w w wbvrru wshydbunp ww xcxlc xjs xkkxiko yeiezlz yhi z zbcnl zq 共进行比较2528次,进行交换2616次 *************************** 起泡法: 完成的序列如下: a be bfeqlp bgegdqxyf blfsh bnfvqr bpuu bwricnfhx bxhftkfqp bz rd cvd dmgwf eg ejdtyp ezuwflat fdoacltr fh fl g gddycbbix gdwb gepspjmct gpnq grylxa h hhprvsmft htoftvknx hwsyy i iijr uu j jauf jv jwilh jxvte k khmnd khortsm ki kxs kyopng k zexolqs l lcyxoi ldaajnopp lrkvpfy lytcp lyvn mpqwv mtmjuojy n ndydxsh njrnpkas nz nztiermb o ohof pjwfwfg psbrziohe ptgdabu puodfjakc puxdq q q q qrudow qrxlxrdq r rcmjm rdrsu rl scoybh skganykg snhacjde sojeto swadsq t teicbqvo tiv tpoj ttt t tv uxu vd vp vpeevmen vzzpkghv w w wbvrru wshydbunp ww xcxlc xjs xkkxiko yeiezlz yhi z zbcnl zq 共进行比较4950次,进行交换2469次 *************************** 希尔排序: