在 JavaScript 中实现堆排序算法

简介

在本实验中，我们将探索如何在 JavaScript 中实现堆排序算法。堆排序是一种基于比较的排序算法，其工作原理是将数组划分为已排序区域和未排序区域，并通过提取最大元素并将其移动到已排序区域来迭代缩小未排序区域。通过本实验，你将更深入地理解堆排序算法的工作原理，以及如何在 JavaScript 中使用递归和闭包来实现它。

堆排序算法

要进行编码练习，请打开终端/SSH 并输入“node”。以下算法使用堆排序算法对数字数组进行排序。请按照以下步骤操作：

• 在函数中使用递归。
• 使用展开运算符（...）克隆原始数组arr。
• 使用闭包声明一个变量l和一个函数heapify。
• 使用for循环和Math.floor()并结合heapify从数组创建一个最大堆。
• 使用for循环反复缩小考虑的范围，使用heapify并在必要时交换值以对克隆数组进行排序。

const heapsort = (arr) => {
  const a = [...arr];
  let l = a.length;
  const heapify = (a, i) => {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let max = i;
    if (left < l && a[left] > a[max]) max = left;
    if (right < l && a[right] > a[max]) max = right;
    if (max !== i) {
      [a[max], a[i]] = [a[i], a[max]];
      heapify(a, max);
    }
  };
  for (let i = Math.floor(l / 2); i >= 0; i -= 1) heapify(a, i);
  for (let i = a.length - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]];
    l--;
    heapify(a, 0);
  }
  return a;
};

例如：

heapsort([6, 3, 4, 1]); // [1, 3, 4, 6]

总结

恭喜你！你已经完成了堆排序实验。你可以在 LabEx 中练习更多实验来提升你的技能。