JavaScript堆排序算法详解：原理、实现与复杂度分析

堆排序原理概述

堆排序主要包含两个核心阶段：

第一阶段是构建堆结构。

堆在数据结构上表现为完全二叉树，需满足特定性质：任意非叶子节点的关键字值不得大于（或不得小于）其左右子节点的关键字值（若子节点存在）。

根据排序需求，堆可分为大根堆和小根堆。若需执行升序排序，应构建大根堆；若需执行降序排序，则应构建小根堆。

在大根堆中，通过调整函数确保最大值节点被移动至堆顶位置。

第二阶段是排序过程。首先将堆顶元素（最大值）保存至数组末尾，随后对剩余未排序序列调用调整函数。调整后，再次将新的最大值保存至倒数第二个位置（即索引-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)。

稳定性：不稳定排序算法。