提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  前端

当前栏目

Javascript堆排序算法详解

JavaScript算法 详解 堆排序
2023-06-13 09:15:31 时间

堆排序分为两个过程：

1.建堆。

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

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

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

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

复制代码代码如下:


//调整函数
functionheadAdjust(elements,pos,len){
 //将当前节点值进行保存
 varswap=elements[pos];
 //定位到当前节点的左边的子节点
 varchild=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;
 }
}
//构建堆
functionbuildHeap(elements){
 //从最后一个拥有子节点的节点开始，将该节点连同其子节点进行比较，
 //将最大的数交换与该节点,交换后，再依次向前节点进行相同交换处理，
 //直至构建出大顶堆（升序为大顶，降序为小顶）
 for(vari=elements.length/2;i>=0;i--){
   headAdjust(elements,i,elements.length);
 }
}
functionsort(elements){
 //构建堆
 buildHeap(elements);
 //从数列的尾部开始进行调整
 for(vari=elements.length-1;i>0;i--){
   //堆顶永远是最大元素，故，将堆顶和尾部元素交换，将
   //最大元素保存于尾部，并且不参与后面的调整
   varswap=elements[i];
   elements[i]=elements[0];
   elements[0]=swap;
   //进行调整，将最大）元素调整至堆顶
   headAdjust(elements,0,i);
 }
}
varelements=[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)。

稳定性：不稳定

相关文章