LeetCode 算法题解集锦

这是一个算法学习笔记，包含了各种常见的算法题解和实现思路。主要涵盖数组、字符串、链表、树结构和动态规划等经典算法类型。

目录

数组算法

数组是最基础的数据结构之一，这里收集了一些常见的数组操作算法题目。

题目列表

旋转图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
// 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
// 输入：matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
// 输出：[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
function rotate(matrix) {
  const n = matrix.length;

  // 步骤1：沿对角线翻转
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      // 交换matrix[i][j]和matrix[j][i]
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }

  // 步骤2：左右翻转
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n / 2; j++) {
      // 交换matrix[i][j]和matrix[i][n-1-j]
      [matrix[i][j], matrix[i][n - 1 - j]] = [
        matrix[i][n - 1 - j],
        matrix[i][j],
      ];
    }
  }

  return matrix;
}

console.log(
  rotate([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
  ])
);

寻找最大值

1
2
3
4
5
6
7
8
9
10
11
12
// 给定一个数组，返回数组中的最大值
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

console.log(findMax([1, 3, 5, 7, 9])); // 输出：9

反转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
// 给定一个数组，反转数组中的元素
function reverseArray(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}

console.log(reverseArray([1, 2, 3, 4, 5])); // 输出：[5, 4, 3, 2, 1]

两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 给定一个整数数组 nums 和一个目标值 target，返回数组中和为目标值的两个数的索引。
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

console.log(twoSum([2, 7, 11, 15], 9)); // 输出：[0, 1]

检查数组是否包含重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  if (nums.length === 1) {
    return false;
  }
  let dp = new Set();
  for (let num of nums) {
    if (dp.has(num)) {
      return true;
    }
    dp.add(num);
  }
  return false;
};

console.log(containsDuplicate([0, 4, 5, 0, 3, 6])); // 输出：true

移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
// 请注意 ，必须在不复制数组的情况下原地对数组进行操作。

function moveZeroes(nums) {
  // 用冒泡的方法
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === 0 && nums[j] !== 0) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
      }
    }
  }
  return nums;
}

// 添加的代码：调用函数并输出结果
console.log(moveZeroes([0, 1, 0, 3, 12])); // 输出：[1, 3, 12, 0, 0]

寻找旋转排序数组中的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 给定一个经过旋转的升序数组，找出其中的最小值。使用二分查找可以实现O(log n)的时间复杂度。
/**
 * @param {number[]} nums
 * @return {number}
 */

// 关键在于理解 最小值的右侧有序这个点
var findMin = function (nums) {
    let left = 0
    let right = nums.length - 1
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2)
        // 左边有序
        if (nums[mid] > nums[right]) {
            left = mid + 1
            // 右边有序
        } else {
            right = mid
        }
    }
    return nums[left];
};

// 示例
console.log(findMin([3, 4, 5, 1, 2])) // 输出: 1

字符串算法

字符串操作是编程中最常见的任务之一，掌握字符串算法对提高编程能力很有帮助。

题目列表

反转字符串

1
2
3
4
5
6
// 给定一个字符串，反转字符串中的字符
function reverseString(str) {
  return str.split("").reverse().join("");
}

console.log(reverseString("hello")); // 输出："olleh"

判断回文

1
2
3
4
5
6
7
// 给定一个字符串，判断其是否为回文
function isPalindrome(str) {
  const cleanedStr = str.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();
  return cleanedStr === cleanedStr.split("").reverse().join("");
}

console.log(isPalindrome("A man, a plan, a canal: Panama")); // 输出：true

字符串包含

1
2
3
4
5
6
// 判断字符串 s 是否包含字符串 t
function contains(s, t) {
  return s.includes(t);
}

console.log(contains("hello world", "world")); // 输出：true

链表算法

链表是一种重要的线性数据结构，它的特点是动态性强，插入和删除操作高效。

题目列表

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prev = null;
  while (head) {
    // 首先获得下一个节点
    let next = head.next;
    // 然后将当前节点指向前一个节点
    head.next = prev;
    // 前一个节点指向当前节点
    prev = head;
    // 当前节点指向下一个节点
    head = next;
  }
  return prev; // 返回���点
};

console.log(
  reverseList({
    val: 1,
    next: {
      val: 2,
      next: { val: 3, next: { val: 4, next: { val: 5, next: null } } },
    },
  })
); // 输出：反转后的链表

合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 合并两个有序链表并返回合并后的新链表
function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let current = dummy;

  while (l1 && l2) {
    if (l1.val < l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }

  current.next = l1 || l2; // 连接剩余部分
  return dummy.next; // 返回合并后的链表头
}

删除链表的倒数第 N 个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 删除链表的倒数第N个节点
// 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let left = head;
  let right = head;
  for (let i = 0; i < n; i++) {
    right = right.next;
  }
  if (!right) return head.next; // 如果要删除的是头节点
  while (right.next) {
    left = left.next;
    right = right.next;
  }
  left.next = left.next.next; // 删除倒数第n个节点
  return head;
};

// 添加的代码：调用函数并输出结果
console.log(
  removeNthFromEnd(
    {
      val: 1,
      next: {
        val: 2,
        next: {
          val: 3,
          next: {
            val: 4,
            next: {
              val: 5,
              next: null,
            },
          },
        },
      },
    },
    2
  )
); // 输出：{ val: 1, next: { val: 2, next: { val: 3, next: { val: 5, next: null } } } }

树结构算法

树是一种非线性数据结构，在解决层次关系问题时非常有用。

题目列表

二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 给定一个二叉树，返回其节点值的前序遍历
function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

function preorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (!node) return;
    result.push(node.val); // 访问根节点
    traverse(node.left); // 遍历左子树
    traverse(node.right); // 遍历右子树
  }
  traverse(root);
  return result;
}

// 示例用法
const root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);
console.log(preorderTraversal(root)); // 输出：[1, 2, 3]

二叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 给定一个二叉树，返回其节点值的层序遍历
function levelOrder(root) {
  const result = [];
  if (!root) return result;

  const queue = [root];
  while (queue.length) {
    const level = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

动态规划

动态规划是解决复杂问题的有效方法，通过将大问题分解为小问题来求解。

爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 假设你正在爬楼梯。需要 n 阶台阶，你可以一次爬 1 阶或 2 阶。计算有多少种不同的方法可以爬到顶部。
function climbStairs(n) {
  if (n <= 2) return n; // 基础情况
  let first = 1,
    second = 2;
  for (let i = 3; i <= n; i++) {
    const temp = first + second; // 当前阶梯的方法数
    first = second; // 更新第一步
    second = temp; // 更新第二步
  }
  return second; // 返回到达第 n 阶的方法数
}

console.log(climbStairs(5)); // 输出：8

最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 给定两个字符串，返回它们的最长公共子序列的长度
function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = Array(m + 1)
    .fill(0)
    .map(() => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

console.log(longestCommonSubsequence("abcde", "ace")); // 输出：3

买卖股票的最佳时机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票 i 天的价格。
// 你只能选择 某一天 买入这只股票，并选择 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
// 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  // 创建二维动态规划数组
  // dp[i][0]：第i天不持有股票的最大利润
  // dp[i][1]：第i天持有股票的最大利润
  let dp = new Array(prices.length).fill().map(() => new Array(2).fill(0));

  // 初始状态：第0天的情况
  // 不持有股票的利润为0
  dp[0][0] = 0;
  // 持有股票的利润为负的第0天股价（买入股票）
  dp[0][1] = -prices[0];

  // 动态规划状态转移
  for (let i = 1; i < prices.length; i++) {
    // 不持有股票的最大利润：
    // 1. 保持昨天不持有的状态
    // 2. 昨天持有股票，今天卖出
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

    // 持有股票的最大利润：
    // 1. 保持昨天持有股票的状态
    // 2. 昨天不持有股票，今天买入
    dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
  }

  // 返回最后一天不持有股票的最大利润
  return dp[prices.length - 1][0];
};

// 添加的代码：调用函数并输出结果
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 输出：5

最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 最大子序和
// 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 子数组 是数组中的一个连续部分。
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  // 1. 创建动态规划数组
  // dp[i]：以nums[i]结尾的最大子数组和
  let dp = new Array(nums.length).fill(0);

  // 2. 初始状态：第一个元素
  dp[0] = nums[0];

  // 3. 记录全局最大和
  let max = nums[0];

  // 4. 动态规划状态转移
  for (let i = 1; i < nums.length; i++) {
    // 关键状态转移方程：
    // 要么从当前元素重新开始，要么延之前的子数组
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);

    // 更新全局最大和
    max = Math.max(max, dp[i]);
  }

  // 5. 返回最大子数组和
  return max;
};

// 添加的代码：调用函数并输出结果
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 输出：6

背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function knapspacking(weights, values, capacity) {
  let n = weights.length;
  // 初始化 dp 数组
  // 第一层是物品，也就是第一个物品，第二个物品
  // 第二层是物品的重量，重量是0 ，也就是不放，次递加，直达到量上限
  let dp = Array(n + 1)
    .fill()
    .map(() => Array(capacity + 1).fill(0));

  // 遍历所有物品
  for (let i = 1; i <= n; i++) {
    // 遍历每种可能的容量
    for (let w = 0; w <= capacity; w++) {
      // 注意这里是 <= capacity
      // 不选择当前物品
      dp[i][w] = dp[i - 1][w];
      // 如果当前物品可以放入背包，尝试选择它
      if (w >= weights[i - 1]) {
        // 不放物品的价值和前一个物品的最佳价值加上本物品的价值 就是当前的最佳价值
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      }
    }
  }

  // 返回最大价值
  return dp[n][capacity];
}

// 添加的代码：调用函数并输出结果
console.log(knapspacking([1, 6, 10], [1, 2, 3], 10)); // 输出：3

验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 验证二叉搜索树
// 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树.
// 有效 二叉搜索树定义如下：
// 节点的左子树只包含 小于 当前节点的数。
// 节点的右子树只包含 大于 当前节点的数。
// 所有左子树和右子树自身必须也是二叉搜索树.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  if (!root) return true;
  if (root.val === null) return true;
  const dfs = (node, min, max) => {
    if (!node) return true;
    if (min != null && node.val <= min) return false;
    if (max != null && node.val >= max) return false;
    return dfs(node.left, min, node.val) && dfs(node.right, node.val, max);
  };
  return dfs(root, null, null);
};

// 添加的代码：调用函数并输出结果
console.log(
  isValidBST({
    val: 5,
    left: { val: 4, left: 3, right: null },
    right: { val: 6, left: 3, right: 7 },
  })
); // 输出：false

给你一个二叉树的根节点 root ， 检查它是否轴对称。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 定义深度优先搜索辅助函数
const dfs = (left, right) => {
  // 如果左右子树有一个为空，则检查它们是否同时为空
  if (left == null || right == null) return left == right;

  // 如果左右子树的值不相等，返回false
  if (left.val != right.val) return false;

  // 递归比较：
  // 1. 左子树的左子节点 与 右子树的右子节点比较
  // 2. 左子树的右子节点 与 右子树的左子节点比较
  return dfs(left.left, right.right) && dfs(left.right, right.left);
};

// 从根节点的左右子树开始比较
console.log(
  dfs(
    {
      val: 1,
      left: { val: 2, left: 3, right: null },
      right: { val: 2, left: null, right: 3 },
    },
    {
      val: 1,
      left: { val: 2, left: 3, right: null },
      right: { val: 2, left: null, right: 3 },
    }
  )
); // 输出：true

有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 有效的括号
// 给你一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断���符串是否有效。
// 有效字符串需满足：
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 每个右括号都有一个对应的相同类型的左括号。

// 示例 1：
// 输入：s = "()"
// 输出：true

// 示例 2：
// 输入：s = "()[]{}"
// 输出：true

// 示例 3：
// 输入：s = "(]"
// 输出：false

// 示例 4：
// 输入：s = "([])"
// 输出：true

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let queue = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(" || s[i] === "[" || s[i] === "{") {
      queue.push(s[i]);
    } else {
      let last = queue.pop();
      if (
        (last === "(" && s[i] === ")") ||
        (last === "[" && s[i] === "]") ||
        (last === "{" && s[i] === "}")
      ) {
        continue;
      } else {
        return false;
      }
    }
  }
  return queue.length === 0;
};

// 添加的代码：调用函数并输出结果
console.log(isValid("()[]{}")); // 输出：true

打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 打家劫舍
// 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗���统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
// 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额.

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  if (nums.length === 1) {
    return nums[0];
  }
  let dp = new Array(nums.length).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    // 这次偷或者不偷，是比较前一次偷了，和前两次偷了哪个更大
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[nums.length - 1];
};

// 添加的代码：调用函数并输出结果
console.log(rob([1, 2, 3, 1])); // 输出：4

将有序数组转换为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 将有序数组转换为二叉搜索树
// 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
  // 辅助函数，递归构建平衡二叉搜索树
  const buildBST = (left, right) => {
    // 递归终止条件
    if (left > right) return null;

    // 选择中间位置作为根节点
    const mid = Math.floor((left + right) / 2);

    // 创建根节点
    const root = new TreeNode(nums[mid]);

    // 递归构建左右子树
    root.left = buildBST(left, mid - 1);
    root.right = buildBST(mid + 1, right);

    return root;
  };

  // 定义树节点
  function TreeNode(val, left, right) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
  // 从整个数组开始构建
  return buildBST(0, nums.length - 1);
};

// 添加的代码：调用函数并输出结果
console.log(sortedArrayToBST([-10, -3, 0, 5, 9])); // 输出：构建的平衡二叉搜索树的根节点

洗牌算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 创建一个对象，包含原始数组和洗牌方法
const ShuffleArray = function (nums) {
  this.original = nums; // 保存原始数组
};

// 洗牌方法
ShuffleArray.prototype.shuffle = function () {
  // 创建副本，避免修改原数组
  let nums = this.original.slice();

  // Fisher-Yates洗牌算法
  for (let i = nums.length - 1; i > 0; i--) {
    // 从0到i随机选择一个索引
    const j = Math.floor(Math.random() * (i + 1));

    // 交换
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  return nums;
};
const shuffleArray = new ShuffleArray([1, 2, 3, 4, 5]);
console.log(shuffleArray.shuffle()); // 输出：随机顺序的数组

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const mergeSort = function (arr) {
  if(arr.length <= 1) {
    return arr;
  }
  let mid = Math.floor(arr.length/2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

const merge = function(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  while(leftIndex < left.length && rightIndex < right.length) {
    if(left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  // 添加剩余元素
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

快速排序

const quickSort = function(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

const partition = function(arr, left, right) {
  const pivot = arr[right]; // 选择最右边的元素作为基准
  let i = left - 1; // 小于pivot的元素的边界

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换元素
    }
  }
  
  // 将pivot放到正确的位置
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
}