java算法大全图解

系统化梳理Java核心算法体系,200+经典算法图解+实战代码,助你构建扎实的算法思维与工程能力

⚡ java算法大全图解|体系化入门指南

在Java软件开发的进阶之路上,算法能力是区分初级与高级工程师的关键分水岭。无论是面试中的手撕代码环节,还是实际工程中对性能瓶颈的优化,亦或是对分布式系统、高并发架构的深度理解,都离不开扎实的算法基础。

本 java算法大全图解 站点致力于构建一套完整、直观、可实践的算法学习路径。我们摒弃传统晦涩的数学推导,采用「图解+代码+场景」三位一体的教学模式,让抽象的算法逻辑变得具象、可操作、易迁移。

全站内容覆盖从基础数据结构(数组、链表、栈、队列、哈希表)到高级算法范式(分治、贪心、回溯、动态规划、图搜索),涵盖 LeetCode、Codeforces、牛客网等平台高频考点,并结合真实业务场景(如电商秒杀限流、地图路径规划、推荐系统排序)进行深度拓展。

特别说明:本 java算法大全图解 内容严格遵循 Java 11+ 语法规范,所有示例代码均通过单元测试验证,支持直接复制运行于 IntelliJ IDEA、Eclipse 或 VS Code(Java Extension Pack)环境。我们倡导「理解优于记忆,实践高于空谈」的学习哲学,确保每位读者不仅能看懂,更能写出、用好、调优。

正如《算法导论》作者所言:“算法是程序的灵魂。”而本 java算法大全图解,正是您点亮灵魂的那束光。

〔为何选择本 java算法大全图解?〕

  • ✅ 结构清晰:按“数据结构→基础算法→高级算法→工程应用”四层递进,符合认知规律
  • ✅ 图解直观:每类算法配套手绘风格流程图、状态转移图、内存布局图,告别“文字迷宫”
  • ✅ 代码可运行:所有 Java 代码均为可执行类(含 main 方法),附带输入输出示例
  • ✅ 深度拓展:不仅讲“怎么做”,更剖析“为何这么做”——时间复杂度下界证明、空间换时间权衡、缓存友好性优化
  • ✅ 真实场景:每章节末设“业务映射”模块,展示算法在 Spring Boot、Netty、Redis、Elasticsearch 中的实际应用

⚙️ 核心数据结构|算法的地基

任何算法都建立在数据结构之上。选择合适的数据结构,往往能将问题复杂度从指数级降至线性级。本节系统梳理 Java 中最核心的五大数据结构,并标注其在 java算法大全图解 中的完整图解索引。

数组
链表
栈
队列
哈希

〔数组 Array|顺序存储的基石〕

数组是内存中连续存储的同构元素集合,Java 中的数组是固定长度的引用类型。其核心优势在于 O(1) 时间复杂度的随机访问能力——通过基地址 + 偏移量直接定位元素。

但数组的劣势同样显著:插入/删除需整体移动元素,时间复杂度为 O(n);且长度不可变,扩容需新建数组并复制。

典型应用场景:

  • 哈希表底层(Java HashMap 在 JDK1.8 后链表转红黑树前使用数组+链表结构)
  • 快速排序、归并排序中的分区操作
  • 滑动窗口算法(如 LeetCode 3:无重复字符的最长子串)
  • 二维数组实现矩阵运算(图像处理、图的邻接矩阵表示)

【示例】数组遍历与二分查找(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 为例):

  1. 初始:left=0, right=6 → mid=3 → arr[3]=12 = target → 返回索引 3
  2. 若查找 16:第一轮 mid=3(值12 <16)→ left=4;第二轮 mid=5(值21 >16)→ right=4;第三轮 mid=4(值16=16)→ 成功

⚠️ 注意:数组必须有序才能使用二分查找——这是初学者高频错误点!

〔链表 Linked List|动态扩展的线性结构〕

链表通过指针/引用串联节点,每个节点包含数据域与指针域。Java 中 LinkedList 基于双向链表实现,支持 O(1) 头尾插入/删除(已知节点位置时)。

与数组相比,链表牺牲了随机访问性能(O(n)),换取了灵活的动态扩容能力。

【经典题型】LeetCode 19:删除链表倒数第 N 个节点

双指针解法思路:

  1. 定义快慢指针 fast 和 slow,初始均指向头结点
  2. fast 先走 n 步
  3. 若 fast 为 null,则删除头结点
  4. 否则同时移动 fast 和 slow,直至 fast.next 为 null
  5. 此时 slow 指向待删节点的前驱,执行 slow.next = slow.next.next

【图解】删除倒数第 2 个节点(链表:1→2→3→4→5):

  • 初始:fast=1, slow=1
  • fast 先走 2 步 → fast=3
  • 同步移动:fast=4, slow=2;fast=5, slow=3;fast=null, slow=4
  • 删除 slow.next(即节点5),结果:1→2→3→4

【易错点】:需处理删除头结点的特殊情况;Java 中无指针,但对象引用等效于指针。

〔栈 Stack|后进先出的结构〕

栈(Stack)是受限的线性表,仅允许在表尾(栈顶)进行插入/删除操作,遵循 LIFO(Last In First Out)原则。

Java 中 Stack 类已过时(线程不安全且继承 Vector),推荐使用 Deque 实现栈: Deque<Integer> stack = new ArrayDeque<>();

核心应用:

  • 函数调用栈(JVM 栈帧管理)
  • 表达式求值(中缀→后缀→计算)
  • 括号匹配(LeetCode 20:有效的括号)
  • 浏览器前进/后退(双栈实现)
  • DFS 算法的显式栈实现

【示例】括号匹配算法(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();
}

【图解】匹配过程 “{[()]}”:

  1. { 入栈 → {[
  2. ( 入栈 → {[(
  3. ) 匹配 ( → 弹出 (
  4. ] 匹配 [ → 弹出 [
  5. } 匹配 { → 弹出 {
  6. 栈空 → 匹配成功

〔队列 Queue|先进先出的流水线〕

队列(Queue)是另一受限线性表,仅允许在表尾插入(enqueue)、表头删除(dequeue),遵循 FIFO(First In First Out)原则。

Java 中推荐使用 Queue<E> queue = new LinkedList<>(); 或线程安全的 ConcurrentLinkedQueue。

扩展类型:

  • 双端队列(Deque):支持头尾插入/删除
  • 优先队列(PriorityQueue):基于堆实现,自动排序
  • 阻塞队列(BlockingQueue):用于生产者-消费者模型

典型场景:

  • BFS(广度优先搜索)的核心数据结构
  • 任务调度系统(如线程池工作队列)
  • 缓存淘汰策略(如 LRU 的辅助结构)
  • 消息队列中间件(Kafka/RabbitMQ 的底层逻辑)

【图解】BFS 求二叉树最小深度(LeetCode 111):

  1. 根节点入队,depth=1
  2. 循环:出队当前层所有节点,若存在叶子节点则返回 depth;否则将其非空子节点入队,depth++
  3. 示例树:[3,9,20,null,null,15,7]
  4. 第一层:3 → depth=1;第二层:9,20 → depth=2;9 是叶子 → 返回 2

〔哈希表 Hash Table|键值映射的利器〕

哈希表通过哈希函数将键映射到桶(bucket)中,实现 O(1) 平均时间复杂度的增删查改。

Java 中 HashMap 是核心实现,JDK1.8 采用:数组 + 链表 + 红黑树 三者组合结构:

  • 默认负载因子 0.75:空间与时间的平衡点
  • 链表长度 ≥ 8 且数组长度 ≥ 64 → 转红黑树
  • 红黑树节点 ≤ 6 → 转回链表

【哈希冲突处理】:

  • 拉链法(链地址法):HashMap 采用
  • 开放地址法:如 ThreadLocal 的 ThreadLocalMap
  • 再哈希法:如 ConcurrentHashMap(JDK1.7)

【图解】HashMap 插入过程(以 key="age" → 18 为例):

  1. 计算 hash("age") → 假设为 0x3A7B
  2. 索引 = (n-1) & hash → 假设 n=16 → 索引=11
  3. 若索引11处为空 → 直接插入
  4. 若已有节点(如 key="age" → 20)→ 判断 key 是否相等
  5. 相等则覆盖;不等则尾插链表(JDK1.8 后避免死循环)

⚠️ 注意:自定义类作为 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):

  1. 初始:i=-1, j=0
  2. j=0: 2<5 → i=0, swap(arr[0],arr[0]) → [5,2,8,3,9,1]
  3. j=1: 2<5 → i=1, swap(arr[1],arr[1]) → [5,2,8,3,9,1]
  4. j=2: 8>5 → 跳过
  5. j=3: 3<5 → i=2, swap(arr[2],arr[3]) → [5,2,3,8,9,1]
  6. j=4: 9>5 → 跳过
  7. j=5: 1<5 → i=3, swap(arr[3],arr[5]) → [5,2,3,1,9,8]
  8. 最终:swap(arr[0],arr[i+1=4]) → [1,2,3,5,9,8]
  9. 基准 5 归位,左子数组 [1,2,3],右子数组 [9,8]

【关键优化】:

【业务映射】:Java 8 中 Arrays.sort() 对对象使用 TimSort(归并+插入混合优化),对基本类型使用双轴快速排序(Yaroslavskiy 算法)——性能更优!

〔树与图|非线性结构的王者〕

树与图是描述复杂关系的核心模型。本节聚焦二叉树遍历、图搜索算法,并给出 java算法大全图解 的可视化解析。

遍历
BFS/DFS
算法

〔二叉树遍历|递归与迭代〕

四种遍历方式(前/中/后/层序):

【示例】中序遍历迭代法(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]):

  1. curr=1 → 入栈 1 → curr=1.left=null
  2. 弹出 1 → 访问 1 → curr=1.right=2
  3. curr=2 → 入栈 2 → curr=2.left=3
  4. curr=3 → 入栈 3 → curr=3.left=null
  5. 弹出 3 → 访问 3 → curr=3.right=null
  6. 弹出 2 → 访问 2 → curr=2.right=null
  7. 结果:[1,3,2]

〔BFS vs DFS|搜索策略对比〕

【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] 重建过程:

  1. 前序首元素 3 为根 → 中序中 3 左侧 [9] 为左子树,右侧 [15,20,7] 为右子树
  2. 左子树:前序 [9],中序 [9] → 单节点
  3. 右子树:前序 [20,15,7],中序 [15,20,7] → 根 20,左 [15],右 [7]
  4. 结果:3 的左孩子 9,右孩子 20;20 的左 15,右 7

〔动态规划|最优子结构的艺术〕

动态规划(DP)是解决重叠子问题与最优子结构性质问题的高效范式,核心在于状态定义与转移方程。

斐波那契
零钱兑换
子序列

〔斐波那契数列|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 操作失效。

〔最长递增子序列 LIS|经典子序列问题〕

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]:

  1. num=2 → tails=[2]
  2. num=6 → tails=[2,6]
  3. num=3 → 替换 6 → tails=[2,3]
  4. num=4 → tails=[2,3,4]
  5. num=5 → tails=[2,3,4,5]
  6. num=1 → 替换 2 → tails=[1,3,4,5]
  7. 结果长度=4

【关键理解】:tails 并非真实 LIS,但其长度等于 LIS 长度——这是 DP 与贪心的精妙结合。

〔字符串算法|模式匹配的艺术〕

字符串处理是算法中的高频场景,本节涵盖 KMP、Rabin-Karp、Trie 等核心算法。

KMP
Rabin-Karp
Trie

〔KMP 算法|无回溯匹配〕

KMP(Knuth-Morris-Pratt)通过预处理模式串生成 next 数组(部分匹配表),避免主串指针回溯。

【next[i] 定义】:子串 pattern[0..i] 的最长公共前后缀长度

【生成 next】:

【匹配过程】:

【图解】text="abababca", pattern="ababca"

【时间复杂度】:O(m+n),m=text 长度,n=pattern 长度

〔Rabin-Karp 算法|哈希滚动匹配〕

将字符串视为数字(如 base=26),用哈希值比较替代逐字符比较,支持批量匹配。

【核心公式】:

【步骤】:

  1. 计算 pattern 的哈希值 hashP
  2. 计算 text 前 n 个字符的哈希值 hashT
  3. 滑动窗口:若 hashT == hashP → 二次验证字符匹配(防哈希冲突)
  4. 更新 hashT(滚动哈希)

【适用场景】:多模式匹配、 plagiarism detection(抄袭检测)

〔Trie 树|前缀树|高效前缀检索〕

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 vs DFS〕

【BFS】:求无权图最短路径(如 LeetCode 102:二叉树层序遍历)

【DFS】:求连通分量、拓扑排序(需记录完成时间)

【关键区别】:

【图解】BFS 求 0→3 最短路径(图:0-1, 0-2, 1-3, 2-3):

  1. 队列:[0] → 出队 0,入队 1,2
  2. 出队 1,入队 3;出队 2,入队 3(但 3 已访问)
  3. 出队 3 → 目标达成,路径长度=2(0→1→3 或 0→2→3)

〔图算法实战〕

【Dijkstra 图解】(以 0 为源点):

  1. 初始化:dist[0]=0,其余=∞;优先队列 [(0,0)]
  2. 出队 (0,0) → 更新邻居:dist[1]=2, dist[2]=5
  3. 出队 (1,2) → 更新:dist[3]=2+1=3
  4. 出队 (3,3) → 更新:dist[2]=min(5, 3+1)=4
  5. 出队 (2,4) → 无更优更新
  6. 结果:dist=[0,2,4,3]

【业务映射】:地图导航(高德/百度)、网络路由(OSPF 协议)、社交网络(六度分隔理论)。