数据结构 程序设计 各种排序算法时间性能的比较

学号

数据结构课程设计

设计说明书

题目

各种排序算法时间性能的比较

起止日期：2011年12月12 日至2011 年12月16日

学生姓名

班级

成绩

指导教师(签字)

电子与信息工程系

2011年12月16日

天津城市建设学院

课程设计任务书

2011—2012学年第1学期

电子与信息工程系软件工程专业班级

课程设计名称：数据结构课程设计

设计题目：各种排序算法时间性能的比较

完成期限：自2011 年12 月12 日至2011 年12 月16 日共 1 周

设计依据、要求及主要内容（可另加附页）：

一、设计目的

熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。

二、设计要求

（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；

（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；

（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；

（4）认真编写课程设计报告。

三、设计内容

对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。

(1) 设计并实现上述各种排序算法；

(2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；

(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。

四、参考文献

1．王红梅．数据结构．清华大学出版社

2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社

一、需求分析

需要对用户输入的一组数据进行排序，并对7种排序的正逆排序进行分析，并做出时间复杂度的比较，并得出最优的排序方法作为结果。

二、问题求解

在排序时，开始做出的任何一个排序的的逆排序的时间复杂度都是一个定值不会变，后来经过单步调试，发现是把正排序放在了起之前，所以逆排序排出来的都是已经排好的数据，所以不会变，我通过复制数组，做成了两个数组（最后做成的总程序为多个数组），然后分别对应每个算法做排序。这样就不会在显示后一个算法的排序是前一个算法已经排序好的数组，而是用户输入的原始数组。

一下是对于每个排序的分析及所遇见的问题：（排序解释都用正排序说明）

1．冒泡排序

该排序没有什么打的问题，用两个for循环即可做出排序。排序原理是两两对比大的放前，小的放后。

2．插入排序

该排序是以第n个数（需排序的数）直接去与数组里已经排序好的数做比较。将其插入比它大的数之前，比它小的数之后。

在做该数组的时候我之前以为r[0]的哨兵可以用任意一的变量来代替，从而是数组从r[0]开始计数，结果表明，并不是这样，因为每一次，最小的数都会呗覆盖掉，所以原假设不成立。

3．希尔排序：

先把数组分成等长的两个数组，用r[i]与r[n/2+i]做比较晓得在前，打的在后，然后在一刚刚两两一组的两组做比较，就这样，每次比较，每组数的个数都是上一次的两倍，最后完成整个数组的排序。

4．直接选择排序

该排序是现在无序的数组中找最值，然后作为第一个元素，之后就是每次找最值，作为下一个元素，直至最后一个元素，排序完成。

5．快速排序

定义两个指针，分别只想第一个与最后一个元素，这两个元素做比较，大的放前，小的放后，然后移动指针，进行下一个比较。两次这样比较排序以后，数组变成为了有序数列。该算法采用为递归算法。

6．归并排序

该排序，也是需要调用递归。

先把数组对半分多次，直到每组只有两个数据时，进行对比、排序。然后再两两合并，最后做到整个数组的排序完成

7．堆排序

先是对堆做比较，左子数小于本数，右子数大于本数，然后不停比较，交换，最后达到整个数组的排序。

三、总体设计

四、详细设计

void Zmppx(int a[] ,int n ) //正序排序

void Nmppx(int a[] ,int n ) //逆序排序

//插入排序

void Zcrpx(int r[] ,int n) //正序排序

void Ncrpx(int r[] ,int n) //逆序排序

//希尔排序

void Zxepx(int r[] ,int n) //正序排序

void Nxepx(int r[] ,int n) //逆序排序

//直接选择排序

void Zzjxzpx(int r[] ,int n) //正序排序

void Nzjxzpx(int r[] ,int n) //逆序排序

//快速排序

void Zkspx(int r[],int left,int right) //正序排序

void Nkspx(int r[],int left,int right) //逆序排序

//归并排序

void Copy(int r[],int b[],int l,int g) //复制函数void ZMerge(int c[],int d[],int l,int m,int g) //正排序算法void Zgbpx(int r[],int left,int right) //正序排序void NMerge(int c[],int d[],int l,int m,int g) //逆排序算法void Ngbpx(int r[],int left,int right) //逆序排序

//堆排序

void Zsift(int r[],int k,int m) //筛选法调整堆算法（正）void Zdpx(int r[] ,int n) //正序排序

void Nsift(int r[],int k,int m) //筛选法调整堆算法（逆）void Ndpx(int r[] ,int n) //逆序排序

//主函数

void main() //输入输出

五、调试与测试

调试用的是简单的黑盒测试，输入数据，给出结果。

遇到的问题如“二”所示。

六、关键源程序清单和执行结果

#include

using namespace std;

int mpzl=0,mpnl=0;

int crzl=0,crnl=0;

int xezl=0,xenl=0;

int zjzl=0,zjnl=0;

int kszl=0,ksnl=0;

int gbzl=0,gbnl=0;

int dzl=0,dnl=0;

//************************************************************* //冒泡排序

void Zmppx(int a[] ,int n )

{

for(int t=1;t<=n;t++)

{

for(int k=1 ;k

{

if(a[k]>a[k+1])

{

int p=a[k+1];

a[k+1]=a[k];

a[k]=p;

mpzl++;

}

mpzl++;

}

mpzl++;

}

}

void Nmppx(int a[] ,int n )

{

for(int t=1;t<=n;t++)

{

for(int k=n-1 ;k>0;k--)

{

if(a[k]

{

int p=a[k+1];

a[k+1]=a[k];

a[k]=p;

mpnl++;

}

mpnl++;

}

mpnl++;

}

}

//************************************************************* //插入排序

void Zcrpx(int r[] ,int n)

{

for(int i=2; i<=n ; i++)

{

r[0]=r[i];

for( int j=i-1;r[j]>r[0];j--)

{

r[j+1]=r[j];

crzl++;

}

r[j+1]=r[0];

crzl++;

}

}

void Ncrpx(int r[] ,int n)

{

for(int i=2; i<=n ; i++)

{

r[0]=r[i];

for( int j=i-1;r[j]

{

r[j+1]=r[j];

crnl++;

}

r[j+1]=r[0];

crnl++;

}

}

//************************************************************* //希尔排序

void Zxepx(int r[] ,int n)

{

for(int d=n/2; d>=1; d=d/2)

{

for(int i=d+1; i<=n; i++)

{

r[0]=r[i];

for(int j=i-d;j>0 &&r[0]

{

r[j+d]=r[j];

xezl++;

}

r[j+d]=r[0];

xezl++;

}

xezl++;

}

}

void Nxepx(int r[] ,int n)

{

for(int d=n/2; d>=1; d=d/2)

{

for(int i=d+1; i<=n; i++)

{

r[0]=r[i];

for(int j=i-d;j>0 &&r[0]>r[j];j=j-d)

{

r[j+d]=r[j];

xenl++;

}

r[j+d]=r[0];

xenl++;

}

xenl++;

}

}

//************************************************************* //直接选择排序

void Zzjxzpx(int r[] ,int n) {

for(int i=1; i

{

int m=i;

for(int j=i+1;j<=n;j++)

{

if(r[j]

m=j;

zjzl++;

}

int p;

if(n!=i)

{

p=r[i];

r[i]=r[m];

r[m]=p;

zjzl++;

}

zjzl++;

}

}

void Nzjxzpx(int r[] ,int n) {

for(int i=1; i

{

int m=i;

for(int j=i+1;j<=n;j++)

{

if(r[j]>r[m])

m=j;

zjnl++;

}

int p;

if(n!=i)

{

p=r[i];

r[i]=r[m];

r[m]=p;

zjnl++;

}

zjnl++;

}

}

//************************************************************* //快速排序

void Zkspx(int r[],int left,int right)

{

int i=left,j=right,p=r[left];

while(i

{

while(i=p)

j--;

kszl++;

int m=r[i];

r[i]=r[j];

r[j]=m;

kszl++;

while(i

i++;

kszl++;

m=r[j];

r[j]=r[i];

r[i]=m;

kszl++;

}

if(left

Zkspx(r,left,i-1);

if(right>i+1)

Zkspx(r,i+1,right);

}

void Nkspx(int r[],int left,int right)

{

int i=left,j=right,p=r[left];

while(i

{

while(i

j--;

ksnl++;

int m=r[i];

r[i]=r[j];

r[j]=m;

ksnl++;

while(i=p)

i++;

m=r[j];

r[j]=r[i];

r[i]=m;

ksnl++;

}

if(left

Nkspx(r,left,i-1);

if(right>i+1)

Nkspx(r,i+1,right);

}

//*************************************************************

//归并排序

int b[100];//定义全局变量，存储Merge合并时暂时存放排序后的数组元素//真正的排序函数比较左右两段元素将较小数字依次暂存数组b中

//将数组b暂存的排序后的元素返回数组

void Copy(int r[],int b[],int l,int g)

{

for(int i=l;i<=g;i++)

{

r[i]=b[i];

gbzl++;

gbnl++;

}

}

//正序合并

void ZMerge(int c[],int d[],int l,int m,int g)

{

int i=l,j=m+1,k=l;

while((i<=m)&&(j<=g))

{

if(c[i]<=c[j])

{

d[k++]=c[i++];

gbzl++;

}

else

{

d[k++]=c[j++];

gbzl++;

}

}

if(i>m)

for(int q=j;q<=g;q++)

{

d[k++]=c[q];

gbzl++;

}

else

for(int q=i;q<=m;q++)

{

d[k++]=c[q];

gbzl++;

}

}

//正序合并排序主函数

void Zgbpx(int r[],int left,int right)

{

if(left

{

int i=(left+right)/2; //数组均分成两段

Zgbpx(r,left,i); //递归对左边数据进行合并排序

Zgbpx(r,i+1,right); //递归对右边数据进行合并排序

ZMerge(r,b,left,i,right); //调用排序函数

Copy(r,b,left,right);

}

}

//逆序合并

void NMerge(int c[],int d[],int l,int m,int g)

{

int i=l,j=m+1,k=l;

while((i<=m)&&(j<=g))

{

if(c[i]>=c[j])

{

d[k++]=c[i++];

gbnl++;

}

else

{

d[k++]=c[j++];

gbnl++;

}

}

if(i>m)

for(int q=j;q<=g;q++)

{

d[k++]=c[q];

gbnl++;

}

else

for(int q=i;q<=m;q++)

{

d[k++]=c[q];

gbnl++;

}

}

//逆序合并排序主函数

void Ngbpx(int r[],int left,int right)

{

if(left

{

int i=(left+right)/2; //数组均分成两段

Ngbpx(r,left,i); //递归对左边数据进行合并排序

Ngbpx(r,i+1,right); //递归对右边数据进行合并排序

NMerge(r,b,left,i,right); //调用排序函数

Copy(r,b,left,right);

}

}

//*************************************************************

//堆排序

void Zsift(int r[],int k,int m)

{

int i=k;

int j=2*i;

while(j<=m)

{

if(j

{

j++;

dzl++;

}

if(r[i]>r[j])

{

dzl++;

break;

}

else

{

int p=r[i];

r[i]=r[j];

r[j]=p;

dzl++;

i=j;

j=2*i;

}

}

}

void Zdpx(int r[] ,int n)

{

for(int i=n/2; i>=1 ; i--)

{

dzl++;

Zsift(r,i,n);

}

for(i=1; i

{

int p=r[1];

r[1]=r[n-i+1];

r[n-i+1]=p;

dzl++;

Zsift(r,1,n-i);

}

}

void Nsift(int r[],int k,int m) {

int i=k;

int j=2*i;

while(j<=m)

{

if(jr[j+1])

{

j++;

dnl++;

}

if(r[i]

{

dnl++;

break;

}

else

{

int p=r[i];

r[i]=r[j];

r[j]=p;

dnl++;

i=j;

j=2*i;

}

}

}

void Ndpx(int r[] ,int n)

{

for(int i=n/2; i>=1 ; i--)

{

dnl++;

Nsift(r,i,n);

}

for(i=1; i

{

int p=r[1];

r[1]=r[n-i+1];

r[n-i+1]=p;

dnl++;

Nsift(r,1,n-i);

}

}

//*************************************************************

void main()

{

int

r[1000],mr1[1000],cr1[1000],xr1[1000],zr1[1000],kr1[1000],gr1[1000],dr1[1000], mr2[1000],cr2[1000],xr2[1000],zr2[1000],kr2[1000],gr2[1000],dr2[1000];

int n;

cout<<"请输入排序个数"<

cin>>n;

cout<<"请输入"<

{

cin>>r[i];

}

for(int k=1;k<=n;k++)

{

mr1[k]=r[k];

mr2[k]=r[k];

cr1[k]=r[k];

cr2[k]=r[k];

xr1[k]=r[k];

xr2[k]=r[k];

zr1[k]=r[k];

zr2[k]=r[k];

kr1[k]=r[k];

kr2[k]=r[k];

gr1[k]=r[k];

gr2[k]=r[k];

dr1[k]=r[k];

dr2[k]=r[k];

}

Zmppx(mr1,n);

cout<<"正序排序以后为"<

for(int j=1;j<=n;j++)

{

cout<

}

cout<

Nmppx(mr2,n);

cout<<"逆序排序以后为"<

for( j=1;j<=n;j++)

{

cout<

}

cout<

Zcrpx(cr1,n);

Ncrpx(cr2,n);

Zxepx(xr1,n);

Nxepx(xr2,n);

Zzjxzpx(zr1,n);

Nzjxzpx(zr2,n);

Zkspx(kr1,1,n);

Nkspx(kr2,1,n);

Zgbpx(gr1,1,n);

Ngbpx(gr2,1,n);

Zdpx(dr1,n);

Ndpx(dr2,n);

cout<<"冒泡正序排序时间复杂度为"<

cout<<"冒泡逆序排序时间复杂度为"<

cout<<"*"<

cout<<"插入正序排序时间复杂度为"<

cout<<"插入逆序排序时间复杂度为"<

cout<<"*"<

cout<<"希尔正序排序时间复杂度为"<

cout<<"希尔逆序排序时间复杂度为"<

cout<<"*"<

cout<<"直接选择正序排序时间复杂度为"<

cout<<"直接选择逆序排序时间复杂度为"<

cout<<"*"<

cout<<"快速正序排序时间复杂度为"<

cout<<"快速逆序排序时间复杂度为"<

cout<<"*"<

cout<<"归并正序排序时间复杂度为"<

cout<<"归并逆序排序时间复杂度为"<

cout<<"*"<

cout<<"堆正序排序时间复杂度为"<

cout<<"堆逆序排序时间复杂度为"<

cout<<"*********************************************"<

int p;

if(mpzl<=crzl && mpzl<=xezl && mpzl<=zjzl && mpzl<=kszl && mpzl<=gbzl && mpzl<=dzl)

p=1;

if(crzl

p=2;

if(xezl

p=3;

if(zjzl

p=4;

if(kszl

p=5;

if(gbzl

p=6;

if(dzl

p=7;

switch(p)

{

case 1:

cout<<"该数列正排序使用冒泡排序最为简便"<

break;

case 2:

cout<<"该数列正排序使用插入排序最为简便"<

break;

case 3:

cout<<"该数列正排序使用希尔排序最为简便"<

break;

case 4:

cout<<"该数列正排序使用直接选择排序最为简便"<

break;

case 5:

cout<<"该数列正排序使用快速排序最为简便"<

break;

case 6:

cout<<"该数列正排序使用归并排序最为简便"<

break;

case 7:

cout<<"该数列正排序使用堆排序最为简便"<

break;

}

int q;

if(mpnl<=crnl && mpnl<=xenl && mpnl<=zjnl && mpnl<=ksnl && mpnl<=gbnl && mpnl<=dnl)

q=1;

if(crnl

q=2;

if(xenl

q=3;

if(zjnl

q=4;

if(ksnl

p=5;

if(gbnl

q=6;

if(dnl

q=7;

switch(q)

{

case 1:

cout<<"该数列逆排序使用冒泡排序最为简便"<

break;

case 2:

cout<<"该数列逆排序使用插入排序最为简便"<

break;

case 3:

cout<<"该数列逆排序使用希尔排序最为简便"<

break;

case 4:

cout<<"该数列逆排序使用直接选择排序最为简便"<

break;

case 5:

cout<<"该数列逆排序使用快速排序最为简便"<

break;

case 6:

cout<<"该数列逆排序使用归并排序最为简便"<

break;

case 7:

cout<<"该数列逆排序使用堆排序最为简便"<

break;

}

}

运算结果