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

实验五 内部排序算法效率比较平台的设计与实现 1. 试验内容

1、问题描述

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。设计和实现内部排序算法效率比较平台，通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观的感受。 2、基本要求

（1）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。

（2）待排序的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。

（3）最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。 3、测试数据

由随机数产生器生成。 4、实现提示

主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。

. 专业.专注 .

. . .. . .

2. 试验目的

掌握多种排序方法的基本思想，如直接插入、冒泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。

. 专业.专注 .

. . .. . .

3. 流程图

开始产生100个随机字符串直接插入排序排序输出序列和交换次数及比较次数起泡排序排序输出序列和交换次数及比较次数希尔排序排序输出序列和交换次数及比较次数简单选择排序排序输出序列和交换次数及比较次数快速排序排序输出序列和交换次数及比较次数堆排序排序输出序列和交换次数及比较次数结束 . 专业.专注 .

. . .. . .

4. 源程序代码

#include #include #include #define le 100 struct point {

char key[11]; }; //冒泡法

void maopao(point c[]) {

point a,b[le]; int i,j,jh=0,bj=0,q; for(i=0;ifor(i=0;ifor(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]=c[i];

. 专业.专注 .

. . .. . .

};

};

};

b[i]=b[j]; b[j]=a; jh=jh+3;

cout<<\"冒泡法:\"<cout<};

//直接插入排序

void zhijiecharu(point c[]) {

point b[le+1]; int i,j,jh=0,bj=0,q; for(i=0;ifor(i=2;i<=le+1;i++){

b[i+1]=c[i];

cout<. 专业.专注 .

. . .. . .

};

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[0];jh=jh+1;

b[j+1]=b[j];jh=jh+1;

q=strcmp(b[0].key,b[j-1].key);bj=bj+1;

cout<<\"直接插入排序:\"<cout<}; //

void shellinsert(point c[],int dk,int d[])

cout<. 专业.专注 .

. . .. . .

{ int j,i,q; point a;

for(i=dk+1;ivoid 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;kb[k+1]=c[k];

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]=a;d[1]=d[1]+1;

c[j+dk]=c[j];d[1]=d[1]+1; q=strcmp(a.key,c[j-dk].key);

. 专业.专注 .

. . .. . .

for(k=0;kcout<<\"希尔排序:\"<cout<};

//希尔排序 void xier(point c[]) {

int dlta[20],t,i;t=le/2; for(i=0;i<20;i++){ }; t=i+1;

shellsort(c,dlta,t); };

//简单选择排序

void jiandanxuanze(point c[])

dlta[i]=t+1; if(t==0)break; t=t/2;

cout<. 专业.专注 .

. . .. . .

{

point a,b[le]; int i,j,jh=0,bj=0,q,w; for(i=0;ifor(i=0;icout<<\"简单选择排序排序:\"<q=i;

for(j=i+1;jif(q==i)continue; else { };

a=b[i]; b[i]=b[q]; b[q]=a; jh=jh+3; bj=bj+1;

w=strcmp(b[q].key,b[j].key); if(w==1)q=j; b[i]=c[i];

. 专业.专注 .

. . .. . .

for(i=0;icout<};

int partition(point c[],int low,int high,int d[]) {

point a,b; int jh=0,bj=0,q; a=c[low]; while(lowq=strcmp(c[high].key,a.key);d[0]=d[0]+1;

while(lowq=strcmp(c[low].key,a.key);d[0]=d[0]+1;

while(low. 专业.专注 .

. . .. . .

};

c[high]=b; d[1]=d[1]+3;

return(low); };

void qsort(point c[],int low,int high,int d[]) {

int pivotloc; if(low//快速排序

void kuaisu(point c[]) {

point b[le]; int i,d[2]; d[0]=0;d[1]=0; for(i=0;ib[i]=c[i];

pivotloc=partition(c,low,high,d); qsort(c,low,pivotloc-1,d); qsort(c,pivotloc+1,high,d);

. 专业.专注 .

. . .. . .

};

qsort(b,0,le-1,d);

cout<<\"快速排序:\"<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){ };

if(2*i+1q=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[i];b[i]=b[2*i];b[2*i]=a;*jh=*jh+3; cout<. 专业.专注 .

. . .. . .

};

};

a=b[we-1];b[we-1]=b[0];b[0]=a;*jh=*jh+3; }; //堆排序

void diup(point c[]) {

point b[le];

int i,jh=0,bj=0,*j,*bl; j=&jh;bl=&bj; for(i=0;ifor(i=le;i>1;i--){ };

cout<<\"堆排序:\"<cout<cout<. 专业.专注 .

. . .. . .

};

void main() {

int i,j,n=10,ans,an;

char b[]=\"abcdefghijklmnopqrstuvwxyz\"; point a[le]; for(i=0;ifor(i=0;izhijiecharu(a); maopao(a); xier(a);

cout<an=rand()*(n-1)/RAND_MAX+1; n=26;

for(j=0;ja[i].key[j]='\\0';

ans=rand()*(n-0)/RAND_MAX+0; a[i].key[j]=b[ans];

. 专业.专注 .

. . .. . .

jiandanxuanze(a); kuaisu(a);

}

diup(a);

参考自

5. 实验结果

运行结果如下： 直接插入排序: 完成的序列如下:

*************************** 冒泡法:

完成的序列如下:

*************************** 希尔排序:

. 专业.专注 .

. . .. . .

完成的序列如下:

*************************** 简单选择排序排序: 完成的序列如下:

*************************** 快速排序: 完成的序列如下:

*************************** 堆排序:

. 专业.专注 .

. . .. . .

完成的序列如下:

. 专业.专注 .