资源描述：
《堆排序与斐波那契查找.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、堆排序堆上图，就是一个完全二叉树，其特点在于：从作为第一层的根开始，除了最后一层之外，第N层的元素个数都必须是2的N次方；第一层一个元素，第二层4个，第三层8个，以此类推。而最后一行的元素，都要紧贴在左边，具备了这两个特点的树，就是一棵完全二叉树。在满足作为完全二叉树的基础上，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值；这样层层递推，就是根节点的值最小，这样的树，称为大顶堆。同理，又有一棵完全二叉树，对于任意一个子节点来说，均不大于其父节点的值，如此递推，就是根节点的值是最大的，这样的数，称为小顶堆。堆排序对于堆排序
2、来说，我们先要做的是，把待排序的一堆无序的数，整理成一个大顶堆，或者小顶堆。将堆顶元素与末尾元素进行交换，使末尾元素最大或最小。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序从最后一个非叶子结点开始，从左至右，从下至上进行调整。找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。步骤二将堆顶元素与末尾元素进行交换，使末尾元
3、素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。建立堆varlen;//因为声明的多个函数都需要数据长度，所以把len设置成为全局变量functionbuildMaxHeap(arr){//建立大顶堆len=arr.length;for(vari=Math.floor(len/2);i>=0;i--){heapify(arr,i);}}堆调整函数functionheapify(arr,i){//堆调整varleft=2*i+1,right=2*i+2,largest=i;if(le
4、ftarr[largest]){largest=left;}if(rightarr[largest]){largest=right;}if(largest!=i){swap(arr,i,largest);heapify(arr,largest);}}交换函数functionswap(arr,i,j){vartemp=arr[i];arr[i]=arr[j];arr[j]=temp;}堆排序函数functionheapSort(arr){buildMaxHeap(ar
5、r);for(vari=arr.length-1;i>0;i--){swap(arr,0,i);len--;heapify(arr,0);}returnarr;}斐波那契查找黄金分割0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。斐波那契数列：1,1,2,3,5,8,13,21,34,55,89…….然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将
6、黄金比例运用到查找技术中。基本思想基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。相对于二分查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种：1）相等，mid位置的
7、元素即为所求2）>，low=mid+1,k-=2;说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2说明范围[mid+1,high]内的元素个数为n-(F(k-1))=Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。3）<，high=mid-1,k-=1。说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找。复杂度分析：最坏情况
8、下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。表中记录的个数为某个斐波那契数小1，即：n=F(k)-1，这是为什么呢？是为了格式上的统一，表中的数据是F(k)-1个，使用mid值进行分割又用掉一个，那么剩下F(k)-2个。正
