Java算法大全：常用算法的思路与代码实践
算法不是一组需要背下来的代码，而是针对特定问题选择合适的数据组织方式和计算步骤。面对一个任务，先确认输入规模、数据是否有序、结果是否允许近似，再考虑时间复杂度、空间复杂度和边界条件，通常比直接套模板更有效。
本文通过一份可运行的 Java 示例，介绍二分查找、归并排序、最大子数组和、滑动窗口、图的广度优先搜索、Dijkstra 最短路径以及零钱兑换动态规划。示例使用 Java 8 语法，不依赖第三方库。代码假设输入符合各方法说明中的约束；如果用于外部输入，还应按业务需要增加参数校验。
一、先看复杂度和边界
常见的时间复杂度从较快到较慢，大致包括 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 和 O(2n)。这只是增长趋势，不代表实际运行时间：数据规模、常数开销、内存访问模式和输入分布都会影响结果。空间复杂度则关注算法额外使用的内存；递归还要考虑调用栈。
边界检查应贯穿实现，而不是等到出现异常才补。常见情况包括空数组、只有一个元素、重复值、负数、零、整数溢出，以及参数是否可能超出数组或内存承受范围。下面的代码会说明它们各自的前提。
二、二分查找：有序数据中的快速定位
二分查找适用于已经按升序排列的数组。每次比较都能排除大约一半候选范围，时间复杂度为 O(log n)，空间复杂度为 O(1)。它不适用于未排序数据；若只是为了查找一次而先排序，排序成本可能超过直接扫描。
下面实现的是 lower bound：返回第一个大于或等于目标值的位置。如果所有元素都小于目标值，返回数组长度。这样既能判断目标是否存在，也能处理重复元素并找到其首次出现位置。
static int lowerBound(int[] a, int target) {
int left = 0;
int right = a.length; // 搜索区间为 [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (a[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}计算中点时使用 left + (right - left) / 2，避免直接相加造成整数溢出。常见错误是循环区间的定义和边界更新不一致，例如使用闭区间却遗漏 left = mid + 1，导致循环无法结束。调用后要检查返回位置是否小于数组长度，再比较对应元素；不能直接访问 a[a.length]。
三、归并排序：稳定的 O(n log n) 排序
归并排序把数组不断拆成两半，分别排序，再将两个有序部分合并。时间复杂度为 O(n log n)，额外空间复杂度为 O(n)。它是稳定排序：相等元素合并时先取左侧元素，可以保留它们原有的相对顺序。
当需要稳定排序，或希望最坏时间复杂度保持在 O(n log n) 时，归并排序是一个清晰的选择。代价是需要额外数组。对于一般业务排序，优先评估 Java 标准库排序方法；自行实现通常是为了学习、特定数据结构或明确的性能需求。
static void mergeSort(int[] a) {
if (a.length < 2) {
return;
}
int[] temp = new int[a.length];
mergeSort(a, temp, 0, a.length);
}
static void mergeSort(int[] a, int[] temp, int from, int to) {
if (to - from < 2) {
return;
}
int mid = from + (to - from) / 2;
mergeSort(a, temp, from, mid);
mergeSort(a, temp, mid, to);
int i = from;
int j = mid;
int k = from;
while (i < mid && j < to) {
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i < mid) {
temp[k++] = a[i++];
}
while (j < to) {
temp[k++] = a[j++];
}
System.arraycopy(temp, from, a, from, to - from);
}这里使用左闭右开区间 [from, to)，长度为 to - from，能让分割和复制范围保持一致。若把数组切分时写成边界不一致的闭区间，容易漏掉最后一个元素或越界。对超大输入，递归深度约为 log n，通常不会像线性递归那样迅速耗尽栈，但仍应结合实际运行环境评估。
四、最大子数组和：动态规划的简洁应用
最大子数组和问题要求在非空连续子数组中找到元素和最大的一个。设 endingHere 表示必须以当前位置结尾的最大和：要么把当前元素接在之前的子数组后面，要么从当前元素重新开始。每步更新全局最大值，时间复杂度 O(n)，额外空间 O(1)。
static long maxSubarraySum(int[] a) {
if (a.length == 0) {
throw new IllegalArgumentException("数组不能为空");
}
long endingHere = a[0];
long best = a[0];
for (int i = 1; i < a.length; i++) {
endingHere = Math.max((long) a[i], endingHere + a[i]);
best = Math.max(best, endingHere);
}
return best;
}初始化为第一个元素，而不是 0，是为了正确处理全为负数的数组；本方法把空数组视为非法输入，并通过异常明确表达。结果使用 long，避免许多常见规模下的求和溢出。不过，任何固定宽度整数类型仍有上限；若业务输入可能使总和超过 long 范围，应使用 BigInteger 或重新定义输入限制。
五、滑动窗口：满足条件的连续区间
滑动窗口适用于连续子数组或子串问题。当窗口右端扩展后，可以通过移动左端恢复约束时，往往能把枚举所有区间的 O(n²) 做到 O(n)。本例求“最多包含 k 种不同整数”的最长连续子数组，使用哈希表记录窗口内各值的频次。
static int longestAtMostKDistinct(int[] a, int k) {
if (k <= 0 || a.length == 0) {
return 0;
}
Map<Integer, Integer> counts = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < a.length; right++) {
counts.put(a[right], counts.getOrDefault(a[right], 0) + 1);
while (counts.size() > k) {
int value = a[left++];
int count = counts.get(value) - 1;
if (count == 0) {
counts.remove(value);
} else {
counts.put(value, count);
}
}
best = Math.max(best, right - left + 1);
}
return best;
}每个元素至多进入和离开窗口一次，哈希表操作按平均 O(1) 估算，因此整体平均时间复杂度为 O(n)，空间复杂度取决于窗口中不同值的数量。k <= 0 时，按“最多包含 k 种不同值”的定义不存在非空合法窗口，方法返回 0。
滑动窗口并非所有区间题目的通用解法。比如在含负数的数组中，窗口和超过某个目标值后，移动左端不一定能让和单调减小，依赖单调性的方案便不再成立。使用前要先证明移动边界能够持续缩小搜索范围。
六、广度优先搜索：无权图的最少步数
广度优先搜索（BFS）从起点一层层扩展，适合遍历图、网格和树，也适合求无权图中从起点到各点的最少边数。时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数；邻接表实现的空间复杂度为 O(V + E)。
static int[] bfs(List<List<Integer>> graph, int source) {
int n = graph.size();
if (source < 0 || source >= n) {
throw new IllegalArgumentException("起点编号无效");
}
int[] distance = new int[n];
Arrays.fill(distance, -1);
ArrayDeque<Integer> queue = new ArrayDeque<>();
distance[source] = 0;
queue.addLast(source);
while (!queue.isEmpty()) {
int node = queue.removeFirst();
for (int next : graph.get(node)) {
if (next < 0 || next >= n) {
throw new IllegalArgumentException("邻接点编号无效");
}
if (distance[next] == -1) {
distance[next] = distance[node] + 1;
queue.addLast(next);
}
}
}
return distance;
}距离数组同时充当访问标记，-1 表示不可达。顶点应编号为 0 到 n - 1，图的每个邻接表也必须符合这一约定。对于无向图，建图时要把边加入两个端点的邻接表；只加入一侧会意外得到有向关系。
七、Dijkstra：非负权图的最短路径
Dijkstra 算法适用于边权非负的加权图，常用优先队列每次取当前距离最小的顶点。邻接表加二叉堆实现的时间复杂度通常写作 O((V + E) log V)，空间复杂度为 O(V + E)。它不适用于存在负权边的图；有负权边时，应根据问题考虑 Bellman–Ford 等算法。
static final class Edge {
final int to;
final long weight;
Edge(int to, long weight) {
this.to = to;
this.weight = weight;
}
}
static long[] dijkstra(List<List<Edge>> graph, int source) {
int n = graph.size();
if (source < 0 || source >= n) {
throw new IllegalArgumentException("起点编号无效");
}
final long INF = Long.MAX_VALUE / 4;
long[] distance = new long[n];
Arrays.fill(distance, INF);
distance[source] = 0;
PriorityQueue<long[]> pq =
new PriorityQueue<>(Comparator.comparingLong(x -> x[0]));
pq.add(new long[]{0, source});
while (!pq.isEmpty()) {
long[] item = pq.poll();
long currentDistance = item[0];
int node = (int) item[1];
// 同一顶点可能有过期队列项，只处理最新距离
if (currentDistance != distance[node]) {
continue;
}
for (Edge edge : graph.get(node)) {
if (edge.to < 0 || edge.to >= n || edge.weight < 0) {
throw new IllegalArgumentException("边端点无效或权重为负");
}
// 避免候选距离越过所选的哨兵上限
if (currentDistance > INF - edge.weight) {
continue;
}
long candidate = currentDistance + edge.weight;
if (candidate < distance[edge.to]) {
distance[edge.to] = candidate;
pq.add(new long[]{candidate, edge.to});
}
}
}
return distance;
}返回结果中，仍为 INF 的顶点表示不可达。这里将 Long.MAX_VALUE / 4 用作哨兵，并跳过超过该上限的候选路径，因此调用方应确保业务所需的合法最短距离小于此值；若需要表示更大的数值，应设计适合业务的距离表示和溢出处理方式。边权为 0 是允许的，负权则会被拒绝。
八、动态规划：零钱兑换的最少硬币数
零钱兑换问题的一个经典版本是：给定若干正整数面额，每种硬币数量不限，求凑出指定金额所需的最少硬币数。定义 dp[x] 为凑出金额 x 的最少硬币数，枚举最后使用的面额，得到转移式 dp[x] = min(dp[x], dp[x - coin] + 1)。时间复杂度为 O(amount × 硬币种类数)，空间复杂度为 O(amount)。
static int coinChange(int[] coins, int amount) {
if (amount < 0) {
throw new IllegalArgumentException("金额不能为负");
}
for (int coin : coins) {
if (coin <= 0) {
throw new IllegalArgumentException("硬币面额必须为正数");
}
}
int unreachable = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, unreachable);
dp[0] = 0;
for (int value = 1; value <= amount; value++) {
for (int coin : coins) {
if (coin <= value && dp[value - coin] != unreachable) {
dp[value] = Math.min(dp[value], dp[value - coin] + 1);
}
}
}
return dp[amount] == unreachable ? -1 : dp[amount];
}方法返回 -1 表示无法凑出金额；金额为 0 时返回 0。请注意，amount + 1 和长度为 amount + 1 的数组都受 Java 的整数范围及可用内存限制。特别是金额很大时，数组可能无法分配，因此真实服务应对金额设置合理上限，并根据问题规模选择其他方法。硬币面额必须是正数，否则递推可能失去意义，甚至出现无效计算。
九、完整可运行示例
将下面代码保存为 CommonAlgorithms.java，使用 Java 8 或更高版本编译运行：javac CommonAlgorithms.java，然后执行 java CommonAlgorithms。此完整类包含前文各方法以及演示入口。
import java.util.*;
public class CommonAlgorithms {
static int lowerBound(int[] a, int target) {
int left = 0, right = a.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (a[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
static void mergeSort(int[] a) {
if (a.length < 2) return;
mergeSort(a, new int[a.length], 0, a.length);
}
static void mergeSort(int[] a, int[] temp, int from, int to) {
if (to - from < 2) return;
int mid = from + (to - from) / 2;
mergeSort(a, temp, from, mid);
mergeSort(a, temp, mid, to);
int i = from, j = mid, k = from;
while (i < mid && j < to) {
if (a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i < mid) temp[k++] = a[i++];
while (j < to) temp[k++] = a[j++];
System.arraycopy(temp, from, a, from, to - from);
}
static long maxSubarraySum(int[] a) {
if (a.length == 0) {
throw new IllegalArgumentException("数组不能为空");
}
long endingHere = a[0], best = a[0];
for (int i = 1; i < a.length; i++) {
endingHere = Math.max((long) a[i], endingHere + a[i]);
best = Math.max(best, endingHere);
}
return best;
}
static int longestAtMostKDistinct(int[] a, int k) {
if (k <= 0 || a.length == 0) return 0;
Map<Integer, Integer> counts = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < a.length; right++) {
counts.put(a[right], counts.getOrDefault(a[right], 0) + 1);
while (counts.size() > k) {
int value = a[left++];
int count = counts.get(value) - 1;
if (count == 0) counts.remove(value);
else counts.put(value, count);
}
best = Math.max(best, right - left + 1);
}
return best;
}
static int[] bfs(List<List<Integer>> graph, int source) {
int n = graph.size();
if (source < 0 || source >= n) {
throw new IllegalArgumentException("起点编号无效");
}
int[] distance = new int[n];
Arrays.fill(distance, -1);
ArrayDeque<Integer> queue = new ArrayDeque<>();
distance[source] = 0;
queue.addLast(source);
while (!queue.isEmpty()) {
int node = queue.removeFirst();
for (int next : graph.get(node)) {
if (next < 0 || next >= n) {
throw new IllegalArgumentException("邻接点编号无效");
}
if (distance[next] == -1) {
distance[next] = distance[node] + 1;
queue.addLast(next);
}
}
}
return distance;
}
static final class Edge {
final int to;
final long weight;
Edge(int to, long weight) {
this.to = to;
this.weight = weight;
}
}
static long[] dijkstra(List<List<Edge>> graph, int source) {
int n = graph.size();
if (source < 0 || source >= n) {
throw new IllegalArgumentException("起点编号无效");
}
final long INF = Long.MAX_VALUE / 4;
long[] distance = new long[n];
Arrays.fill(distance, INF);
distance[source] = 0;
PriorityQueue<long[]> pq =
new PriorityQueue<>(Comparator.comparingLong(x -> x[0]));
pq.add(new long[]{0, source});
while (!pq.isEmpty()) {
long[] item = pq.poll();
long currentDistance = item[0];
int node = (int) item[1];
if (currentDistance != distance[node]) continue;
for (Edge edge : graph.get(node)) {
if (edge.to < 0 || edge.to >= n || edge.weight < 0) {
throw new IllegalArgumentException("边端点无效或权重为负");
}
if (currentDistance > INF - edge.weight) continue;
long candidate = currentDistance + edge.weight;
if (candidate < distance[edge.to]) {
distance[edge.to] = candidate;
pq.add(new long[]{candidate, edge.to});
}
}
}
return distance;
}
static int coinChange(int[] coins, int amount) {
if (amount < 0) {
throw new IllegalArgumentException("金额不能为负");
}
for (int coin : coins) {
if (coin <= 0) {
throw new IllegalArgumentException("硬币面额必须为正数");
}
}
int unreachable = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, unreachable);
dp[0] = 0;
for (int value = 1; value <= amount; value++) {
for (int coin : coins) {
if (coin <= value && dp[value - coin] != unreachable) {
dp[value] = Math.min(dp[value], dp[value - coin] + 1);
}
}
}
return dp[amount] == unreachable ? -1 : dp[amount];
}
public static void main(String[] args) {
int[] sorted = {1, 2, 2, 4, 7};
System.out.println("lowerBound(2) = " + lowerBound(sorted, 2));
int[] values = {5, 1, 4, 2, 8};
mergeSort(values);
System.out.println("排序结果 = " + Arrays.toString(values));
System.out.println("最大子数组和 = "
+ maxSubarraySum(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
System.out.println("最多两种不同值的最长窗口 = "
+ longestAtMostKDistinct(new int[]{1, 2, 1, 3, 2}, 2));
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, 5));
System.out.println("最短距离 = "
+ Arrays.toString(dijkstra(weighted, 0)));
System.out.println("最少硬币数 = "
+ coinChange(new int[]{1, 2, 5}, 11));
}
}十、选择算法时的实用检查清单
- 数据是否有序？有序数组可以考虑二分查找；如果查询很多，排序和维护顺序的成本也要计算。
- 问题是否涉及连续区间？检查窗口移动是否具备单调性，不能只因题目出现“子数组”就机械套滑动窗口。
- 图的边权是什么？无权最短路可用 BFS；非负权最短路可用 Dijkstra；负权边需要其他方法。
- 结果和中间值会不会溢出？Java 的整数溢出不会自动抛出异常。应根据输入上限选择
long、检查加法，或使用大整数类型。 - 输入规模是否有上限？算法复杂度之外，数组分配、递归深度和对象数量也会影响可运行性。对外部输入尤其要限制规模，避免不受控的数据消耗过多 CPU 或内存。
算法代码只解决计算问题，本身不等于安全机制。二分查找或 Dijkstra 不会自动验证调用方身份、权限或数据可信度；对于不可信输入，仍应在边界处进行类型、范围和数量校验。涉及支付、权限、密码学或其他高风险业务时，应使用经过审查的领域实现与成熟库，并按实际威胁模型测试，不能把教学示例直接当作安全方案。
掌握这些算法的关键，不是记住每一行代码，而是能说清楚：算法依赖什么前提，为什么每轮迭代都在推进，以及哪些输入会破坏这个前提。把复杂度分析、边界测试和输入约束一起纳入实现，才能把算法从题解带到可靠的软件代码中。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
