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/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/array_methods("`Array Methods`") subgraph Lab Skills javascript/variables -.-> lab-28496{{"`JavaScript 中的归并排序`"}} javascript/data_types -.-> lab-28496{{"`JavaScript 中的归并排序`"}} javascript/arith_ops -.-> lab-28496{{"`JavaScript 中的归并排序`"}} javascript/comp_ops -.-> lab-28496{{"`JavaScript 中的归并排序`"}} javascript/cond_stmts -.-> lab-28496{{"`JavaScript 中的归并排序`"}} javascript/array_methods -.-> lab-28496{{"`JavaScript 中的归并排序`"}} end

归并排序算法

要使用归并排序算法进行编码练习,请遵循以下步骤:

  1. 打开终端/SSH并输入 node
  2. 使用递归对数字数组进行排序。
  3. 如果数组的 length 小于 2,则返回该数组。
  4. 使用 Math.floor() 计算数组的中间点。
  5. 使用 Array.prototype.slice() 将数组切成两半,并对创建的子数组递归调用 mergeSort()
  6. 最后,使用 Array.from()Array.prototype.shift() 将两个已排序的子数组合并为一个。

以下是代码:

const mergeSort = (arr) => {
  if (arr.length < 2) return arr;
  const mid = Math.floor(arr.length / 2);
  const l = mergeSort(arr.slice(0, mid));
  const r = mergeSort(arr.slice(mid, arr.length));
  return Array.from({ length: l.length + r.length }, () => {
    if (!l.length) return r.shift();
    else if (!r.length) return l.shift();
    else return l[0] > r[0] ? r.shift() : l.shift();
  });
};

用这个例子试试:

mergeSort([5, 1, 4, 2, 3]); // [1, 2, 3, 4, 5]

总结

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

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