算法与数据结构程设计报告.doc

算法与数据结构程设计报告一 设计题目： 堆排序的算法二运行环境：1、 硬件：计算机2、 软件：microsoft visual c+6.0三目的和意义：目的：创建一个大堆，按从大到小顺序输出堆元素，实现堆排序。意义：利用堆排序，即使在最坏情况下的时间复杂度也是o(nlog2n)，相对于快速排序来说，时间复杂度小，这是堆排序的最大优点，可用于对若干元素进行排序，加快排序速度。四算法设计的基本思想：堆排序算法设计基本思想：堆排序利用了大根堆堆顶记录的关键字最大这一特征，使得在当前无序区中选取最大关键字的记录变得简单。先将初始文件r1.n建成一个大根堆，此堆为初始的无序区。再将关键字最大的记录r1(即堆顶)和无序区的最后一个记录rn交换，由此得到新的无序区r1.n-1和有序区rn，且满足r1.n-1.keysrn.key。由于交换后新的根r1可能违反堆性质，故应将当前无序区r1.n-1调整为堆。然后再次将r1.n-1中关键字最大的记录r1和该区间的最后一个记录rn-1交换，由此得到新的无序区r1.n-2和有序区rn-1.n，且仍满足关系r1.n-2.keysrn-1.n.keys，同样要将r1.n-2调整为堆。直到无序区只有一个元素为止.五 程序流程图： 流程图1 输入数组长度len的值 ilen i=0输入aii+temp=1;sum=0;sum+tem=0i=sum-1调用建堆函数build()i-ilen-1i=0tmp=a0;a0=alen-1-i;alen-1-i=tmp; 调用建堆函数build()调用打印队函数prnthp() 调用打印已排序数组函数prntar()printf(“-“); printf(n 排序结果：n) 调用调用打印数组函数prnt()printf(n=nn)调用getch(). k=i; j=2*k+1 jn yjn & aj=ajtmp=ak 返回主调函数ak=ajaj=tmp 流程图2：建堆函数build()流程图3：打印数组函数print() printf(n) in i=0printf(%3d,ai)i+printf(n)h=0,sum=0,item=1; size=b2-b1+1;ysum=sizen sum+=itemh+item*=2 item=1;cnt=0;start=b1;tmp=1;printf(n-n)；printf( 堆：n)真 y n ih i=0jh-i j=0 打印空格 ji+1 j=0 打印空格 jsize-1输出acnt+ j+ j+ j+ printf(n)tmp*=2 i+流程图4：打印堆函数prnthp()六 算法设计分析：性能分析：堆排序的时间主要由建立初始堆和不断重复建堆这两部分的时间开销构成,它们均是通过调用heapify实现的。其中：建立初始堆时，总共需进行的关键字比较次数 4n =o(n) ;排序过程中进行n-1次重建堆所进行的总比较次数不超过下式： 2*( log2(n-1) + log2(n-2) + log22 ) 2n log2n =o(n log2n)因此堆排序总的时间复杂度是 o(n+ n log2n)= o(n log2n)。堆排序在最坏情况下的时间复杂度也是o(nlog2n)，相对于快速排序来说，这是堆排序的最大优点。另外，堆排序仅需一个记录大小供交换用的辅助空间。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录较少的文件，但对n较大的文件还是很有效的。堆排序是就地排序，辅助空间为o(1)，它是不稳定的排序方法。堆的描述：堆排序(heapsort)是一树形选择排序。堆是对基于数组的树的重要应用场合之一。它是节点间具有层次次序关系的完全二叉树。其中，父节点值大于或等于其孩子节点值的，叫“最大堆（maximum heap）”;父节点值小于或等于孩子节点值的，叫“最小堆（minimum heap）”.在最大堆中，根中的元素值最大；在最小堆中，根中的元素值最小。堆排序的特点是：在排序过程中，将rl.n看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 堆的存储特点 ：在这里，讨论作为顺序表存储的堆。它是按某种次序将一系列数据以完全二叉树形式存放的一种表。它要求堆中的节点的值都大于或等于其孩子节点的值。 按照这种存储方式，可知第i个元素的左右儿子分别是第2i和第2i+1个元素，而它的父亲节点是第i/2个元素。由于父亲节点和儿子节点具有这样的顺序关系，所以可以方便地由父亲节点找到儿子节点，反之亦然。可见，这种存储方式大大节省了存储空间，高效快速。 堆的相关操作 ：作为抽象表结构，堆允许增加和删除表项。插入过程不用假定新表项占有一个特定的位置而只需维持堆顺序。但是删除操作总是删去表中的最大项 （根）。 堆可以用于那些客户程序想直接访问最大（小）元素的场合。作为表，堆并不提供find操作，而对表的直接访问是只读的。所有的堆处理算法都有责任更新树和维持堆顺序。 1.建堆：数组具有对应的树表示形式。一般情况下，树并不满足堆的条件。通过重新排列元素，可以建立一棵“堆化”的树。 2.插入一个元素：新元素被加入到表中，随后树被更新以恢复堆次序。例如，下面的步骤将15加入到表中。 3.删除一个元素：删除总是发生在根节点处。用表中的最后一个元素来填补空缺位置，结果树被更新以恢复堆条件。 在堆实现时我们是采用数组来存储堆的完全二叉树表示，并且用一种有效的算法来保证对堆的所有操作不破坏堆的性质。这种表示的主要问题在于数组的大小需要事先确定，这使得对堆的大小有了一个初始的限定。在堆中数据增长到超过这个界限时虽然可以通过复制的方法建立更大的向量来存放堆，但整个向量的复制是不可避免的，这大大降低了操作效率。为避免这个问题，可把二叉树的顺序存储改为二叉树的链表存储 . 根据算法复杂性分析的结果。williams&floyd在1964年提出的堆排序算法在最坏情况的时间复杂性为2nlogn+o(n)。但在判定树的模型下，为n个数排序的算法时间复杂性的下界为nlogn+o(n)。可见，williams&floyd的算法或许可以改进。其中在进入实质性排序的第i步，在把第i大元素（在堆顶）与当时处在第i大的目标位置的元素对调之后，总是让堆顶元素往下沉，可能直到叶子才完成局部（重新）堆化。如果当时处在第i大的目标位置元素很小，则下沉过程中要做很多次的比较。如果能把这个次数降下来，或许能对williams&floyd的算法作出效率上的显著改进。顾训穰，诸宇章就是这样循着发现问题、提出问题、分析问题和解决问题的线索，通过让空缺结点一下下沉h/2达到改进的目的，于1994年在软件学报上发表他们的成果。改进后的堆排序算法在最坏情况下的时间复杂性为nlogn+nloglogn+o(n)主项系数由2降为1，与下界的主项系数同。 进一步，王晓东、傅清祥等还是沿着发现问题、提出问题、分析问题和解决问题的思路，发现顾训穰、诸宇章的算法可以通过让空缺结点下沉f(h)=h-logh(不是h/2)改进其时间复杂性的次项，于1996年在软件学报上发表他们的成果。进一步改进后的堆排序算法在最最坏情况下的时间复杂性为nlogn+n3(n)+o(n)其中，函数x=3(y)是3阶ackerman函数y=a(x，3)的逆函数。众多的反映表明以上的设计是可取的。七 源代码： 程序源代码如下：/* name: heapsort2.c author: huangxing description: 堆排序算法的过程演示 date: 30/11/2005 copyright: */#include#define n 6int k,j;/* 建堆函数 */void build(int *a,int i,int n) int tmp; k=i; j=2*k+1; while(j=n) if(jn & aj=aj)break; tmp=ak; ak=aj; aj=tmp; k=j; j=2*j+1; /* 打印数组函数 */void prnt(int *a,int n) int i; printf(n); for(i=0;in;i+) printf(%3d,ai); printf(n);/* 打印堆函数 */void prnthp(int *a,int b1,int b2) int size; int h=0,sum=0,item=1; int i,j,cnt,start,tmp; size=b2-b1+1; while(sum=size) sum+=item; h+; item*=2; item=1; cnt=0; start=b1; tmp=1; printf(n-n); printf( 堆：n); while(1) for(i=0;ih;i+) for(j=0;jh-i;j+) printf( ); for(j=0;ji+1;j+)printf( ); for(j=0;jsize-1)goto end; printf(%4d,acnt+); printf(n); tmp*=2; end: printf(n); return; /* 打印已排序数组函数 */void prntar(int *a,int b2,int len) int i; printf( 已排序：n); for(i=0;ib2;i+) printf( ); for(i=b2;i=len;i+) printf(%3d,ai); printf(n); main() /* int a=-1,2,5,1,0,-3,-2,8,6; */ int a50; int i; int tmp; int sum; int num; int len; printf( 堆排序n); printf(n=n); printf(n 请输入待排序数组个数,以回车结束：n); scanf(%3d,&len); printf(n 请输入待排序数组,以回车结束：n); for(i=0;ilen;i+) scanf(%3d,&ai); tmp=1;sum=0; while(sum+tmp=0;i-) build(a,i,len-1); prnthp(a,0,len-1); /* 改建堆 */ for(i=0;ilen-1;i+) tmp=a0; a0=alen-1-i; alen-1-i=tmp; build(a,0,len-2-i); prnthp(a,0,len-2-i); prntar(a,len-1-i,len-1); printf(n-n); printf(n 排序结果：n); prnt(a,len); printf(n=nn); getch();八 程序调试过程分析： 程序刚开始运行不了，错误达8处，于是本人就认真检查，居然发现有6处不是写错了符号就是少了括号，粗心之至。于是改过来，但还有2处错误怎么也改不好，也不知道错在哪里。于是问同学，上网查资料，发帖子求助，终于搞明白，也改过来了，原来是调用函数时出的错。现在程序改好，可以正常运行了，以下就可以看到程序运行结果。九 运行结果及分析：经过不断调试，确保程序无误后，输入执行程序，会得到以下程序结果：我们随便举一例，假若我们输入8回车，会得到下面结果：我们再随便输入8个数，如果输入的是以下8个数字：6 9 5 8 7 0 -3 8再回车就能看到程序最后执行的结果，如下： 十、小结： 经过几天的不断努力，课程设计终于完成了，但肯定还存在许多不足，在这里有一点心得，堆就是一个关键字序列，对于堆排序，归结起来，有两个步骤：（1）建堆；（2）反复调整堆。对于给定的序列，用堆排序的过程主要是通过画完全二叉树来演示。通过这个课题，复习了许多没搞懂的地方，也通过这比较了与别的排序法的区别，例如堆排序与直接插入排序的区别：直接选择排序中，为了从r1.n中选出关键字最小的记录，必须进行n-1次比较，然后在r2.n中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些