Javascript堆排序算法详解
堆排序分为两个过程：
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)。
稳定性：不稳定
热门推荐
10 对患者生日祝福语简短
11 结婚祝福语简短装备
12 周岁祝福语学生文案简短
13 订婚领证祝福语简短精辟
14 导师获奖祝福语大全简短
15 新婚购房祝福语简短精辟
16 牛年祝福语简短的爱人
17 送芒果的祝福语简短
18 送给学长毕业祝福语简短