Javascript堆排序算法详解

堆排序分为两个过程：

1.建堆。

堆实质上是完全二叉树，必须满足：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。

堆分为：大根堆和小根堆，升序排序采用大根堆，降序排序采用小根堆。

如果是大根堆，则通过调整函数将值最大的节点调整至堆根。

2.将堆根保存于尾部，并对剩余序列调用调整函数，调整完成后，再将最大跟保存于尾部-1（-1，-2，...，-i），再对剩余序列进行调整，反复进行该过程，直至排序完成。

代码如下:

//调整函数
function headAdjust(elements, pos, len){
  //将当前节点值进行保存
  var swap = elements[pos];
  //定位到当前节点的左边的子节点
  var child = pos * 2 + 1;
  //递归，直至没有子节点为止
  while(child < len){
    //如果当前节点有右边的子节点，并且右子节点较大的场合，采用右子节点
    //和当前节点进行比较
    if(child + 1 < len && elements[child] < elements[child + 1]){
      child += 1;
    }
    //比较当前节点和最大的子节点，小于则进行值交换，交换后将当前节点定位
    //于子节点上
    if(elements[pos] < elements[child]){
      elements[pos] = elements[child];
      pos = child;
      child = pos * 2 + 1;
    }
    else{
      break;
    }
    elements[pos] = swap;
  }
}
//构建堆
function buildHeap(elements){
  //从最后一个拥有子节点的节点开始，将该节点连同其子节点进行比较，
  //将最大的数交换与该节点,交换后，再依次向前节点进行相同交换处理，
  //直至构建出大顶堆（升序为大顶，降序为小顶）
  for(var i=elements.length/2; i>=0; i--){
    headAdjust(elements, i, elements.length);
  }
}
function sort(elements){
  //构建堆
  buildHeap(elements);
  //从数列的尾部开始进行调整
  for(var i=elements.length-1; i>0; i--){
    //堆顶永远是最大元素，故，将堆顶和尾部元素交换，将
    //最大元素保存于尾部，并且不参与后面的调整
    var swap = elements[i];
    elements[i] = elements[0];
    elements[0] = swap;
    //进行调整，将最大）元素调整至堆顶
    headAdjust(elements, 0, i);
  }
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements);
console.log(' after: ' + elements);

效率：

时间复杂度：最好：O(nlog2n)，最坏：O(nlog2n)，平均：O(nlog2n)。

空间复杂度：O(1)。

稳定性：不稳定

赞 (0)

相关推荐

  • JavaScript实现显示函数调用堆栈的方法

    本文实例讲述了JavaScript实现显示函数调用堆栈的方法.分享给大家供大家参考,具体如下: 许多大型的JavaScript应用程序间的函数调用关系是非常复杂的,在开发或者调试过程中,经常需要跟踪某个函数是由哪些函数调用后才触发执行的,弄清楚这些函数的调用顺序对我们理解代码的数据流向是非常重要的. Firebug提供了console.trace()来显示函数堆栈,在需要调试的地方加上下面的一行代码就能显示该函数调用时的上下文关系.IE6就没有这么方便了,它没有提供显示函数堆栈的工具,当不可避免

  • JS实现队列与堆栈的方法

    JS实现队列与堆栈的方法

    本文实例讲述了JS实现队列与堆栈的方法.分享给大家供大家参考,具体如下: 在面向对象的程序设计里,一般都提供了实现队列(queue)和堆栈(stack)的方法,而对于JS来说,我们可以实现数组的相关操作,来实现队列和堆栈的功能,看下面的相关介绍. 一.看一下它们的性质,这种性质决定了它们的使用场合 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 二.看一下实现的代码(JS代码) var a=new

  • JavaScript调用堆栈及setTimeout使用方法深入剖析

    Javascript中会经常用到setTimeout来推迟一个函数的执行,如: 复制代码 代码如下: setTimeout(function(){alert("Hello World");},1000); 会在执行到这句话后延迟1秒钟来弹出alert窗口.那么再看这一段: 复制代码 代码如下: function a(){ setTimeout(function() {alert(1)}, 0); alert(2); } a(); 注意这段代码中的setTimeout延迟设为了0,就是延

  • java自带的工具Jstack截取进程中的堆栈信息

    java自带的工具Jstack截取进程中的堆栈信息

    在Java软件的使用过程中,有时会莫名的出现奇怪的问题.而这些问题常常无法使用日志信息定位,这时我们就需要通过查看进程内部线程的堆栈调用关系来分析问题出在哪里. 举个例子,当我们在做某个操作时,莫名的会弹出多个警告框,其中有些信息是正常的,有些则不是.对于这些错误的警告信息,我们该如何定位是哪个位置的代码出现了错误弹出的框呢? 我们就需要在弹框以后,去查看软件的各个线程,去查找究竟是哪个线程导致了该问题.可是有时因为环境.时间等问题,我们根本不能拿着IDE去调试, 只能通过工具软件拍下内存快照,

  • JavaScript数组实现数据结构中的队列与堆栈

    JavaScript数组实现数据结构中的队列与堆栈

    一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组

  • 详解堆的javascript实现方法

    堆的定义 最大(最小)堆是一棵每一个节点的键值都不小于(大于)其孩子(如果存在)的键值的树.大顶堆是一棵完全二叉树,同时也是一棵最大树.小顶堆是一棵完全完全二叉树,同时也是一棵最小树. 另外,记住这两个概念,对写代码太重要了: 1.父节点和子节点的关系:看定义 2.完全二叉树:参考[2] 基本操作 1.Build(构建堆) 2.Insert(插入) 3.Delete(删除:最小或者最大的那个) 代码实现 首先,写代码前有两个非常重要的点: 1.用一个数组就可以作为堆的存储结构,非常简单而且易操作

  • JavaScript把数组作为堆栈使用的方法

    本文实例讲述了JavaScript把数组作为堆栈使用的方法.分享给大家供大家参考.具体如下: JavaScript把数组作为堆栈使用的代码范例,支持堆栈常用的push和pop方法 <script type="text/javascript"> var numbers = ["one", "two", "three", "four"]; numbers.push("five")

  • 使用堆实现Top K算法（JS实现）

    先来聊一聊Top K算法,具体内容如下 应用场景: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节.         假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个.一个查询串的重复度越高,说明查询它的用户越多,也就是越热门.),请你统计最热门的10个查询串,要求使用的内存不能超过1G. 必备知识: 什么是哈希表?         哈希表(Hash table,也叫散列表),是根据关键码值(K

  • js自动生成的元素与页面原有元素发生堆叠的解决方法

    js自动生成的元素与页面原有元素发生堆叠的解决方法

     商品属性和商品规格是js动态生成的元素,商品扩展信息的两个文本框是原有的元素,他们发生堆叠,我以为是我生成的元素所在div大小不固定导致的,因为商品规格的下面复选框是第二次ajax生成的,我怀疑第二次ajax是不是不能将页面原有元素向下推到合适的位置. 搞了几个小时,尝试固定元素所在容器div的的大小,但是不好固定啊,元素的个数是不定的,尝试改变属性和规格的生成顺序,属性部分堆到规格部分上去了,规格部分的元素怎么不独立占位置呢,后来才想到会不会是浮动了,去除浮动,给原有元素(商品扩展信息部分)

  • Javascript堆排序算法详解

    堆排序分为两个过程: 1.建堆. 堆实质上是完全二叉树,必须满足:树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. 堆分为:大根堆和小根堆,升序排序采用大根堆,降序排序采用小根堆. 如果是大根堆,则通过调整函数将值最大的节点调整至堆根. 2.将堆根保存于尾部,并对剩余序列调用调整函数,调整完成后,再将最大跟保存于尾部-1(-1,-2,...,-i),再对剩余序列进行调整,反复进行该过程,直至排序完成. 复制代码 代码如下: //调整函数 function head

  • PHP实现的堆排序算法详解

    PHP实现的堆排序算法详解

    本文实例讲述了PHP实现的堆排序算法.分享给大家供大家参考,具体如下: 经验 工作了,面试我工作这家公司时被技术面打击得不行,因为自己的数据结构等基础学得实在太差,虽然原来是想做设计师的说...不过看在PHP写得还凑合的份上能来实习了,但还是决心恶补一下基础. 其实自己之前也确实感觉到了基础的重要性,一些比较深的东西都比较底层,不学好根本没法进行.像我之前用PHP做websocket,就牵扯到数据包.数据帧等概念,搞不清楚,连数据都没法处理,还得后来补.所以我准备重新学一下数据结构,算法,网络等

  • Java堆排序算法详解

    堆是数据结构中的一种重要结构,了解"堆"的概念和操作,可以帮助我们快速地掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+

  • Javascript快速排序算法详解

    快速排序是对冒泡排序的一种改进.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,最终达到整个数据变成有序序列. 假设要排序的数组是A[0]--A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为基准数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序.值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对

  • Javascript冒泡排序算法详解

    比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 复制代码 代码如下: function sort(elements){   for(var i=0;i<elements.length-1;i++){     for(var j=0;j<elements.length-i-

  • 前端JavaScript多数元素的算法详解

    目录 题目:多数元素 方法一:map 实现 方法二:排序 题目:多数元素 给定一个大小为 n 的数组 nums ,返回其中的多数元素.多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素. 你可以假设数组是非空的,并且给定的数组总是存在多数元素. 示例 1: 输入: nums = [3,2,3]输出: 3 示例 2: 输入: nums = [2,2,1,1,1,2,2]输出: 2 提示: n == nums.length 1 <= n <= 5 * 104 -109 <= nums

  • Js面试算法详解

    素数 Q:你将如何验证一个素数? A:一个素数只能被它自己和1整除.所以,我将运行一个while循环并加1.(看代码示例,如果你无法理解,那这不是你的菜.先回去学习javaScript基础知识然后再回来吧.) 方法1 function isPrime(n){ var divisor = 2; while (n > divisor){ if(n % divisor == 0){ return false; } else divisor++; } return true; } isPrime(137

  • JavaScript WeakMap使用详解

    WeakMap 对象是一组键/值对的集合,其中的键是弱引用的.其键必须是对象,而值可以是任意的. 语法 new WeakMap([iterable]) 参数 iterable Iterable 是一个数组(二元数组)或者其他可迭代的且其元素是键值对的对象.每个键值对会被加到新的 WeakMap 里.null 会被当做 undefined. 描述 WeakMap 的 key 只能是 Object 类型. 原始数据类型 是不能作为 key 的(比如 Symbol). Why WeakMap? 在 J

  • JavaScript Reduce使用详解

    JavaScript Reduce使用详解

    学会这一个技巧 Reduce 让你开启编程新世界 Learning This Reduce Skill and a Whole New World Will Open up for You

  • Python实现堆排序案例详解

    Python实现堆排序案例详解

    Python实现堆排序 一.堆排序简介 堆排序(Heap Sort)是利用堆这种数据结构所设计的一种排序算法. 堆的结构是一棵完全二叉树的结构,并且满足堆积的性质:每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点. 关于二叉树和完全二叉树的介绍可以参考:https://blog.csdn.net/weixin_43790276/article/details/104737870 堆排序先按从上到下.从左到右的顺序将待排序列表中的元素构造成一棵完全二叉树,然后对完全二叉树进行调整,使

随机推荐