Javascript堆排序算法详解_Javascript教程-查字典教程网
Javascript堆排序算法详解
Javascript堆排序算法详解
发布时间:2016-12-30 来源:查字典编辑
摘要:堆排序分为两个过程: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教程学习
    编程开发子分类