数据结构——内部排序算法比较.doc

广 西 大 学 实 验 报 告 姓名_马瑞良_学号_0807100333_计网_专业_083_班_2009_年_12_月_08_日实验内容 内部排序算法比较 指导教师 一、 实验内容对各种内部排序算法进行比较二、实验要求（1）任意输入5组各10个数据；（2）对冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序的关键字比较和交换次数进行统计。三、所需主要仪器及现有套数：微机 台软件： visual C+四、程序源码：#includeusing namespace std;struct Recint key;/直接插入排序void instpass(Rec r,int n,int &m,int &k)cout直接插入排序结果是:n;m=0;k=0;int i,j,x;for(i=2;i=n;i+)r0=ri;j=i-1;x=ri.key;while(m+,xrj.key)rj+1=rj;j-;rj+1=r0;k+;/冒泡排序void bubbsort(Rec r,int n,int &m,int &k)cout冒泡排序结果是:n;m=0;k=0;int i,j;Rec x;bool flag;for(i=1;i=n-1;i+)flag=true;for(j=1;jrj+1.key)flag=false;x=rj;rj=rj+1;rj+1=x;k+;if(flag) break;/直接选择排序void selesort(Rec r,int n,int &m,int &l)m=0;l=0;cout直接选择排序结果是:n;int i,j,k;Rec x;for(i=1;i=n-1;i+)k=i;for(j=i+1;j=n;j+)if(m+,rj.keyrk.key)k=j;if(m+,i!=k)x=ri;ri=rk;rk=x;l+;/快速排序void qkpass(Rec r,int s,int t,int &i,int &m,int &k)int j,x;Rec rp;i=s;j=t;rp=rs;x=ri.key;while(m+,ij)while(m+,(i=x)j-;ri=rj;while(m+,(ij)&(ri.key=x)i+;rj=ri;ri=rp;k+;void qksort0(Rec r,int s,int t,int &m,int &n)int k;if(st)qkpass(r,s,t,k,m,n);qksort0(r,s,k-1,m,n);qksort0(r,k+1,t,m,n);void qksort(Rec r,int n,int &m,int &k)m=0;k=0;cout快速排序结果是:n;qksort0(r,1,n,m,k);/堆排序void sift(Rec r,int k,int m,int &l,int &n)int i,j,x;Rec t;bool finished;i=k;j=2*i;t=rk;x=t.key;finished=false;while(l+,(j=m)&(!finished) if(l+,(jm)&(rj.key=rj.key)finished=true;elseri=rj;i=j;j=2*i;ri=t;void heapsort(Rec r,int n,int &j,int &k)j=0;k=0;cout=1;i-)sift(r,i,n,j,k);for(i=n;i=2;i-)t=r1;r1=ri;ri=t;k+;sift(r,1,i-1,j,k);/显示void prnt(Rec r,int n,int &m,int &k)for(int i=1;i=n;i+)coutri.key ;coutendl;cout比较次数:mendl;cout交换次数:kendl;void main()Rec *r,*r1,*r2,*r3,*r4,*r5;int k(0),m(0),n;coutn;r=new Recn+1;r1=new Recn+1;r2=new Recn+1;r3=new Recn+1;r4=new Recn+1;r5=new Recn+1;for(int i=1;iri.key;for(i=1;i=n;i+)r1i.key=ri.key;r2i.key=ri.key;r3i.key=ri.key;r4i.key=ri.key;r5i.key=ri.key;/直接插入排序instpass(r1,n,m,k);prnt(r1,n,m,k);coutendl;/冒泡排序bubbsort(r2,n,m,k);prnt(r2,n,m,k);coutendl;/直接选择排序selesort(r3,n,m,k);prnt(r3,n,m,k);coutendl;/快速排序qksort(r4,n,m,k);prnt(r4,n,m,k);coutendl;/堆排序heapsort(