数据结构--内部排序的比较

存储管理、查找和排序

班级： 姓名： 学号： 完成日期：

题目：内部排序算法比较

问题描述：通过随机数据比较各算法的关键字比较次数与移动次

数。

一、需求分析：

内部排序方法有：插入排序，快速排序，简单选择排序，堆排序，归并排序，基数排序。

二、概要设计

本实验中用到的函数：

1.起泡排序函数

void gensort(int b[],int n) 2.插入排序函数

void insertsort(sqlist b,int n) 3.希尔排序

void shellsort(sqlist b,int n) 4.选择排序

void gentsort(int b[],int n) 5.快速排序

void quicksort(sqlist r,int s,int t) 6.堆排序

void sift(sqlist r,int s,int m)

三、详细设计

#include #include #include

#define N 66 //头文件和宏定义 int p,q; //全局变量

//-----------------------起泡排序 void gensort(int b[],int n) {

int i,j;int s=0,t=0; for(i=0;i

for(j=i+1;j

if(b[i]>b[j]) {

int temp=b[i]; b[i]=b[j]; b[j]=temp; s+=3; }}}

cout<<\移动次数=\比较次数=\}

//-------------------------------插入排序 typedef int KeyType;

struct rec {

KeyType key; };

typedef rec sqlist[N];

void insertsort(sqlist b,int n) {

int i,j;int s=0,t=0; for(i=2;i

b[0]=b[i]; s++; j=i-1; t++;

while(b[0].key

b[j+1]=b[j]; j--; s++; t++; }

b[j+1]=b[0]; s++; }

cout<<\移动次数=\比较次数=\}

//------------------------------------希尔排序 void shellsort(sqlist b,int n) {

int i,j,gap; rec x; int s=0,t=0; gap=n/2; while(gap>0) {

for(i=gap+1;i

j=i-gap; while(j>0) { t++;

if(b[j].key>b[j+gap].key) {

x=b[j];b[j]=b[j+gap]; b[j+gap]=x;j=j-gap; s+=3; }

else j=0; gap=gap/2; }}

cout<<\移动次数=\比较次数=\}}

//---------------------------------------选择排序 void gentsort(int b[],int n) {

int i,j,k; int s=0,t=0; for(i=0;i

for(j=i+1;j

if(b[k]>b[j]) {k=j;} } if(k!=i) {int temp=b[k]; b[k]=b[i]; b[i]=temp; s+=3; }}

cout<<\移动次数=\比较次数=\}

//--------------------------------快速排序 void output(sqlist b,int n)//输出元素值 {

for(int i=0;i

cout<

void display(int n,int m)//输出计数 {

cout<<\移动次数=\比较次数=\}

void BeforeSort()//初始化计数器 { p=0;q=0; }

void quicksort(sqlist r,int s,int t) {

int i=s,j=t; if(s

{

r[0]=r[s];p++; while(i

while(i=r[0].key) j--; r[i]=r[j]; q++; p++; p++;

while(i

r[j]=r[i];q++;p++; }

r[i]=r[0];p++; } else return; quicksort(r,s,j-1); quicksort(r,j+1,t); }

void sort(sqlist r,int s,int t) {

BeforeSort(); quicksort(r,s,t); display(p,q); }

//---------------------------------堆排序 void sift(sqlist r,int s,int m) {

int j; rec x; x=r[s];

for(j=2*s;j<=m;j*=2) {q++;

if(j

if(!(x.key

void heapsort(sqlist &r,int m) {

int i;rec w; for(i=m/2;i>0;--i) sift(r,i,m); for(i=m;i>1;--i) {

w=r[i];r[i]=r[1]; r[1]=w; p+=3;

sift(r,1,i-1); } }

void sorting(sqlist &r,int t) {

BeforeSort(); heapsort(r,t); display(p,q);

}

//-----------------------------------主函数 void main() {

int a1[N],i; int e=N;

for(i=0;i

cout<<\排序前数组:\\n\for(i=0;i

cout<cout<<\起泡排序运行结果:\\n\gensort(a1,sizeof(a1)/sizeof(int)); cout<<\ \\n\cout<<\插入排序运行结果:\\n\e=N;

for(i=0;i

a[i].key=e--; }

insertsort(a,N); e=N;

for(i=0;i

b[i].key=e--;}

cout<<\ \\n\cout<<\希尔排序运行结果:\\n\shellsort(b,N);

cout<<\ \\n\cout<<\选择排序运行结果:\\n\e=N; int c1[N]; for(i=0;i

cout<<\ \\n\cout<<\快速排序运行结果:\\n\e=N; sqlist c;

int low=0,high=10; for(i=0;i

c[i].key=e--; }

sort(c,low,high);

cout<<\ \\n\cout<<\堆排序运行结果:\\n\sqlist d; e=N;

for(i=0;i

cout<<\排序后数组:\\n\for(i=0;i

cout<for(i=0;i

{a1[i]=e++;}

cout<<\排序前数组:\\n\for(i=0;i

cout<cout<<\起泡排序运行结果:\\n\gensort(a1,sizeof(a1)/sizeof(int)); cout<<\ \\n\cout<<\插入排序运行结果:\\n\e=1;

for(i=0;i

for(i=0;i

b[i].key=e++; }

cout<<\ \\n\cout<<\希尔排序运行结果:\\n\shellsort(b,N);

cout<<\ \\n\cout<<\选择排序运行结果:\\n\e=1;

for(i=0;i

cout<<\ \\n\cout<<\快速排序运行结果:\\n\

e=1;

for(i=0;i

cout<<\ \\n\cout<<\堆排序运行结果:\\n\ e=1;

for(i=0;i

cout<<\排序后数组:\\n\for(i=0;i

cout<for(i=0;i

a1[i]=rand()0; c1[i]=a1[i]; a[i].key=a1[i]; b[i].key=a1[i]; c[i].key=a1[i]; d[i].key=a1[i]; }

cout<<\排序前数组:\\n\for(i=0;icout<<\起泡排序运行结果:\\n\

gensort(a1,sizeof(a1)/sizeof(int)); cout<

cout<<\插入排序运行结果:\\n\insertsort(a,N); cout<

cout<<\希尔排序运行结果:\\n\shellsort(b,N); cout<

cout<<\选择排序运行结果:\\n\gentsort(c1,N); cout<

cout<<\快速排序运行结果:\\n\sort(c,low,high); cout<

cout<<\堆排序运行结果:\\n\sorting(d,N);

cout<<\排序后数组:\\n\for(i=0;i四、调试分析：

程序运行基本正常。但有少量的语法错误。由于程序中没有给计数器清零。在每个算法程序开始时，将计数器的初值赋为零即可。

五、测试结果：

六、附录

源程序清单：

#include #include #include #define N 66 int p,q;

void gensort(int b[],int n) {

int i,j;int s=0,t=0; for(i=0;i

for(j=i+1;j

if(b[i]>b[j]) {

int temp=b[i]; b[i]=b[j]; b[j]=temp; s+=3; }}}

cout<<\移动次数=\比较次数=\}

typedef int KeyType; struct rec

{

KeyType key; };

typedef rec sqlist[N];

void insertsort(sqlist b,int n) {

int i,j;int s=0,t=0; for(i=2;i

b[0]=b[i]; s++; j=i-1; t++;

while(b[0].key

b[j+1]=b[j]; j--; s++;

t++; }

b[j+1]=b[0]; s++; }

cout<<\移动次数=\比较次数=\}

void shellsort(sqlist b,int n) {

int i,j,gap; rec x; int s=0,t=0; gap=n/2; while(gap>0) {

for(i=gap+1;i

j=i-gap; while(j>0) { t++;

if(b[j].key>b[j+gap].key) {

x=b[j];b[j]=b[j+gap]; b[j+gap]=x;j=j-gap; s+=3; }

else j=0; gap=gap/2;

}}

cout<<\移动次数=\比较次数=\}}

void gentsort(int b[],int n) {

int i,j,k; int s=0,t=0; for(i=0;i

for(j=i+1;j

if(b[k]>b[j]) {k=j;} } if(k!=i) {int temp=b[k]; b[k]=b[i]; b[i]=temp; s+=3; }}

cout<<\移动次数=\比较次数=\}

void output(sqlist b,int n) {

for(int i=0;i

cout<

void display(int n,int m) {

cout<<\移动次数=\比较次数=\}

void BeforeSort() { p=0;q=0; }

void quicksort(sqlist r,int s,int t) {

int i=s,j=t; if(s

r[0]=r[s];p++; while(i

while(i=r[0].key) j--; r[i]=r[j]; q++; p++; p++;

while(i

r[j]=r[i];q++;p++; }

r[i]=r[0];p++; } else return;

quicksort(r,s,j-1); quicksort(r,j+1,t); }

void sort(sqlist r,int s,int t) {

BeforeSort(); quicksort(r,s,t); display(p,q); }

void sift(sqlist r,int s,int m) { int j; rec x; x=r[s];

for(j=2*s;j<=m;j*=2) {q++;

if(j

if(!(x.key

void heapsort(sqlist &r,int m) {

int i;rec w; for(i=m/2;i>0;--i) sift(r,i,m); for(i=m;i>1;--i) {

w=r[i];r[i]=r[1]; r[1]=w; p+=3;

sift(r,1,i-1); } }

void sorting(sqlist &r,int t) {

BeforeSort(); heapsort(r,t); display(p,q); }

void main() {

int a1[N],i; int e=N;

for(i=0;i

cout<<\排序前数组:\\n\for(i=0;i

cout<cout<<\起泡排序运行结果:\\n\gensort(a1,sizeof(a1)/sizeof(int)); cout<<\ \\n\cout<<\插入排序运行结果:\\n\e=N;

for(i=0;i

a[i].key=e--; }

insertsort(a,N); e=N;

for(i=0;i

b[i].key=e--;}

cout<<\ \\n\cout<<\希尔排序运行结果:\\n\shellsort(b,N);

cout<<\ \\n\cout<<\选择排序运行结果:\\n\e=N; int c1[N]; for(i=0;i

cout<<\ \\n\cout<<\快速排序运行结果:\\n\e=N; sqlist c;

int low=0,high=10; for(i=0;i

c[i].key=e--; }

sort(c,low,high);

cout<<\ \\n\cout<<\堆排序运行结果:\\n\sqlist d;

e=N;

for(i=0;i

cout<<\排序后数组:\\n\for(i=0;i

cout<for(i=0;i

cout<<\排序前数组:\\n\for(i=0;i

cout<cout<<\起泡排序运行结果:\\n\gensort(a1,sizeof(a1)/sizeof(int)); cout<<\ \\n\cout<<\插入排序运行结果:\\n\e=1;

for(i=0;i

for(i=0;i

b[i].key=e++; }

cout<<\ \\n\

cout<<\希尔排序运行结果:\\n\shellsort(b,N);

cout<<\ \\n\cout<<\选择排序运行结果:\\n\e=1;

for(i=0;i

cout<<\ \\n\cout<<\快速排序运行结果:\\n\e=1;

for(i=0;i

cout<<\ \\n\cout<<\堆排序运行结果:\\n\e=1;

for(i=0;i

cout<<\排序后数组:\\n\for(i=0;i

cout<for(i=0;i

a1[i]=rand()0; c1[i]=a1[i]; a[i].key=a1[i]; b[i].key=a1[i];

c[i].key=a1[i]; d[i].key=a1[i]; }

cout<<\排序前数组:\\n\for(i=0;icout<<\起泡排序运行结果:\\n\gensort(a1,sizeof(a1)/sizeof(int)); cout<

cout<<\插入排序运行结果:\\n\insertsort(a,N); cout<

cout<<\希尔排序运行结果:\\n\shellsort(b,N); cout<

cout<<\选择排序运行结果:\\n\gentsort(c1,N); cout<

cout<<\快速排序运行结果:\\n\sort(c,low,high); cout<

cout<<\堆排序运行结果:\\n\sorting(d,N);

cout<<\排序后数组:\\n\for(i=0;i

本文来源：https://www.bwwdw.com/article/pzj8.html