




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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 ,这是
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 技术创新对产业的影响与机遇分析
- 数据中心行业的PUE优化实践案例分享
- 2025至2030内衣护理胸罩行业产业运行态势及投资规划深度研究报告
- 2025至2030转盘抛丸机行业项目调研及市场前景预测评估报告
- 2025至2030中国自行车花鼓行业发展趋势分析与未来投资战略咨询研究报告
- 2025至2030中国自动纸箱安装机行业市场占有率及投资前景评估规划报告
- 2025至2030中国自动售货机行业市场深度分析及发展预测与投资策略报告
- 2025至2030中国脱硫吸收剂行业市场占有率及投资前景评估规划报告
- 2025至2030中国脊柱侧弯支架行业产业运行态势及投资规划深度研究报告
- 2025至2030中国胸腰椎脊柱器械行业发展趋势分析与未来投资战略咨询研究报告
- 增汇减排技术与应用智慧树知到期末考试答案章节答案2024年浙江农林大学
- 2014年10月自考00730中外音乐史试题及答案含解析
- 员工关系风险防范培训课件
- 硫酸镁在产科的应用总结
- 小米智能家居解决方案
- 心脑血管预防科普课件
- 2024年中国自动焊线机市场分析报告
- 人工智能讲座
- 建设工程造价咨询成果文件质量标准(word)
- 中建八局分包入场安全指导手册v2.0
- RH精炼工艺培训教材
评论
0/150
提交评论