引言

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

简介

排序算法总结

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等，本文只讲解内部排序算法。用一张表格概括：

这份 算法专题 不是按教材顺序堆知识点，而是按面试刷题的真实路径整理：先搞清复杂度，再掌握二分、双指针、滑动窗口、DFS/BFS、回溯、动态规划、贪心、Top K 这些高频模板，最后用字符串、链表、排序和 LeetCode 题单做复盘。

算法题准备到后面，很容易陷入一个状态：题刷了不少，但换个条件就卡住。原因通常不是题量不够，而是没有把题目归到模板里。面试时真正有用的是：看到题目后能判断它像哪类问题，先写出可工作的版本，再解释复杂度和边界处理。

适合谁看

• 正在准备校招、社招算法题，希望按题型系统刷 LeetCode 的同学。
• 已经刷过一些题，但复盘时说不清“这题为什么这么做”的读者。
• 数据结构基础还可以，但缺少算法模板和边界处理经验的后端开发者。
• 面试前只有 7 到 30 天，需要快速找回手感的工程师。

回溯题的特点很明显：题目让你找所有方案、所有路径、所有组合，或者在一堆选择里试探。它和 DFS 很像，区别在于回溯更强调“选择 -> 递归 -> 撤销选择”。

面试里写回溯，最重要的是先说清递归函数的含义。函数含义稳了，参数、结束条件和撤销选择就不容易乱。

面试考察重点

• 能写组合、排列、子集三类模板。
• 能解释 path、startIndex、used 的作用。
• 能根据题目判断是否需要去重。
• 能做简单剪枝，避免无效搜索。
• 能说清复杂度和结果规模有关。

二分查找最容易让人翻车的地方不是思想，而是边界。left、right、mid、循环条件、返回值，只要有一个含义没想清楚，就很容易写出死循环或者漏掉答案。

面试里判断能不能用二分，先看一句话：答案所在空间是否有单调性。数组有序只是最直观的一种情况，最小速度、最小容量、最小天数这类题，也可以在答案范围上二分。

面试考察重点

• 能写出基础二分模板。
• 能处理左边界、右边界。
• 能识别答案二分，而不是只会在数组里找数。
• 能解释为什么循环会结束，为什么不会漏答案。
• 能说出时间复杂度是 O(logn)，空间复杂度通常是 O(1)。

算法思想不要孤立背。面试里更有用的问法是：什么信号提示我该用它？模板里最容易错的地方在哪里？如果面试官改条件，我应该从哪个变量或状态开始调整？

这份题单按思想组织，每一类都给出“识别信号、常用模板、代表题、复盘重点”。题目数量控制在能代表模板的范围内，先把这些题讲明白，比机械刷更多题更划算。

怎么用这份题单

不要一上来就把所有题目按顺序刷完。更适合面试准备的方式是：先读对应的模板文章，确认自己能手写核心代码，再做“必刷题”，最后用“进阶题”检查边界和变体。

目标	建议动作
快速建立模板	先读 二分查找、双指针与滑动窗口、DFS/BFS 这些高频模板文章
补齐搜索和 DP	继续读 回溯算法、动态规划，每类至少手写 2 道基础题
面试前查漏补缺	用 贪心算法、Top K 问题、并查集 补齐常见变体
复盘自己的答案	每题写下题型识别信号、核心变量含义、复杂度、边界样例。如果这些讲不清，说明这题还没真正掌握

刷数据结构题，不建议只按难度从 Easy 刷到 Hard。更稳的方式是按结构建立题型：数组看下标和区间，链表看指针，栈队列看顺序约束，树图看遍历，堆看优先级，哈希表看快速定位。

下面的题单控制在面试高频和模板代表题范围内。每类先做“必刷题”，再做“进阶题”。题目做完后，至少写下复杂度、边界样例和这题属于哪个模板。

怎么用这份题单

数据结构题不要只记结论。每刷一类题，先回到对应结构看一次“存储方式、核心操作、复杂度”，再动手写题。这样面试官追问 Java 集合、Redis、MySQL 索引或缓存场景时，答案不会只停在题解层面。

结构	先读什么	刷题时重点看什么
数组、链表、栈队列	线性数据结构详解、双指针与滑动窗口	下标、指针更新、入栈出栈时机
哈希表	哈希表面试题总结	key 的设计、计数时机、冲突和扩容
树和图	树结构详解、图详解、DFS 与 BFS	递归返回值、访问标记、BFS 层数统计
堆和 Top K	堆详解、Top K 问题面试题总结	堆大小、比较器、数据流场景
Trie 和并查集	Trie 前缀树面试题总结、并查集面试题总结	节点结构、结束标记、路径压缩、连通判断
LRU	LRU 缓存面试题总结	哈希表和双向链表如何保持 O(1)

复杂度分析是算法面试的第一道门。面试官不一定要求你把证明写得很严，但会希望你能说清：这段代码跑了多少轮、额外用了多少空间、输入规模变大后会发生什么。

先把一个边界讲清楚：复杂度分析通常看输入规模趋近很大时的增长趋势，不是精确运行时间。O(n) 不代表一定比 O(nlogn) 快，常数、数据规模、缓存命中和实现细节都会影响真实耗时。不过面试里先按 Big O 说清增长量级，再补一句实际场景的限制，就够用了。

面试考察重点

• 能根据循环、递归、数据结构操作判断时间复杂度。
• 能区分额外空间和输入本身占用的空间。
• 能说清最好、最坏、平均复杂度分别适合哪些算法。
• 遇到递归代码时，能用递归树或子问题规模分析。
• 不把 HashMap、排序、堆操作都默认当成 O(1)。

DFS 和 BFS 是树、图、矩阵题的基础。面试里不会只问“DFS 是什么”，更常见的是给你一个岛屿、课程依赖、最短步数或二叉树层序遍历，让你选搜索方式并写出边界处理。

一个简单判断：需要一路走到底、枚举路径或处理连通块时，优先想 DFS；需要按层推进、求最短步数时，优先想 BFS。

面试考察重点

• 能写递归 DFS、队列 BFS。
• 能说出树和图搜索的复杂度。
• 能处理 visited，避免重复访问和死循环。
• 能区分“遍历所有节点”和“求最短步数”。
• 能把矩阵题转换成图搜索。

动态规划难，不是因为代码一定长，而是因为状态定义一旦错了，后面的转移方程、初始化和遍历顺序都会跟着错。

面试里不要一上来就背模板。先问自己两个问题：这个问题能不能拆成子问题？当前答案是否依赖前面已经算过的答案？如果这两个问题都成立，再考虑 DP。

面试考察重点

• 能说清 dp[i] 或 dp[i][j] 的含义。
• 能写出状态转移方程。
• 能处理初始化和遍历顺序。
• 能判断是否可以压缩空间。
• 能区分背包、子序列、区间等常见类型。

贪心算法的代码往往不长，难点在于为什么当前选择不会影响全局最优。面试里如果只写代码，不解释贪心策略，很容易被追问到卡住。

可以先记一个判断方式：如果问题可以通过排序或维护一个当前最优边界，每一步做出局部选择，并且这个选择不会破坏后续最优解，就可以尝试贪心。

面试考察重点

• 能找出贪心策略。
• 能用交换、反证或直觉边界说明策略合理。
• 能处理排序后的遍历条件。
• 能区分贪心和动态规划。

贪心题怎么想？

贪心题最怕“凭感觉选”。写代码前至少要说清两个东西：