搜索
《数据结构》课程实验实验报告题目：内部排序算法效率比较平台的设计与实现专业：计算机科学与技术班级：姓名：学号：完成日期：一、试验内容各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。设计和实现内部排序算法效率比较平台，通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观的感受。二、试验目的掌握多种排序方法的基本思想，如直接插入、冒泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。三、源程序代码#includeiostream.h#includestring.h#includestdlib.h#definele100structpoint{charkey[11];};//冒泡法voidmaopao(pointc[]){pointa,b[le];inti,j,jh=0,bj=0,q;for(i=0;ile;i++){b[i]=c[i];};for(i=0;ile;i++){for(j=le-1;ji;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冒泡法:endl完成的序列如下:endl;for(i=0;ile;i++){coutb[i].key;};coutendl共进行比较bj次,进行交换jh次endl***************************endl;};//直接插入排序voidzhijiecharu(pointc[]){pointb[le+1];inti,j,jh=0,bj=0,q;for(i=0;ile;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直接插入排序:endl完成的序列如下:endl;for(i=1;ile+1;i++){coutb[i].key;};coutendl共进行比较bj次,进行交换jh次endl***************************endl;};//voidshellinsert(pointc[],intdk,intd[]){intj,i,q;pointa;for(i=dk+1;ile+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;j0&&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;kle;k++){b[k+1]=c[k];};for(k=0;kt;k++)shellinsert(b,dlta[k],d);cout希尔排序:endl完成的序列如下:endl;for(i=1;ile+1;i++){coutb[i].key;};coutendl共进行比较d[0]次,进行交换d[1]次endl***************************endl;};//希尔排序voidxier(pointc[]){intdlta[20],t,i;t=le/2;for(i=0;i20;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;ile;i++){b[i]=c[i];};for(i=0;ile-1;i++){q=i;for(j=i+1;jle;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简单选择排序排序:endl完成的序列如下:endl;for(i=0;ile;i++){coutb[i].key;};coutendl共进行比较bj次,进行交换jh次endl***************************endl;};intpartition(pointc[],intlow,inthigh,intd[]){pointa,b;intjh=0,bj=0,q;a=c[low];while(lowhigh){q=strcmp(c[high].key,a.key);d[0]=d[0]+1;while(lowhigh&&q!=-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(lowhigh&&q!=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(lowhigh){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;ile;i++){b[i]=c[i];};qsort(b,0,le-1,d);cout快速排序:endl完成的序列如下:endl;for(i=0;ile;i++){coutb[i].key;};coutendl共进行比较d[1]次,进行交换d[0]次endl***************************endl;};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+1we){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;ile;i++){b[i]=c[i];};for(i=le;i1;i--){diu(b,i,j,bl);};cout堆排序:endl完成的序列如下:endl;for(i=0;ile;i++){coutb[i].key;};coutendl共进行比较bj次,进行交换jh次endl***************************endl;};voidmain(){inti,j,n=10,ans,an;charb[]=abcdefghijklmnopqrstuvwxyz;pointa[le];for(i=0;ile;i++){n=10;an=rand()*(n-1)/RAND_MAX+1;n=26;for(j=0;jan;j++){ans=rand()*(n-0)/RAND_MAX+0;a[i].key[j]=b[ans];};a[i].key[j]='\0';};for(i=0;ile;i++){couta[i].keyendl;};zhijiecharu(a);maopao(a);xier(a);jiandanxuanze(a);kuaisu(a);diup(a);};四、流程图开始产生100个随机字符串直接插入排序排序输出序列和交换次数及比较次数起泡排序排序输出序列和交换次数及比较次数希尔排序排序输出序列和交换次数及比较次数简单选择排序排序输出序列和交换次数及比较次数快速排序排序输出序列和交换次数及比较次数堆排序排序输出序列和交换次数及比较次数结束五、调试过程要很好的理解各种算法就可以这样才可以编出程序来，要注意比较次数和交换次数的计数问题。六、结果分析运行结果如下：ovpjxvtesnhacjdeldaajnopprlbpuuhwsyydmgwfvzzpkghvjrahhprvsmftlytcptpojflnztiermbndydxshbzrdvpeevmenkhortsmjvnlcyxoijwilhhtoftvknxzbnfvqrvdtyhitvptgdabufdoacltrblfshgpnqnzyeiezlzqlbxhftkfqpmpqwvsojetogepspjmctqrudowpsbrziohewteicbqvokhmndtivwshydbunpbwricnfhxrcmjmnjrnpkasqmtmjuojyejdtypiqwwswadsqbeiijruupuxdqgdwbohofcvduxupjwfwfgzbcnlggddycbbixlyvnskganykggrylxapuodfjakcwbvrrurdrsuwscoybhzqxjsegxcxlcezuwflatkibgegdqxyfqrxlxrdqkyopngjaufkbfeqlplrkvpfykzexolqshkxsxkkxikottttfh直接插入排序:完成的序列如下:abebfeqlpbgegdqxyfblfshbnfvqrbpuubwricnfhxbxhftkfqpbzrdcvddmgwfegejdtypezuwflatfdoacltrfhflggddycbbixgdwbgepspjmctgpnqgrylxahhhprvsmfthtoftvknxhwsyyiiijruujjaufjvjwilhjxvtekkhmndkhortsmkikxskyopngkzexolq