Javascript堆排序算法详解

2019-07-24 作者:网站首页   |   浏览(131)

堆排序分为两个过程:

Javascript堆排序算法详解,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)。

稳定性:不稳定

堆排序分为两个过程: 1.建堆。 堆实质上是完全二叉树,必须满足:树中任一非叶子结点的关键字...

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)。

稳定性:不稳定

您可能感兴趣的文章:

  • JavaScript希尔排序、快速排序、归并排序算法
  • javascript快速排序算法详解
  • JS实现冒泡排序,插入排序和快速排序并排序输出
  • js实现数组冒泡排序、快速排序原理
  • JavaScript排序算法之希尔排序的2个实例
  • 基于JavaScript实现的希尔排序算法分析
  • JavaScript中几种常见排序算法小结
  • JS折半插入排序算法实例
  • JS排序算法之希尔排序与快速排序实现方法

本文由yzc216亚洲城发布于网站首页,转载请注明出处:Javascript堆排序算法详解

关键词: yzc216亚洲城