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

实验五 内部排序算法效率比较平台的设计与实现1. 试验内容1、问题描述各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。设计和实现内部排序算法效率比较平台，通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观的感受。2、基本要求（1）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。（2）待排序的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。（3）最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。3、测试数据由随机数产生器生成。4、实现提示主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。2. 试验目的掌握多种排序方法的基本思想，如直接插入、冒泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。3. 流程图4. 源程序代码#include#include#include#define le 100struct pointchar key11;/冒泡法void maopao(point c)point a,ble;int i,j,jh=0,bj=0,q;for(i=0;ile;i+)bi=ci;for(i=0;ii;j-)bj=bj+1;q=strcmp(bi.key,bj.key);if(q=1)a=bi;bi=bj;bj=a;jh=jh+3;cout冒泡法:endl完成的序列如下:endl;for(i=0;ile;i+)coutbi.key ;coutendl共进行比较bj次,进行交换jh次endl*endl;/直接插入排序void zhijiecharu(point c)point ble+1;int i,j,jh=0,bj=0,q;for(i=0;ile;i+)bi+1=ci;for(i=2;i=le+1;i+)q=strcmp(bi.key,bi-1.key);bj=bj+1;if(q=-1)b0=bi;bi=bi-1;jh=jh+2;q=strcmp(b0.key,bi-2.key);bj=bj+1;for(j=i-2;q=-1;j-)bj+1=bj;jh=jh+1;q=strcmp(b0.key,bj-1.key);bj=bj+1;bj+1=b0;jh=jh+1;cout直接插入排序:endl完成的序列如下:endl;for(i=1;ile+1;i+)coutbi.key ;coutendl共进行比较bj次,进行交换jh次endl*endl;/void shellinsert(point c,int dk,int d)int j,i,q;point a;for(i=dk+1;i0&q=-1;j=j-dk)cj+dk=cj;d1=d1+1;q=strcmp(a.key,cj-dk.key);cj+dk=a;d1=d1+1;void shellsort(point c,int dlta,int t)int k,d2,i;d0=0;d1=0;point ble+1;for(k=0;kle;k+)bk+1=ck;for(k=0;kt;k+)shellinsert(b,dltak,d);cout希尔排序:endl完成的序列如下:endl;for(i=1;ile+1;i+)coutbi.key ;coutendl共进行比较d0次,进行交换d1次endl*endl;/希尔排序void xier(point c)int dlta20,t,i;t=le/2;for(i=0;i20;i+)dltai=t+1;if(t=0)break;t=t/2;t=i+1;shellsort(c,dlta,t);/简单选择排序void jiandanxuanze(point c)point a,ble;int i,j,jh=0,bj=0,q,w;for(i=0;ile;i+)bi=ci;for(i=0;ile-1;i+)q=i;for(j=i+1;jle;j+)bj=bj+1;w=strcmp(bq.key,bj.key);if(w=1)q=j;if(q=i)continue;else a=bi;bi=bq;bq=a;jh=jh+3;cout简单选择排序排序:endl完成的序列如下:endl;for(i=0;ile;i+)coutbi.key ;coutendl共进行比较bj次,进行交换jh次endl*endl;int partition(point c,int low,int high,int d)point a,b;int jh=0,bj=0,q;a=clow;while(lowhigh)q=strcmp(chigh.key,a.key);d0=d0+1;while(lowhigh&q!=-1)high-;q=strcmp(chigh.key,a.key);d0=d0+1;b=clow;clow=chigh;chigh=b;d1=d1+3;q=strcmp(clow.key,a.key);d0=d0+1;while(lowhigh&q!=1)low+;q=strcmp(clow.key,a.key);d0=d0+1;b=clow;clow=chigh;chigh=b;d1=d1+3;return(low);void qsort(point c,int low,int high,int d)int pivotloc;if(lowhigh)pivotloc=partition(c,low,high,d);qsort(c,low,pivotloc-1,d);qsort(c,pivotloc+1,high,d);/快速排序void kuaisu(point c)point ble;int i,d2;d0=0;d1=0;for(i=0;ile;i+)bi=ci;qsort(b,0,le-1,d);cout快速排序:endl完成的序列如下:endl;for(i=0;ile;i+)coutbi.key ;coutendl共进行比较d1次,进行交换d0次endl*=0;i-)q=strcmp(bi.key,b2*i.key);*bj=*bj+1;if(q=-1)a=bi;bi=b2*i;b2*i=a;*jh=*jh+3;if(2*i+1we)q=strcmp(bi.key,b2*i+1.key);*bj=*bj+1;if(q=-1)a=bi;bi=b2*i+1;b2*i+1=a;*jh=*jh+3;a=bwe-1;bwe-1=b0;b0=a;*jh=*jh+3;/堆排序void diup(point c)point ble;int i,jh=0,bj=0,*j,*bl;j=&jh;bl=&bj;for(i=0;i1;i-)diu(b,i,j,bl); cout堆排序:endl完成的序列如下:endl;for(i=0;ile;i+)coutbi.key ;coutendl共进行比较bj次,进行交换jh次endl*endl;void main()int i,j,n=10,ans,an;char b=abcdefghijklmnopqrstuvwxyz;point ale;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;ai.keyj=bans;ai.keyj=0;for(i=0;ile;i+)coutai.keyendl;zhiji