堆排序及算法分析.doc

《堆排序及算法分析.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、堆排序及算法分析前言记得在学习数据结构的时候一味的想用代码实现算法，重视的是写出来的代码有一个正确的输入，然后有一个正确的输出，那么就很满足了。从网上看了许多的代码，看了之后貌似懂了，自己写完之后也正确了，但是不久之后就忘了，因为大脑在回忆的时候，只依稀记得代码中的部分，那么的模糊，根本不能再次写出正确的代码，也许在第一次写的时候是因为参考了别人的代码，看过之后大脑可以进行短暂的高清晰记忆，于是欺骗了我，以为自己写出来的，满足了成就感。可是代码是计算机识别的，而我们更喜欢文字，图像。所以我们在学习算法的时候要注重算法的原理以及算法的分析，用文字，图像表达出来，然后当需

2、要用的时候再将文字转换为代码。记忆分为三个步骤：编码，存储和检索，就以学习为例，先理解知识，再归纳知识，最后巩固知识，为了以后的应用而方便检索知识。堆排序过程堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]]>=A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。既然是堆排序，自然需要先建立一个堆，而建堆的核心内容是调整堆，使二叉树满足堆的定义（每个节点的值都不大于其父节点的值）。调堆的过程应该从最后一个非叶子节点开始，假设有数组A={1,3,4,5,7,2,6

3、,8,0}。那么调堆的过程如下图，数组下标从0开始，A[3]=5开始。分别与左孩子和右孩子比较大小，如果A[3]最大，则不用调整，否则和孩子中的值最大的一个交换位置，在图1中是A[7]>A[3]>A[8]，所以A[3]与A[7]对换，从图1.1转到图1.2。所以建堆的过程就是1:for(i=headLen/2;i>=0;i++)2: 3:doAdjustHeap(A,heapLen,i)调堆：如果初始数组是非降序排序，那么就不需要调堆，直接就满足堆的定义，此为最好情况，运行时间为Θ(1)；如果初始数组是如图1.5，只有A[0]=1不满足堆的定义，经过与子节点的比较调整

4、到图1.6，但是图1.6仍然不满足堆的定义，所以要递归调整，一直到满足堆的定义或者到堆底为止。如果递归调堆到堆底才结束，那么是最坏情况，运行时间为O(h)(h为需要调整的节点的高度，堆底高度为0，堆顶高度为floor(logn))。建堆完成之后，堆如图1.7是个大根堆。将A[0]=8与A[heapLen-1]交换,然后heapLen减一，如图2.1，然后AdjustHeap(A,heapLen-1,0)，如图2.2。如此交换堆的第一个元素和堆的最后一个元素，然后堆的大小heapLen减一，对堆的大小为heapLen的堆进行调堆，如此循环，直到heapLen==1时停止

5、，最后得出结果如图3。1:/*2:输入：数组A，堆的长度hLen，以及需要调整的节点i3:功能：调堆4:*/5: 6:voidAdjustHeap(intA[],inthLen,inti)7:{8:intleft=LeftChild(i);//节点i的左孩子9:intright=RightChild(i);//节点i的右孩子节点10:intlargest=i;11:inttemp;12: 13:while(left

6、

7、right

8、18:}19:20:if(right

9、}39:}40:}41: 42:/*43:输入：数组A，堆的大小hLen44:功能：建堆45:*/46:voidBuildHeap(intA[],inthLen)47:{48:inti;49:intbegin=hLen/2-1;//最后一个非叶子节点50:for(i=begin;i>=0;i--)51:{52:AdjustHeap(A,hLen,i);53:}54:}55: 56:/*57:输入：数组A，待排序数组的大小aLen58:功能：堆排序59:*/60:voidHeapSort(intA[],intaLen)61:{62:inthLen=aL