堆排序与斐波那契查找

1、堆排序堆 上图，就是一个完全二叉树，其特点在于： 从作为第一层的根开始，除了最后一层之外，第N层的元素个数都必须是2的N次方；第一层一个元素，第二层4个，第三层8个，以此类推。 而最后一行的元素，都要紧贴在左边，具备了这两个特点的树，就是一棵完全二叉树。 在满足作为完全二叉树的基础上，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值；这样层层递推，就是根节点的值最小，这样的树，称为大顶堆。 同理，又有一棵完全二叉树，对于任意一个子节点来说，均不大于其父节点的值，如此递推，就是根节点的值是最大的，这样的数，称为小顶堆。堆排序 对于堆排序来说，我们先要做的是，把待排序的一堆无序的数，整理成

2、一 个大顶堆，或者小顶堆。 将堆顶元素与末尾元素进行交换，使末尾元素最大或最小。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序从最后一个非叶子结点开始，从左至右，从下至上进行调整。找到第二个非叶节点4，由于4,9,8中9元素最大，4和9交换。这时，交换导致了子根4,5,6结构混乱，继续调整，4,5,6中6最大，交换4和6。步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。建立堆 var len

3、; / 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量 function buildMaxHeap(arr) / 建立大顶堆 len = arr.length; for (var i = Math.floor(len/2); i = 0; i-) heapify(arr, i); 堆调整函数function heapify(arr, i) / 堆调整 var left = 2 * i + 1, right = 2 * i + 2, largest = i; if (left arrlargest) largest = left; if (right arrlargest) la

4、rgest = right; if (largest != i) swap(arr, i, largest); heapify(arr, largest); 交换函数 function swap(arr, i, j) var temp = arri; arri = arr j; arr j = temp; 堆排序函数 function heapSort(arr) buildMaxHeap(arr); for (var i = arr.length - 1; i 0; i-) swap(arr, 0, i); len-; heapify(arr, 0); return arr; 0.618被公认

5、为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。 斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。基本思想 基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。 相对于二分查找，一般将待比较的key值与第mid=（low+

6、high）/2位置的元素比较 斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1; 开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种： 1）相等，mid位置的元素即为所求 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）= 0; i-) heapify(arr, i); 堆调整函数function heapify(arr, i) / 堆调整 var left = 2 * i + 1, right = 2 * i + 2, largest = i; if (left arrlargest) largest = left; if (right arrlargest) largest = right; if (largest != i) swap(arr, i, largest); heapify(arr, largest); 表中记录的个数为某个斐波那契数小1，即：n=F(k)-1 ，这是