JS 实现堆排序

关于堆排序的介绍，可以参考 leetcode 某大佬的文章【动画模拟】一个破堆排我搞了四个动画，本文严重参考了该文章

代码实现

/**
 * 堆排序
 *
 * 因为大顶堆（或小顶堆）一定是一颗完全二叉树，当我们用数组表示完全二叉树时，有如下规律：
 *
 * （1）左子树在数组中的位置 = 2 * i + 1
 *
 * （2）右子树在数组中的位置 = 2 * i + 2
 *
 * 其中i为左右子树的父节点在数组中的位置
 *
 * @param {*} nums 要排序的数组
 * @returns
 */
var heapSort = function (nums) {
  // 大顶堆
  const len = nums.length;
  // 最后一个非叶子节点，即最后一个父结点
  let lastParent = Math.trunc(len / 2) - 1;
  // 从后往前构建大顶堆
  for (let i = lastParent; i >= 0; i--) {
    sink(nums, i, len);
  }
  let temp = len - 1;
  while (temp > 0) {
    // 将大顶堆的根结点交换到数组的最后一个位置
    swap(nums, 0, temp--);
    // 将新的根结点下沉到合适的位置，重新构建大顶堆
    sink(nums, 0, temp);
  }
  return nums;
};
/**
 * 下沉节点
 * @param {*} nums 数组
 * @param {*} parentIndex 父节点的下标
 * @param {*} end 下沉结束的位置
 * @returns
 */
function sink(nums, parentIndex, end) {
  // 左子节点对应的下标
  let lIndex = parentIndex * 2 + 1;
  // 右子节点对应的下标
  let rIndex = lIndex + 1;
  // 如果左子节点不存在，那么右子节点一定也不存在，当前节点已经是叶子节点了，无需下沉
  if (lIndex > end) return;
  // 默认认为左子结点的值大于右子节点的值，即nums[lIndex] > nums[rIndex]
  let maxIndex = lIndex;
  // 找到左右子节点中的较大值
  if (rIndex <= end && nums[lIndex] < nums[rIndex]) {
    maxIndex = rIndex;
  }
  // 如果左右子节点中的较大值 > 父节点的值，那么交换较大值和父节点
  if (nums[maxIndex] > nums[parentIndex]) {
    // 交换nums[lIndex] 和nums[parentIndex]
    swap(nums, maxIndex, parentIndex);
    // 交换节点值之后，将交换后的子节点作为新的父节点继续下沉,直到合适的位置
    sink(nums, maxIndex, end);
  }
}
function swap(nums, i, j) {
  // 通过[a,b]=[b,a]的方式交换a,b的值
  [nums[i], nums[j]] = [nums[j], nums[i]];
}
JavaScript

测试

console.log(heapSort([5, 2, 3, 1, 4, 7, 8, 6]));
// [ 1, 2, 3, 4, 5, 6, 7, 8]
JavaScript