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

《算法与数据结构程设计报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法与数据结构程设计报告一．设计题目：堆排序的算法二．运行环境：1、硬件：计算机2、软件：MicrosoftVisualC++6.0三．目的和意义：目的：创建一个大堆，按从大到小顺序输出堆元素，实现堆排序。意义：利用堆排序，即使在最坏情况下的时间复杂度也是O(nlog2n)，相对于快速排序来说，时间复杂度小，这是堆排序的最大优点，可用于对若干元素进行排序，加快排序速度。四．算法设计的基本思想：堆排序算法设计基本思想：堆排序利用了大根堆堆顶记录的关键字最大这一特征，使得在当前无序区中选取最大关键字的记录变得简单。先将初始文件

2、R[1..n]建成一个大根堆，此堆为初始的无序区。再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录r[n]交换，由此得到新的无序区r[1..n-1]和有序区r[n]，且满足r[1..n-1].keys≤r[n].key。由于交换后新的根R[1]可能违反堆性质，故应将当前无序区r[1..n-1]调整为堆。然后再次将r[1..n-1]中关键字最大的记录r[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区r[1..n-2]和有序区r[n-1..n]，且仍满足关系r[1..n-2].keys≤r[n-1.

3、.n].keys，同样要将r[1..n-2]调整为堆。直到无序区只有一个元素为止.五．程序流程图：流程图1输入数组长度len的值I=0i=sum-1调用建堆函数build()I--I

4、排序数组函数prntar()Printf(“----------------“);printf("排序结果：")调用调用打印数组函数prnt()printf("==============================")调用getch()..k=i;j=2*k+1J=a[j]tmp=a[k]返回主调函数a[k]=a[j]a[j]=tmp流程图2：建堆函数build()流程图3：打印数组函数print()printf("")i

5、0printf("%3d",a[i])i++printf("")h=0,sum=0,item=1;`size=b2-b1+1;Ysum<=sizeNsum+=itemh++item*=2item=1;cnt=0;start=b1;tmp=1;printf("----------------------")；printf("堆：")真YNisize-1输出a[cnt++]j++j++j++

6、printf("")tmp*=2i++流程图4：打印堆函数prnthp()五．算法设计分析： 性能分析：堆排序的时间主要由建立初始堆和不断重复建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。其中：建立初始堆时，总共需进行的关键字比较次数≤4n=O(n);排序过程中进行n-1次重建堆所进行的总比较次数不超过下式：2*(└log2(n-1)┘+└log2(n-2)┘+…+└log22┘)<2n└log2n┘=O(nlog2n)因此堆排序总的时间复杂度是O(n+nlog2n)=O(nlog2n)。堆排序在最

7、坏情况下的时间复杂度也是O(nlog2n)，相对于快速排序来说，这是堆排序的最大优点。另外，堆排序仅需一个记录大小供交换用的辅助空间。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录较少的文件，但对n较大的文件还是很有效的。堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。堆的描述：堆排序(HeapSort)是一树形选择排序。堆是对基于数组的树的重要应用场合之一。它是节点间具有层次次序关系的完全二叉树。其中，父节点值大于或等于其孩子节点值的，叫“最大堆（maximumheap）”;父节点值小于或等于孩子节点

8、值的，叫“最小堆（minimumheap）”.在最大堆中，根中的元素值最大；在最小堆中，根中的元素值最小。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。从算法描述来看，堆排