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

学 号 数据结构课程设计设计说明书题目各种排序算法时间性能的比较起止日期： 2011年 12月 12 日 至 2011 年 12月16日学生姓名班级成绩指导教师(签字) 电子与信息工程系2011年 12月16日天津城市建设学院课程设计任务书20112012学年第1学期 电子与信息工程 系 软件工程 专业 班级课程设计名称： 数据结构课程设计 设计题目： 各种排序算法时间性能的比较 完成期限：自 2011 年 12 月 12 日至 2011 年 12 月 16 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。(1) 设计并实现上述各种排序算法；(2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。四、参考文献1王红梅数据结构清华大学出版社2王红梅数据结构学习辅导与实验指导清华大学出版社3严蔚敏，吴伟民数据结构（C语言版）清华大学出版社一、需求分析需要对用户输入的一组数据进行排序，并对7种排序的正逆排序进行分析，并做出时间复杂度的比较，并得出最优的排序方法作为结果。二、问题求解在排序时，开始做出的任何一个排序的的逆排序的时间复杂度都是一个定值不会变，后来经过单步调试，发现是把正排序放在了起之前，所以逆排序排出来的都是已经排好的数据，所以不会变，我通过复制数组，做成了两个数组（最后做成的总程序为多个数组），然后分别对应每个算法做排序。这样就不会在显示后一个算法的排序是前一个算法已经排序好的数组，而是用户输入的原始数组。一下是对于每个排序的分析及所遇见的问题：（排序解释都用正排序说明）1冒泡排序该排序没有什么打的问题，用两个for循环即可做出排序。排序原理是两两对比大的放前，小的放后。2插入排序该排序是以第n个数（需排序的数）直接去与数组里已经排序好的数做比较。将其插入比它大的数之前，比它小的数之后。在做该数组的时候我之前以为r0的哨兵可以用任意一的变量来代替，从而是数组从r0开始计数，结果表明，并不是这样，因为每一次，最小的数都会呗覆盖掉，所以原假设不成立。3希尔排序：先把数组分成等长的两个数组，用ri与rn/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 <iostream>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<n;k+)if(ak>ak+1)int p=ak+1;ak+1=ak;ak=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(ak<ak+1)int p=ak+1;ak+1=ak;ak=p;mpnl+;mpnl+;mpnl+;/*/插入排序void Zcrpx(int r ,int n)for(int i=2; i<=n ; i+)r0=ri;for( int j=i-1;rj>r0;j-)rj+1=rj;crzl+;rj+1=r0;crzl+;void Ncrpx(int r ,int n)for(int i=2; i<=n ; i+)r0=ri;for( int j=i-1;rj<r0;j-)rj+1=rj;crnl+;rj+1=r0;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+)r0=ri;for(int j=i-d;j>0 &&r0<rj;j=j-d)rj+d=rj;xezl+;rj+d=r0;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+)r0=ri;for(int j=i-d;j>0 &&r0>rj;j=j-d)rj+d=rj;xenl+;rj+d=r0;xenl+;xenl+;/*/直接选择排序void Zzjxzpx(int r ,int n)for(int i=1; i<n ; i+)int m=i;for(int j=i+1;j<=n;j+)if(rj<rm)m=j;zjzl+;int p;if(n!=i)p=ri;ri=rm;rm=p;zjzl+;zjzl+;void Nzjxzpx(int r ,int n)for(int i=1; i<n ; i+)int m=i;for(int j=i+1;j<=n;j+)if(rj>rm)m=j;zjnl+;int p;if(n!=i)p=ri;ri=rm;rm=p;zjnl+;zjnl+;/*/快速排序void Zkspx(int r,int left,int right)int i=left,j=right,p=rleft; while(i<j)while(i<j&&rj>=p)j-;kszl+;int m=ri;ri=rj; rj=m;kszl+;while(i<j&&ri<=p)i+;kszl+;m=rj;rj=ri;ri=m;kszl+; if(left<i-1) 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=rleft; while(i<j)while(i<j&&rj<=p)j-;ksnl+;int m=ri;ri=rj; rj=m;ksnl+;while(i<j&&ri>=p)i+;m=rj;rj=ri;ri=m;ksnl+; if(left<i-1) Nkspx(r,left,i-1); if(right>i+1) Nkspx(r,i+1,right);/*/归并排序int b100;/定义全局变量，存储Merge合并时暂时存放排序后的数组元素/真正的排序函数 比较左右两段元素 将较小数字依次暂存数组b中/将数组b暂存的排序后的元素返回数组void Copy(int r,int b,int l,int g)for(int i=l;i<=g;i+)ri=bi;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(ci<=cj)dk+=ci+;gbzl+;elsedk+=cj+;gbzl+;if(i>m)for(int q=j;q<=g;q+)dk+=cq;gbzl+;elsefor(int q=i;q<=m;q+)dk+=cq;gbzl+;/正序合并排序主函数void Zgbpx(int r,int left,int right)if(left<right)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(ci>=cj)dk+=ci+;gbnl+;elsedk+=cj+;gbnl+;if(i>m)for(int q=j;q<=g;q+)dk+=cq;gbnl+;elsefor(int q=i;q<=m;q+)dk+=cq;gbnl+;/逆序合并排序主函数void Ngbpx(int r,int left,int right)if(left<right)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<m && rj<rj+1)j+;dzl+;if(ri>rj)dzl+;break;elseint p=ri;ri=rj;rj=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<n;i+)int p=r1;r1=rn-i+1;rn-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(j<m && rj>rj+1)j+;dnl+;if(ri<rj)dnl+;break;elseint p=ri;ri=rj;rj=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<n;i+)int p=r1;r1=rn-i+1;rn-i+1=p;dnl+;Nsift(r,1,n-i);/*void main()int r1000,mr11000,cr11000,xr11000,zr11000,kr11000,gr11000,dr11000,mr21000,cr21000,xr21000,zr21000,kr21000,gr21000,dr21000;int n;cout<<"请输入排序个数"<<endl;cin>>n;cout<<"请输入"<<n<<"个要排序的数整数"<<endl;for(int i=1;i<=n;i+)cin>>ri;for(int k=1;k<=n;k+)mr1k=rk;mr2k=rk;cr1k=rk;cr2k=rk;xr1k=rk;xr2k=rk;zr1k=rk;zr2k=rk;kr1k=rk;kr2k=rk;gr1k=rk;gr2k=rk;dr1k=rk;dr2k=rk;Zmppx(mr1,n);cout<<"正序排序以后为"<<endl;for(int j=1;j<=n;j+)cout<<mr1j<<"t"cout<<endl;Nmppx(mr2,n);cout<<"逆序排序以后为"<<endl;for( j=1;j<=n;j+)cout<<mr2j<<"t"cout<<endl;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<<"冒泡正序排序时间复杂度为"<<mpzl<<"次"<<endl;cout<<"冒泡逆序排序时间复杂度为"<<mpnl<<"次"<<endl;cout<<"*"<<endl;cout<<"插入正序排序时间复杂度为"<<crzl<<"次"<<endl;cout<<"插入逆序排序时间复杂度为"<<crnl<<"次"<<endl;cout<<"*"<<endl;cout<<"希尔正序排序时间复杂度为"<<xezl<<"次"<<endl;cout<<"希尔逆序排序时间复杂度为"<<xenl<<"次"<<endl;cout<<"*"<<endl;cout<<"直接选择正序排序时间复杂度为"<<zjzl<<"次"<<endl;cout<<"直接选择逆序排序时间复杂度为"<<zjnl<<"次"<<endl;cout<<"*"<<endl;cout<<"快速正序排序时间复杂度为"<<kszl<<"次"<<endl;cout<<"快速逆序排序时间复杂度为"<<ksnl<<"次"<<endl;cout<<"*"<<endl;cout<<"归并正序排序时间复杂度为"<<gbzl<<"次"<<endl;cout<<"归并逆序排序时间复杂度为"<<gbnl<<"次"<<endl;cout<<"*"<<endl;cout<<"堆正序排序时间复杂度为"<<dzl<<"次"<<endl;cout<<"堆逆序排序时间复杂度为"<<dnl<<"次"<<endl;cout<<"*"<<endl;int p;if(mpzl<=crzl && mpzl<=xezl && mpzl<=zjzl && mpzl<=kszl && mpzl<=gbzl && mpzl<=dzl)p=1;if(crzl<mpzl && crzl<=xezl && crzl<=zjzl && crzl<=kszl && crzl<=gbzl && crzl<=dzl)p=2;if(xezl<mpzl && xezl<crzl && xezl<=zjzl && xezl<=kszl && xezl<=gbzl && xezl<=dzl)p=3;if(zjzl<mpzl && zjzl<crzl && zjzl<xezl && zjzl<=kszl && zjzl<=gbzl && zjzl<=dzl)p=4;if(kszl<mpzl && kszl<crzl && kszl<xezl && kszl<zjzl && kszl<=gbzl && kszl<=dzl)p=5;if(gbzl<mpzl && gbzl<crzl && gbzl<xezl && gbzl<zjzl && gbzl<kszl && gbzl<=dzl)p=6;if(dzl<mpzl && dzl<crzl && dzl<xezl && dzl<zjzl && dzl<kszl && dzl<gbzl)p=7;switch(p)case 1:cout<<"该数列正排序使用冒泡排序最为简便"<<endl;break;case 2:cout<<"该数列正排序使用插入排序最为简便"<<endl;break;case 3:cout<<"该数列正排序使用希尔排序最为简便"<<endl;break;case 4:cout<<"该数列正排序使用直接选择排序最为简便"<<endl;break;case 5:cout<<"该数列正排序使用快速排序最为简便"<<endl;break;case 6:cout<<"该数列正排序使用归并排序最为简便"<<endl;break;case 7:cout<<"该数列正排序使用堆排序最为简便"<<endl;break;int q;if(mpnl<=crnl && mpnl<=xenl && mpnl<=zjnl && mpnl<=ksnl && mpnl<=gbnl && mpnl<=dnl)q=1;if(crnl<mpnl && crnl<=xenl && crnl<=zjnl && crnl<=ksnl && crnl<=gbnl && crnl<=dnl)q=2;if(xenl<mpnl && xenl<crnl && xenl<=zjnl && xenl<=ksnl && xenl<=gbnl && xenl<=dnl)q=3;if(zjnl<mpnl && zjnl<crnl && zjnl<xenl && zjnl<=ksnl && zjnl<=gbnl && zjnl<=dnl)q=4;if(ksnl<mpnl && ksnl<crnl && ksnl<xenl && ksnl<zjnl && ksnl<=gbnl && ksnl<=dnl)p=5;if(gbnl<mpnl && gbnl<crnl && gbnl<xenl && gbnl<zjnl && gbnl<ksnl && gbnl<=dnl)q=6;if(dnl<mpnl && dnl<crnl && dnl<xenl && dnl<zjnl && dzl<ksnl && dnl<gbnl)q=7;switch(q)case 1:cout<<"该数列逆排序使用冒泡排序最为简便"<<endl;break;case 2:cout<<"该数列逆排序使用插入排序最为简便"<<endl;break;case 3:cout<<"该数列逆排序使用希尔排序最为简便"<<endl;break;case 4:cout<<"该数列逆排序使用直接选择排序最为简便"<<endl;break;case 5:cout<<"该数列逆排序使用快速排序最为简便"<<endl;break;case 6:cout<<"该数列逆排序使用归并排序最为简便"<<endl;break;case 7:cout<<"该数列逆排序使用堆排序最为简便"<<endl;break;运算结果