在JavaScript中实现堆排序算法

JavaScriptJavaScriptBeginner
立即练习

This tutorial is from open-source community. Access the source code

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

简介

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


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL javascript(("`JavaScript`")) -.-> javascript/BasicConceptsGroup(["`Basic Concepts`"]) javascript(("`JavaScript`")) -.-> javascript/AdvancedConceptsGroup(["`Advanced Concepts`"]) javascript/BasicConceptsGroup -.-> javascript/variables("`Variables`") javascript/BasicConceptsGroup -.-> javascript/data_types("`Data Types`") javascript/BasicConceptsGroup -.-> javascript/arith_ops("`Arithmetic Operators`") javascript/BasicConceptsGroup -.-> javascript/comp_ops("`Comparison Operators`") javascript/BasicConceptsGroup -.-> javascript/cond_stmts("`Conditional Statements`") javascript/BasicConceptsGroup -.-> javascript/loops("`Loops`") javascript/BasicConceptsGroup -.-> javascript/array_methods("`Array Methods`") javascript/AdvancedConceptsGroup -.-> javascript/spread_rest("`Spread and Rest Operators`") subgraph Lab Skills javascript/variables -.-> lab-28374{{"`在JavaScript中实现堆排序算法`"}} javascript/data_types -.-> lab-28374{{"`在JavaScript中实现堆排序算法`"}} javascript/arith_ops -.-> lab-28374{{"`在JavaScript中实现堆排序算法`"}} javascript/comp_ops -.-> lab-28374{{"`在JavaScript中实现堆排序算法`"}} javascript/cond_stmts -.-> lab-28374{{"`在JavaScript中实现堆排序算法`"}} javascript/loops -.-> lab-28374{{"`在JavaScript中实现堆排序算法`"}} javascript/array_methods -.-> lab-28374{{"`在JavaScript中实现堆排序算法`"}} javascript/spread_rest -.-> lab-28374{{"`在JavaScript中实现堆排序算法`"}} end

堆排序算法

要进行编码练习,请打开终端/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中练习更多实验来提升你的技能。

您可能感兴趣的其他 JavaScript 教程