|
这篇文章主要介绍了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)。
稳定性：不稳定 | 
发表于 2018-12-25 05:44:56
