Java算法大全：常见算法原理与实现示例

算法不是脱离问题的代码模板。选算法时，既要看输入规模和数据结构，也要看结果是否需要稳定、图中是否有负权边、内存是否允许保存中间状态。实现时还要处理空输入、索引边界和数值溢出等问题。

本文用 Java 标准库介绍几类常见算法：归并排序、二分查找、图的广度优先搜索、Dijkstra 最短路径、KMP 字符串匹配和 0/1 背包。示例可保存为 AlgorithmExamples.java，使用 Java 8 或更高版本编译运行。各算法代码集中在一个类中，便于复制验证。

一、先明确复杂度与边界

时间复杂度描述输入规模增长时，运行步骤大致如何增长；空间复杂度描述额外内存的增长趋势。它们不是精确的运行时间承诺：常数开销、硬件、数据分布和 JVM 状态都会影响实际耗时。

• 数组下标：长度为 n 的数组合法下标是 0 到 n - 1。空数组没有合法下标。
• 整数运算：Java 的整数溢出不会自动报错，而是按固定宽度回绕。涉及乘法、距离累加、容量计算时，应评估范围，必要时改用 long 并显式检查。
• 递归深度：递归遍历链表或图可能因输入很深而触发 StackOverflowError。大规模输入时，优先考虑显式栈或队列。
• 输入规模：算法复杂度再好，也需要考虑内存上限。保存全部图边、动态规划表或递归状态都可能成为实际限制。

二、归并排序：稳定的 O(n log n) 排序

归并排序采用分治策略：把数组分成两半，分别排序，再将两个有序部分合并。递归层数约为 log n，每层处理约 n 个元素，因此时间复杂度为 O(n log n)。下面的实现对数组进行原地排序（排序结果写回原数组），需要一个长度为 n 的辅助数组，额外空间复杂度为 O(n)。

当两个待合并元素相等时，代码先取左侧元素，因此排序是稳定的：相等元素的相对顺序保持不变。它适合需要稳定排序、且可以接受额外内存的场景。若数据量很大且内存紧张，不能只看时间复杂度。

三、二分查找：有序数据上的快速定位

二分查找每次将搜索区间缩小一半，时间复杂度为 O(log n)，额外空间复杂度为 O(1)。前提是输入数组已经按升序排列。示例返回目标值的任意一个匹配位置；若不存在则返回 -1。

常见错误是对未排序数组使用二分查找，或者把右边界写成数组长度后仍按闭区间处理。实现使用闭区间 [left, right]，并通过 left + (right - left) / 2 计算中点，避免直接相加可能导致的整数溢出。

四、广度优先搜索：按层遍历无权图

广度优先搜索（BFS）从起点开始，先访问距离起点一步的节点，再访问两步的节点，依此类推。对无权图，它可以求从起点到各节点的最少边数。使用邻接表时，遍历时间复杂度为 O(V + E)，空间复杂度为 O(V)；其中 V 是顶点数，E 是边数。

示例将图表示为邻接表，并把图视为有向图；无向图添加边时，需要把两个方向都加入。不可达节点的距离保留为 -1。遍历过程中先标记再入队，能避免同一个节点被重复加入队列。

五、Dijkstra：非负权图的单源最短路径

Dijkstra 算法适用于边权非负的图。每次从尚未确定的节点中选择当前距离最小者，再用它尝试更新相邻节点。下面用优先队列实现，时间复杂度约为 O((V + E) log V)，空间复杂度为 O(V + E)。

它不能正确处理负权边。存在负权边时，应根据具体问题考虑 Bellman-Ford 等算法；若存在可达负权环，还需定义并处理“最短路径不存在”的情况。示例使用 Long.MAX_VALUE 表示不可达距离，并在距离相加前检查溢出。它要求节点编号从 0 到 V - 1，权重为非负 long。

六、KMP：避免字符串匹配中的重复比较

朴素字符串匹配在最坏情况下可能需要 O(nm) 次比较，其中 n 是文本长度，m 是模式串长度。KMP 预先计算模式串的最长相等前后缀信息，在失配时利用已匹配部分跳过不必要的比较，时间复杂度为 O(n + m)，额外空间复杂度为 O(m)。

实现按 Java char 单位比较，即 UTF-16 代码单元，而不是按 Unicode 字素簇比较。对于需要按用户可见字符处理的文本，应先明确规范化和字符边界需求。这里规定空模式串匹配位置为 0；非空模式串找不到时返回 -1。

七、0/1 背包：每个物品最多选择一次

给定物品重量和价值，以及容量上限，0/1 背包要求每个物品选或不选，求不超过容量时的最大总价值。动态规划使用 dp[c] 表示容量不超过 c 时的最大价值，时间复杂度为 O(nW)，空间复杂度优化为 O(W)。

容量循环必须从大到小。若从小到大更新，同一物品可能在一轮中被重复使用，变成完全背包问题。示例允许重量为零的物品（每个仍只计算一次），要求重量、价值非负，容量非负；它使用 long 保存价值，但极端输入下累加仍可能溢出，生产代码应按业务上限检查。

八、完整可运行示例

将以下内容保存为 AlgorithmExamples.java。运行后会演示排序、查找、图遍历、最短路径、字符串匹配和背包结果。示例为了便于阅读，未加入通用的参数校验框架；传入无效节点编号或数组长度不匹配的物品数据时，方法可能抛出异常。

import java.util.*;

public class AlgorithmExamples {
    private static void mergeSort(int[] a) {
        if (a == null || a.length < 2) {
            return;
        }
        int[] temp = new int[a.length];
        sort(a, temp, 0, a.length - 1);
    }

    private static void sort(int[] a, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        sort(a, temp, left, mid);
        sort(a, temp, mid + 1, right);

        int i = left;
        int j = mid + 1;
        int k = left;
        while (i <= mid && j <= right) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        while (j <= right) {
            temp[k++] = a[j++];
        }
        System.arraycopy(temp, left, a, left, right - left + 1);
    }

    // 要求 a 已按升序排列；返回任意一个匹配位置，找不到返回 -1。
    private static int binarySearch(int[] a, int target) {
        int left = 0;
        int right = a.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (a[mid] == target) {
                return mid;
            } else if (a[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    // 图为有向图；不可达节点距离为 -1。
    private static int[] bfs(List<List<Integer>> graph, int start) {
        int n = graph.size();
        int[] distance = new int[n];
        Arrays.fill(distance, -1);
        distance[start] = 0;

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph.get(u)) {
                if (distance[v] == -1) {
                    distance[v] = distance[u] + 1;
                    queue.offer(v);
                }
            }
        }
        return distance;
    }

    private static final class Edge {
        final int to;
        final long weight;

        Edge(int to, long weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    private static final class State {
        final int node;
        final long distance;

        State(int node, long distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    // 所有边权必须非负；Long.MAX_VALUE 表示不可达。
    private static long[] dijkstra(List<List<Edge>> graph, int start) {
        int n = graph.size();
        long[] distance = new long[n];
        Arrays.fill(distance, Long.MAX_VALUE);
        distance[start] = 0L;

        PriorityQueue<State> pq =
            new PriorityQueue<>(Comparator.comparingLong(s -> s.distance));
        pq.offer(new State(start, 0L));

        while (!pq.isEmpty()) {
            State current = pq.poll();
            if (current.distance != distance[current.node]) {
                continue; // 丢弃队列中的过期状态
            }
            for (Edge edge : graph.get(current.node)) {
                if (edge.weight < 0) {
                    throw new IllegalArgumentException("Dijkstra 不支持负权边");
                }
                if (current.distance > Long.MAX_VALUE - edge.weight) {
                    continue; // 本次距离相加会溢出
                }
                long candidate = current.distance + edge.weight;
                if (candidate < distance[edge.to]) {
                    distance[edge.to] = candidate;
                    pq.offer(new State(edge.to, candidate));
                }
            }
        }
        return distance;
    }

    private static int[] buildLps(String pattern) {
        int[] lps = new int[pattern.length()];
        int length = 0;
        int i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                lps[i++] = ++length;
            } else if (length > 0) {
                length = lps[length - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }

    // 返回首次匹配位置；空模式串返回 0，未匹配返回 -1。
    private static int kmpSearch(String text, String pattern) {
        if (pattern.isEmpty()) {
            return 0;
        }
        int[] lps = buildLps(pattern);
        int i = 0;
        int j = 0;
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == pattern.length()) {
                    return i - j;
                }
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return -1;
    }

    // 每件物品最多使用一次；重量、价值和容量均须非负。
    private static long knapsack01(int[] weights, long[] values, int capacity) {
        if (weights.length != values.length) {
            throw new IllegalArgumentException("重量和价值数组长度必须相同");
        }
        if (capacity < 0) {
            throw new IllegalArgumentException("容量不能为负数");
        }
        long[] dp = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            if (weights[i] < 0 || values[i] < 0) {
                throw new IllegalArgumentException("重量和价值不能为负数");
            }
            if (weights[i] > capacity) {
                continue;
            }
            for (int c = capacity; c >= weights[i]; c--) {
                dp[c] = Math.max(dp[c],
                    dp[c - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        int[] numbers = {7, 2, 9, 2, 5};
        mergeSort(numbers);
        System.out.println("排序：" + Arrays.toString(numbers));
        System.out.println("查找 5 的位置：" + binarySearch(numbers, 5));

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(0).add(1);
        graph.get(0).add(2);
        graph.get(1).add(3);
        graph.get(2).add(3);
        System.out.println("BFS 距离：" + Arrays.toString(bfs(graph, 0)));

        List<List<Edge>> weighted = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            weighted.add(new ArrayList<>());
        }
        weighted.get(0).add(new Edge(1, 4));
        weighted.get(0).add(new Edge(2, 1));
        weighted.get(2).add(new Edge(1, 2));
        weighted.get(1).add(new Edge(3, 1));
        weighted.get(2).add(new Edge(3, 7));
        System.out.println("最短距离：" +
            Arrays.toString(dijkstra(weighted, 0)));

        System.out.println("KMP 位置：" + kmpSearch("ababcabcacbab", "abcac"));
        System.out.println("背包最大价值：" +
            knapsack01(new int[]{2, 3, 4}, new long[]{3, 4, 5}, 5));
    }
}

九、如何根据问题选择算法

• 需要对数组整体排序，且稳定性重要：考虑归并排序；若数据规模或内存约束特殊，还要比较其他排序方案。
• 在升序数组中查找元素：使用二分查找；若要找到重复值中的第一个或最后一个，需要调整区间收缩条件，不能假设当前实现会返回边界位置。
• 求无权图的最少边数：使用 BFS；图有边权时，不能简单把 BFS 的层数当成加权最短距离。
• 求非负权图的单源最短路径：使用 Dijkstra；含负权边时改用适合该图性质的算法。
• 查找一个模式串在文本中的位置：可用 KMP；若涉及大小写折叠、Unicode 规范化或按自然语言字符匹配，需要先明确文本处理规则。
• 每个物品最多选一次且容量不大：可用 0/1 背包；容量很大时，O(nW) 的时间和 O(W) 的空间可能不可接受，应重新评估问题条件和算法。

十、常见错误与安全边界

算法代码不等于输入校验。对外部输入使用这些方法时，应检查节点编号、边的目标节点、数组长度和数据规模。比如图的邻接表必须与顶点编号范围一致；容量若由不可信输入决定，直接分配 new long[capacity + 1] 可能造成内存耗尽。还应注意 capacity + 1 本身可能溢出，实际服务应设置合理上限并在分配前校验。

不要把算法的平均或渐进复杂度当成拒绝服务防护保证。攻击者可能构造超大输入，使排序、图遍历或动态规划消耗过多 CPU 和内存。对网络接口或批处理任务，应结合业务设置输入长度、顶点数、边数、容量和执行时间限制，并避免在不可信输入上无限递归。

这些示例是通用算法实现，不是密码学实现。排序、二分查找、KMP、BFS、Dijkstra 和背包都不提供保密性、完整性、身份认证或抗攻击性。不要用它们替代经过审查的加密、签名、密码哈希或安全随机数方案；涉及安全功能时，应使用 Java 标准加密架构（JCA）中的合适 API 或可靠的安全库，并遵循其参数要求。

掌握算法的关键不是记住代码，而是同时记住前置条件、返回约定和资源成本。把这些条件写进注释与测试用例，再用空输入、极小输入、重复值、不可达节点和极端数值验证实现，通常比直接复制模板更能避免隐蔽错误。