算法基础知识体系概览

什么是算法与数据结构？

数据结构（Data Structure） 是计算机中组织和存储数据的方式——数组像一排编了号的储物柜，链表像手拉手排队的人，树像公司的层级组织架构。选择合适的数据结构，能让数据的增删改查效率产生量级差异。

算法（Algorithm） 是解决特定问题的步骤和方法——排序算法决定怎么把乱序数据排好，搜索算法决定怎么在海量数据中找到目标。同一个问题，不同算法的效率可能天差地别。

数据结构和算法是所有计算机程序的基石。无论你用什么编程语言、什么框架，底层都在和数据结构与算法打交道：

React 的 Virtual DOM Diff 是树的比较算法
Vue 的响应式依赖收集用到了 Set 和 Map
浏览器渲染排版用到了布局算法
前端路由匹配用到了字符串匹配 / Trie 树

为什么前端要学算法？

原因	说明
面试硬要求	大厂面试必考手写算法题，通常 1-2 道 LeetCode 难度
代码质量	掌握算法思维能写出更高效、更优雅的代码
框架原理	React Fiber、Vue Diff、虚拟列表等底层依赖各种算法
性能优化	大数据量场景下，算法复杂度直接影响页面流畅度
职业上限	算法能力决定了能解决多复杂的技术问题

核心知识点

复杂度分析——衡量算法好坏的"尺子"

时间复杂度用 大 O 表示法描述算法执行时间随数据量增长的变化趋势：

复杂度	名称	示例	10 万数据耗时量级
$O(1)$	常数	数组随机访问	1 次
$O(\log n)$	对数	二分查找	17 次
$O(n)$	线性	遍历数组	10 万次
$O(n \log n)$	线性对数	快排、归并排序	170 万次
$O(n^2)$	平方	冒泡排序	100 亿次

复杂度的直觉

$O(n)$ 和 $O(n^2)$ 在数据量小（几十个）时差异不大，但当 $n = 100000$ 时， $O(n^2)$ 耗时是 $O(n)$ 的 10 万倍。面试中"优化时间复杂度"通常就是从 $O(n^2)$ 降到 $O(n \log n)$ 或 $O(n)$ 。

基础数据结构

数据结构	特点	前端应用
数组	连续内存、随机访问 $O(1)$ 、插入删除 $O(n)$	列表渲染、状态数组
链表	非连续内存、插入删除 $O(1)$ 、访问 $O(n)$	React Fiber 链表、LRU 缓存
栈	后进先出（LIFO）	浏览器历史记录、撤销/重做、括号匹配
队列	先进先出（FIFO）	任务队列、BFS、消息队列
哈希表	键值对存储、查找 $O(1)$	Map/Set、缓存、去重
树	层级结构、查找 $O(\log n)$	DOM 树、组件树、路由树
图	节点+边、表示关系网络	依赖关系、社交网络、拓扑排序

常见算法思维

双指针：用两个指针从不同方向遍历，常用于排序数组的问题（两数之和、三数之和、接雨水）。

滑动窗口：维护一个动态的"窗口"在数组上滑动，适合连续子序列/子串问题（无重复最长子串、最大子数组和）。

递归与分治：把大问题拆成相同结构的小问题——归并排序、快速排序、二叉树遍历都是经典的分治应用。

动态规划（DP）：把问题分解为重叠子问题，用"表格"记录已计算的结果避免重复计算——爬楼梯、零钱兑换、最长递增子序列。

贪心：每一步选择当前最优解，期望得到全局最优——合并区间、买卖股票。

回溯：穷举所有可能的组合/排列，不满足条件就"回退"——全排列、N 皇后、组合总和。

排序算法

算法	平均时间	最坏时间	空间	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	✅ 稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	❌ 不稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	✅ 稳定
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n)$	✅ 稳定
快速排序	$O(n \log n)$	$O(n^2)$	$O(\log n)$	❌ 不稳定
堆排序	$O(n \log n)$	$O(n \log n)$	$O(1)$	❌ 不稳定

面试重点

快排和归并是面试考得最多的排序算法。快排的核心是分区（Partition）——选一个基准值，比它小的放左边，比它大的放右边，然后递归处理两边。

二分查找

二分查找的前提是有序数组。每次将查找范围缩小一半，时间复杂度 $O(\log n)$ ——在 100 万个元素中找一个数，最多只需 20 次比较。

二分查找的难点不在于"二分"本身，而在于边界条件的处理（left <= right 还是 left < right？返回 left 还是 right？）。掌握标准模板后，可以延伸到"第一个大于 target 的位置"、"搜索旋转数组"等变体。

学习建议

推荐学习路径

复杂度分析 → 学会评估算法好坏
数组 + 链表 + 栈 + 队列 → 线性数据结构
哈希表 + 树 → 非线性数据结构
双指针 + 滑动窗口 → 最易上手的算法思维
排序 + 二分查找 → 经典必考
递归 + 动态规划 + 回溯 → 进阶算法思维

什么是算法与数据结构？​

为什么前端要学算法？​

核心知识点​

复杂度分析——衡量算法好坏的"尺子"​

基础数据结构​

常见算法思维​

排序算法​

二分查找​

学习建议​

相关链接​