前端工程师必备算法与数据结构详解：从排序到动态规划，大厂高频考点全解析

一、排序算法精讲（附LeetCode真题）

1. 快速排序（分治思想）

思想：选取基准值(pivot)将数组分为左右两部分，递归排序子数组。
LeetCode实战：912. 排序数组

const quickSort = (arr) => {
  if (arr.length <= 1) return arr;
  const pivot = arr.pop();
  const left = arr.filter(x => x <= pivot);
  const right = arr.filter(x => x > pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
};

复杂度：平均O(n log n)，最坏O(n²)（可通过三数取中法优化）

2. 归并排序（稳定排序）

应用场景：链表排序、外部排序

const merge = (left, right) => {
  let res = [];
  while (left.length && right.length) {
    res.push(left[0] <= right[0] ? left.shift() : right.shift());
  }
  return res.concat(left, right);
};

const mergeSort = (arr) => {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
};

LeetCode真题：146. 排序链表

---

二、二叉树遍历全解（递归与非递归实现）

1. 前序遍历（根-左-右）

递归实现：

const preorder = (root) => {
  if (!root) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
};

迭代实现（栈+右左入栈）：

const preorderTraversal = (root) => {
  const stack = [root], res = [];
  while (stack.length) {
    const node = stack.pop();
    if (!node) continue;
    res.push(node.val);
    stack.push(node.right); // 右节点先入栈
    stack.push(node.left);
  }
  return res;
};

LeetCode真题：143. 二叉树的前序遍历

2. 中序遍历（左-根-右）

Morris遍历（空间复杂度O(1)）：

const inorderTraversal = (root) => {
  let curr = root, res = [];
  while (curr) {
    if (!curr.left) {
      res.push(curr.val);
      curr = curr.right;
    } else {
      let pre = curr.left;
      while (pre.right && pre.right !== curr) pre = pre.right;
      if (!pre.right) {
        pre.right = curr;
        curr = curr.left;
      } else {
        pre.right = null;
        res.push(curr.val);
        curr = curr.right;
      }
    }
  }
  return res;
};

应用场景：二叉搜索树中序有序

---

三、动态规划核心模型（附大厂真题）

1. 背包问题（0-1背包）

状态方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
空间优化（一维数组逆序更新）：

const knapsack = (weights, values, capacity) => {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let j = capacity; j >= weights[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
};

LeetCode真题：414. 分割等和子集

2. 最长递增子序列（LIS）

贪心+二分优化：

const lengthOfLIS = (nums) => {
  const tails = [];
  for (const num of nums) {
    let l = 0, r = tails.length;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (tails[mid] < num) l = mid + 1;
      else r = mid;
    }
    if (l === tails.length) tails.push(num);
    else tails[l] = num;
  }
  return tails.length;
};

复杂度：O(n log n)

---

四、链表高频操作（大厂必考）

1. 反转链表（迭代/递归）

迭代实现：

const reverseList = (head) => {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};

递归实现：

const reverseList = (head) => {
  if (!head || !head.next) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};

LeetCode真题：205. 反转链表

---

扩展：算法学习路线

1. 基础阶段：掌握数组/链表操作 → 理解栈/队列 → 学习二叉树遍历
2. 进阶阶段：深入动态规划 → 掌握图算法（BFS/DFS） → 研究高级数据结构（Trie/红黑树）
3. 实战训练：按标签刷LeetCode（排序/树/动态规划各50题） → 参加周赛 → 模拟面试

通过系统性学习与实践，结合文中提供的代码模板和真题解析，可快速提升算法思维与编码能力，从容应对大厂面试与技术挑战。