java常见算法合集

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)); // 输出 4

}

}

📈 三、动态规划（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")); // 输出 "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> graph, int start, int n) {

int[] dist = new int[n];

Arrays.fill(dist, Integer.MAX_VALUE);

dist[start] = 0;

PriorityQueue 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> 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-KarpO(n + m)哈希滚动匹配Boyer-MooreO(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 kmpSearch(String text, String pattern) {

List 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")); // 输出 [0, 2, 6]

}

}

📊 六、其他实用算法

算法描述背包问题动态规划经典问题汉诺塔递归经典问题快速幂快速计算 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)); // 输出 24

}

}

📚 七、推荐学习资源

类型推荐资源视频课程B站《尚硅谷 Java 数据结构与算法》在线练习LeetCode、牛客网、蓝桥杯书籍《算法导论》《剑指 Offer》《程序员代码面试指南》GitHubhttps://github.com/ztiany/JavaAlgorithm

✅ 总结：Java 常见算法分类一览

类别算法名称排序冒泡、快排、归并、堆排查找二分、插值、斐波那契动态规划LCS、背包、LIS图论DFS/BFS、Dijkstra、Prim、拓扑排序字符串KMP、Rabin-Karp、Boyer-Moore数学快速幂、大数相加、素数判断实用并查集、贪心算法、回溯算法

如果你正在准备面试或提升编程能力，建议按以下顺序学习：

排序算法 → 查找算法 → 动态规划 → 图论 → 字符串匹配 → 实战刷题（LeetCode）

掌握这些算法，不仅能帮助你通过技术面试，还能让你在实际开发中写出更高效、更优雅的代码。