系统化梳理Java核心算法体系,200+经典算法图解+实战代码,助你构建扎实的算法思维与工程能力
在Java软件开发的进阶之路上,算法能力是区分初级与高级工程师的关键分水岭。无论是面试中的手撕代码环节,还是实际工程中对性能瓶颈的优化,亦或是对分布式系统、高并发架构的深度理解,都离不开扎实的算法基础。
本 java算法大全图解 站点致力于构建一套完整、直观、可实践的算法学习路径。我们摒弃传统晦涩的数学推导,采用「图解+代码+场景」三位一体的教学模式,让抽象的算法逻辑变得具象、可操作、易迁移。
全站内容覆盖从基础数据结构(数组、链表、栈、队列、哈希表)到高级算法范式(分治、贪心、回溯、动态规划、图搜索),涵盖 LeetCode、Codeforces、牛客网等平台高频考点,并结合真实业务场景(如电商秒杀限流、地图路径规划、推荐系统排序)进行深度拓展。
特别说明:本 java算法大全图解 内容严格遵循 Java 11+ 语法规范,所有示例代码均通过单元测试验证,支持直接复制运行于 IntelliJ IDEA、Eclipse 或 VS Code(Java Extension Pack)环境。我们倡导「理解优于记忆,实践高于空谈」的学习哲学,确保每位读者不仅能看懂,更能写出、用好、调优。
正如《算法导论》作者所言:“算法是程序的灵魂。”而本 java算法大全图解,正是您点亮灵魂的那束光。
任何算法都建立在数据结构之上。选择合适的数据结构,往往能将问题复杂度从指数级降至线性级。本节系统梳理 Java 中最核心的五大数据结构,并标注其在 java算法大全图解 中的完整图解索引。
数组是内存中连续存储的同构元素集合,Java 中的数组是固定长度的引用类型。其核心优势在于 O(1) 时间复杂度的随机访问能力——通过基地址 + 偏移量直接定位元素。
但数组的劣势同样显著:插入/删除需整体移动元素,时间复杂度为 O(n);且长度不可变,扩容需新建数组并复制。
典型应用场景:
【示例】数组遍历与二分查找(java算法大全图解 核心代码):
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 避免 (left + right) 溢出
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
【图解】二分查找过程(以有序数组 [2,5,8,12,16,21,27] 查找 12 为例):
⚠️ 注意:数组必须有序才能使用二分查找——这是初学者高频错误点!
链表通过指针/引用串联节点,每个节点包含数据域与指针域。Java 中 LinkedList 基于双向链表实现,支持 O(1) 头尾插入/删除(已知节点位置时)。
与数组相比,链表牺牲了随机访问性能(O(n)),换取了灵活的动态扩容能力。
【经典题型】LeetCode 19:删除链表倒数第 N 个节点
双指针解法思路:
fast 和 slow,初始均指向头结点fast 先走 n 步fast 为 null,则删除头结点fast 和 slow,直至 fast.next 为 nullslow 指向待删节点的前驱,执行 slow.next = slow.next.next【图解】删除倒数第 2 个节点(链表:1→2→3→4→5):
【易错点】:需处理删除头结点的特殊情况;Java 中无指针,但对象引用等效于指针。
栈(Stack)是受限的线性表,仅允许在表尾(栈顶)进行插入/删除操作,遵循 LIFO(Last In First Out)原则。
Java 中 Stack 类已过时(线程不安全且继承 Vector),推荐使用 Deque 实现栈: Deque<Integer> stack = new ArrayDeque<>();
核心应用:
【示例】括号匹配算法(java算法大全图解 拓展):
public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') stack.push(c);
else if (stack.isEmpty()) return false;
else if (c == ')' && stack.pop() != '(') return false;
else if (c == ']' && stack.pop() != '[') return false;
else if (c == '}' && stack.pop() != '{') return false;
}
return stack.isEmpty();
}
【图解】匹配过程 “{[()]}”:
队列(Queue)是另一受限线性表,仅允许在表尾插入(enqueue)、表头删除(dequeue),遵循 FIFO(First In First Out)原则。
Java 中推荐使用 Queue<E> queue = new LinkedList<>(); 或线程安全的 ConcurrentLinkedQueue。
扩展类型:
典型场景:
【图解】BFS 求二叉树最小深度(LeetCode 111):
哈希表通过哈希函数将键映射到桶(bucket)中,实现 O(1) 平均时间复杂度的增删查改。
Java 中 HashMap 是核心实现,JDK1.8 采用:数组 + 链表 + 红黑树 三者组合结构:
【哈希冲突处理】:
ThreadLocal 的 ThreadLocalMapConcurrentHashMap(JDK1.7)【图解】HashMap 插入过程(以 key="age" → 18 为例):
⚠️ 注意:自定义类作为 key 必须重写 hashCode() 和 equals()——否则哈希表失效!
排序是算法中的基础操作,也是衡量程序员基本功的重要标尺。本节对主流排序算法进行系统对比,并给出 java算法大全图解 中的深度解析。
| 算法 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学演示 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 小规模数据 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 基本有序数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大数据、需稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用首选(平均最快) |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | Top K 问题 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 | 整数且范围小 |
| 桶排序 | O(n+k) | O(n²) | O(n+k) | 稳定 | 均匀分布数据 |
【图解】快速排序分区过程(以 [5,2,8,3,9,1] 为例,基准=5):
【关键优化】:
【业务映射】:Java 8 中 Arrays.sort() 对对象使用 TimSort(归并+插入混合优化),对基本类型使用双轴快速排序(Yaroslavskiy 算法)——性能更优!
查找是数据处理中最频繁的操作。本节从线性查找、二分查找出发,延伸至树形结构与哈希查找,构建完整的查找知识体系。
二分查找要求序列有序,每次将搜索区间减半,时间复杂度 O(log n)。
【变形题型】LeetCode 33:旋转排序数组中的搜索
数组 [4,5,6,7,0,1,2] 是 [0,1,2,4,5,6,7] 旋转 3 位的结果。目标 target=0。
解法:每次判断哪半段有序,再判断 target 是否在该有序段内。
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) { // 左半段有序
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else { // 右半段有序
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
【图解】搜索过程:
二叉搜索树(BST)满足:左子树 < 根 < 右子树,支持动态插入/删除,平均时间复杂度 O(log n)。
【典型问题】LeetCode 98:验证二叉搜索树
错误思路:仅比较 node.left.val < node.val < node.right.val
正确思路:每个节点需满足 下界 < 节点值 < 上界,边界向上传递。
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
【图解】验证树 [5,1,4,null,null,3,6]:
B 树(Balance Tree)是多路搜索树,每个节点可含多个键值,用于磁盘存储优化。
【B+ 树特性】(MySQL InnoDB 索引实现):
【图解】B+ 树插入过程(阶数=4):
【业务映射】:Elasticsearch 的倒排索引底层也采用 B+ 树结构,实现高效全文检索。
树与图是描述复杂关系的核心模型。本节聚焦二叉树遍历、图搜索算法,并给出 java算法大全图解 的可视化解析。
四种遍历方式(前/中/后/层序):
【示例】中序遍历迭代法(Java):
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
【图解】中序遍历过程(树:[1,null,2,3]):
【BFS(广度优先)】:使用队列,逐层扩展,适合求最短路径(无权图)
【DFS(深度优先)】:使用栈(递归),沿路径深入,适合路径存在性、拓扑排序
【经典题】LeetCode 200:岛屿数量
输入:grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]
输出:3(三块独立岛屿)
【DFS 解法】:
int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
grid[i][j] = '0'; // 标记已访问
dfs(grid, i+1, j); dfs(grid, i-1, j);
dfs(grid, i, j+1); dfs(grid, i, j-1);
}
【图解】DFS 覆盖过程:从 (0,0) 开始,将相连的 '1' 全标记为 '0' → 一次 DFS 覆盖第一块岛屿;后续 (2,2)、(3,3) 各触发一次。
【图解】前序 [3,9,20,15,7] + 中序 [9,3,15,20,7] 重建过程:
动态规划(DP)是解决重叠子问题与最优子结构性质问题的高效范式,核心在于状态定义与转移方程。
定义:F(n) = F(n-1) + F(n-2),F(0)=0, F(1)=1
【状态定义】:dp[i] 表示第 i 项的值
【转移方程】:dp[i] = dp[i-1] + dp[i-2]
【初始状态】:dp[0]=0, dp[1]=1
【空间优化】:仅需两个变量滚动更新
public int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
【图解】n=5 时状态转移:
LeetCode 322:给定 coins=[1,2,5],amount=11,求最少硬币数(返回 3:5+5+1)
【状态定义】:dp[i] 表示凑成金额 i 的最少硬币数
【转移方程】:dp[i] = min(dp[i - coin] + 1) for each coin ≤ i
【初始状态】:dp[0]=0,其余初始化为 amount+1(表示不可达)
【图解】amount=6, coins=[1,2,5]:
【易错点】:初始化不可达值需为大数(如 amount+1),否则 min 操作失效。
LeetCode 300:nums=[10,9,2,5,3,7,101,18] → LIS=[2,3,7,18] 或 [2,5,7,101],长度=4
【O(n²) 解法】:
【O(n log n) 解法】(贪心+二分):
【图解】nums=[2,6,3,4,5,1]:
【关键理解】:tails 并非真实 LIS,但其长度等于 LIS 长度——这是 DP 与贪心的精妙结合。
字符串处理是算法中的高频场景,本节涵盖 KMP、Rabin-Karp、Trie 等核心算法。
KMP(Knuth-Morris-Pratt)通过预处理模式串生成 next 数组(部分匹配表),避免主串指针回溯。
【next[i] 定义】:子串 pattern[0..i] 的最长公共前后缀长度
【生成 next】:
【匹配过程】:
【图解】text="abababca", pattern="ababca"
【时间复杂度】:O(m+n),m=text 长度,n=pattern 长度
将字符串视为数字(如 base=26),用哈希值比较替代逐字符比较,支持批量匹配。
【核心公式】:
【步骤】:
【适用场景】:多模式匹配、 plagiarism detection(抄袭检测)
Trie(字典树)是多叉树结构,用于高效存储与检索字符串集合的前缀信息。
【节点结构】:
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd;
}
【插入操作】:逐字符构建路径,末尾节点设 isEnd=true
【搜索操作】:沿路径向下,到末尾节点且 isEnd=true → 存在
【前缀搜索】:沿路径向下,到末尾节点即可(不要求 isEnd)
【图解】插入 ["app", "apple", "apply"]:
【性能】:时间复杂度 O(L),L 为字符串平均长度,与单词数无关
【业务映射】:搜索引擎的自动补全、IDE 的代码提示、IP 路由表查找
图(Graph)由顶点集与边集构成,是描述关系的通用模型。本节涵盖图存储、遍历与核心算法。
【邻接矩阵】:二维数组 graph[u][v] 表示边权,适合稠密图(边多)
【邻接表】:List<List<Edge>>,每个顶点存其邻接点列表,适合稀疏图(边少)
【Java 实现】(稀疏图推荐):
class Graph {
List<List<Edge>> adj = new ArrayList<>();
Graph(int n) { for(int i=0; i<n; i++) adj.add(new ArrayList<>()); }
void addEdge(int u, int v, int w) { adj.get(u).add(new Edge(v, w)); }
}
class Edge { int v, w; Edge(int v, int w) { this.v = v; this.w = w; } }
【空间对比】:
【BFS】:求无权图最短路径(如 LeetCode 102:二叉树层序遍历)
【DFS】:求连通分量、拓扑排序(需记录完成时间)
【关键区别】:
【图解】BFS 求 0→3 最短路径(图:0-1, 0-2, 1-3, 2-3):
【Dijkstra 图解】(以 0 为源点):
【业务映射】:地图导航(高德/百度)、网络路由(OSPF 协议)、社交网络(六度分隔理论)。