java常见算法合集
Java 中的常见算法可以按照用途和复杂度分为多个类别，下面整理一份 Java 常见算法合集，包括每种算法的简要说明、实现示例以及适用场景。
🧮 一、排序算法（Sorting Algorithms）
| 算法 |
时间复杂度（平均） |
是否稳定 |
描述 |
| 冒泡排序 |
O(n²) |
✅ 是 |
相邻元素比较交换 |
| 选择排序 |
O(n²) |
❌ 否 |
每次选最小值放到前面 |
| 插入排序 |
O(n²) |
✅ 是 |
构建有序序列 |
| 快速排序 |
O(n log n) |
❌ 否 |
分治策略，递归排序 |
| 归并排序 |
O(n log n) |
✅ 是 |
分治策略，稳定排序 |
| 堆排序 |
O(n log n) |
❌ 否 |
利用最大堆结构排序 |
| 计数排序 |
O(n + k) |
✅ 是 |
适用于整数排序 |
| 桶排序 |
O(n + k) |
✅ 是 |
将数据分到桶中再排序 |
| 基数排序 |
O(n * k) |
✅ 是 |
按位数排序 |
示例：快速排序
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
quickSort(arr, 0, arr.length - 1);
}
}
🔍 二、查找算法（Searching Algorithms）
| 算法 |
时间复杂度 |
描述 |
| 线性查找 |
O(n) |
遍历数组查找目标 |
| 二分查找 |
O(log n) |
适用于有序数组 |
| 插值查找 |
O(log log n) |
优化版二分查找 |
| 斐波那契查找 |
O(log n) |
使用斐波那契数列划分区间 |
示例：二分查找
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
System.out.println(binarySearch(arr, 5));
}
}
📈 三、动态规划（Dynamic Programming）
用于解决最优化问题，如：
- 背包问题（Knapsack）
- 最长公共子序列（LCS）
- 最长递增子序列（LIS）
- 编辑距离（Edit Distance）
- 矩阵链乘法（Matrix Chain Multiplication）
示例：最长公共子序列（LCS）
public class LCS {
public static String longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
sb.append(text1.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}
public static void main(String[] args) {
System.out.println(longestCommonSubsequence("abcde", "ace"));
}
}
🧭 四、图论算法（Graph Algorithms）
| 算法 |
应用场景 |
| DFS / BFS |
图遍历、连通性判断 |
| Dijkstra |
单源最短路径 |
| Floyd-Warshall |
多源最短路径 |
| Prim / Kruskal |
最小生成树 |
| 拓扑排序 |
有向无环图任务调度 |
| 强连通分量（Tarjan） |
图分析 |
示例：Dijkstra 最短路径
import java.util.*;
public class Dijkstra {
static class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public static void dijkstra(List<List<Edge>> graph, int start, int n) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int u = current[0], d = current[1];
if (d > dist[u]) continue;
for (Edge edge : graph.get(u)) {
int v = edge.to, w = edge.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{v, dist[v]});
}
}
}
System.out.println(Arrays.toString(dist));
}
public static void main(String[] args) {
int n = 5;
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
graph.get(0).add(new Edge(1, 4));
graph.get(0).add(new Edge(2, 1));
graph.get(2).add(new Edge(1, 2));
graph.get(1).add(new Edge(3, 1));
graph.get(2).add(new Edge(3, 5));
graph.get(3).add(new Edge(4, 3));
dijkstra(graph, 0, n);
}
}
🧮 五、字符串匹配算法（String Matching）
| 算法 |
时间复杂度 |
描述 |
| 暴力匹配 |
O(nm) |
逐个字符比对 |
| KMP 算法 |
O(n + m) |
利用前缀表避免回溯 |
| Rabin-Karp |
O(n + m) |
哈希滚动匹配 |
| Boyer-Moore |
O(nm) |
从后往前比对 |
示例：KMP 算法
public class KMP {
public static int[] buildLPS(String pattern) {
int[] lps = new int[pattern.length()];
int len = 0;
int i = 1;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
public static List<Integer> kmpSearch(String text, String pattern) {
List<Integer> result = new ArrayList<>();
int[] lps = buildLPS(pattern);
int i = 0, j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
}
if (j == pattern.length()) {
result.add(i - j);
j = lps[j - 1];
} else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
return result;
}
public static void main(String[] args) {
System.out.println(kmpSearch("abababaabab", "aba"));
}
}
📊 六、其他实用算法
| 算法 |
描述 |
| 背包问题 |
动态规划经典问题 |
| 汉诺塔 |
递归经典问题 |
| 快速幂 |
快速计算 a^b mod m |
| 位运算技巧 |
如异或交换、统计1的个数等 |
| 并查集 |
处理集合合并与查询 |
示例：快速幂算法
public class FastPower {
public static long fastPower(long base, long exponent, long mod) {
long result = 1;
base %= mod;
while (exponent > 0) {
if ((exponent & 1) == 1) result = (result * base) % mod;
base = (base * base) % mod;
exponent >>= 1;
}
return result;
}
public static void main(String[] args) {
System.out.println(fastPower(2, 10, 1000));
}
}
📚 七、推荐学习资源
✅ 总结：Java 常见算法分类一览
| 类别 |
算法名称 |
| 排序 |
冒泡、快排、归并、堆排 |
| 查找 |
二分、插值、斐波那契 |
| 动态规划 |
LCS、背包、LIS |
| 图论 |
DFS/BFS、Dijkstra、Prim、拓扑排序 |
| 字符串 |
KMP、Rabin-Karp、Boyer-Moore |
| 数学 |
快速幂、大数相加、素数判断 |
| 实用 |
并查集、贪心算法、回溯算法 |
如果你正在准备面试或提升编程能力，建议按以下顺序学习：
排序算法 → 查找算法 → 动态规划 → 图论 → 字符串匹配 → 实战刷题（LeetCode）
掌握这些算法，不仅能帮助你通过技术面试，还能让你在实际开发中写出更高效、更优雅的代码。