java经典算法指在Java语言环境下实现并广泛应用的经典算法模型,涵盖数据结构操作、问题求解策略与性能优化技术。这些算法不仅是计算机科学的理论基石,更是程序员算法思维训练的核心载体。
按算法设计策略可分为:
• 分治法(Divide and Conquer)
• 贪心算法(Greedy Algorithm)
• 动态规划(Dynamic Programming)
• 回溯算法(Backtracking)
• 分支限界法(Branch and Bound)
java经典算法广泛应用于:
• 排序与查找系统
• 网络路由计算
• 编译器优化
• 人工智能路径规划
• 加密与安全协议
评估算法优劣的三大维度:
• 时间复杂度:O(1)、O(log n)、O(n)、O(n log n)、O(n²)等
• 空间复杂度:原地排序 vs 额外空间开销
• 稳定性:相等元素排序后相对位置是否保持
Java作为企业级开发主流语言,其算法实现具有强类型约束、垃圾回收机制、泛型支持等特性,使得算法实现更具工程化价值:
以快速排序为例,Java 7后Arrays.sort()对原生类型使用双轴快速排序(Dual-Pivot Quicksort),平均性能提升10%-20%,体现了语言与算法的深度协同进化。
掌握数组/链表/栈/队列/树/图基础操作,理解递归与分治思想,实现二分查找、冒泡排序、选择排序等O(n²)算法
深入动态规划状态转移、贪心选择性质、回溯剪枝策略,实现快速排序、归并排序、堆排序等O(n log n)算法
掌握图论最短路径(Dijkstra/Floyd)、最小生成树(Prim/Kruskal)、拓扑排序等算法,理解NP完全问题与近似算法
java经典算法必须依托数据结构实现,二者是"方法"与"载体"的共生关系:
| 数据结构 | 典型算法 | Java实现类 |
|---|---|---|
| 数组 | 二分查找、快速排序 | Arrays, ArrayList |
| 链表 | 反转链表、环检测 | LinkedList |
| 栈 | 表达式求值、括号匹配 | Stack, Deque |
| 队列 | BFS遍历、任务调度 | Queue, PriorityQueue |
| 二叉树 | 前中后序遍历、BST操作 | TreeMap, TreeSet |
| 哈希表 | 快速查找、去重统计 | HashMap, HashSet |
| 图 | Dijkstra、Kruskal | 自定义AdjacencyList |
• 误区1:算法题必须用最优时间复杂度
→ 实际工程需平衡可读性与性能,O(n log n)的归并排序有时优于O(n)的暴力法
• 误区2:刷题数量决定算法能力
→ 质量重于数量,理解3种动态规划模型(背包/序列/区间)比机械刷50题更有效
• 误区3:Java性能低于C++
→ 现代JIT编译器使Java在多数场景下性能相当,且具备内存安全等工程优势
java经典算法中,排序是检验算法思维的"试金石",不同场景需选择不同策略
通过元素间比较决定顺序,理论下界为O(n log n)
相邻元素两两比较并交换,每轮将最大值"冒泡"至末尾。时间复杂度O(n²),空间O(1),稳定排序。
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // 提前终止优化
}
}
分治思想典型应用:选基准→分区→递归。平均O(n log n),最坏O(n²),空间O(log n),不稳定。
Java 7后Arrays.sort()对原生类型使用双轴快速排序(Dual-Pivot Quicksort):
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = dualPivotPartition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
private static int dualPivotPartition(int[] arr, int left, int right) {
if (arr[left] > arr[right]) swap(arr, left, right);
int pivot1 = arr[left], pivot2 = arr[right];
int p = left + 1, lt = left + 1, gt = right - 1;
while (p <= gt) {
if (arr[p] < pivot1) {
swap(arr, p, lt);
lt++; p++;
} else if (arr[p] > pivot2) {
swap(arr, p, gt);
gt--;
} else {
p++;
}
}
swap(arr, left, lt - 1);
swap(arr, right, gt + 1);
return lt - 1;
}
稳定排序,时间O(n log n),空间O(n),适合链表排序和外部排序。
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
订单按时间倒序排列,需保持相同时间订单的原始顺序(稳定性要求)→ Java对象数组用TimSort
ERROR > WARN > INFO > DEBUG,固定映射关系→ 计数排序(ERROR→0,WARN→1,...)
实时更新用户积分,取前10名→ 小顶堆(PriorityQueue)
java经典算法中,查找是数据检索的核心能力,不同场景需选择不同策略
顺序扫描所有元素,时间O(n),空间O(1),适用于无序数据
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}
将目标值置于末尾,避免边界检查,减少循环条件判断
public static int sentinelSearch(int[] arr, int target) {
int n = arr.length;
if (n == 0) return -1;
int last = arr[n - 1];
arr[n - 1] = target;
int i = 0;
while (arr[i] != target) i++;
arr[n - 1] = last; // 恢复原值
return (i < n - 1 || last == target) ? i : -1;
}
B+树索引:叶子节点存储数据指针,非叶子节点仅存储索引,适合范围查询
IP范围映射表→ 二分查找(IP转整数后比较)
空间效率极高的概率型数据结构,用于快速判断元素是否存在(可能误判,不会漏判)
java经典算法中,动态规划是解决最优化问题的核心思想
原始递归:F(n) = F(n-1) + F(n-2),存在大量重叠子问题
// 递归(低效)
public static int fib(int n) {
return n <= 1 ? n : fib(n-1) + fib(n-2);
}
// 动态规划(自底向上)
public static int fibDP(int n) {
if (n <= 1) return n;
int[] dp = new int[n+1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
// 空间优化版
public static int fibOptimized(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int temp = a + b;
a = b; b = temp;
}
return b;
}
含冷冻期/手续费/限制交易次数等变体,核心是状态定义与转移
字符串匹配、拼写检查、DNA序列比对
最小路径和、不同路径、地下城游戏
java经典算法中,图论是解决网络连通性问题的核心工具
• 邻接矩阵:适合稠密图(边数接近顶点平方)
• 邻接表:适合稀疏图(边数远小于顶点平方)
// 邻接表实现(Java泛型) public class Graph{ private Map >> adjList; public Graph() { adjList = new HashMap<>(); } public void addVertex(T vertex) { adjList.putIfAbsent(vertex, new ArrayList<>()); } public void addEdge(T from, T to, int weight) { adjList.get(from).add(new Edge<>(to, weight)); } private static class Edge { T target; int weight; Edge(T t, int w) { target = t; weight = w; } } }
递归实现,适合路径存在性判断、连通分量、拓扑排序
public void dfs(T start, Setvisited, List path) { visited.add(start); path.add(start); for (Edge edge : adjList.get(start)) { if (!visited.contains(edge.target)) { dfs(edge.target, visited, path); } } }
队列实现,适合最短路径(无权图)、层次遍历
public List> bfs(T start) { List
> result = new ArrayList<>(); Queue
queue = new LinkedList<>(); Set visited = new HashSet<>(); queue.offer(start); visited.add(start); while (!queue.isEmpty()) { int size = queue.size(); List level = new ArrayList<>(); for (int i = 0; i < size; i++) { T node = queue.poll(); level.add(node); for (Edge edge : adjList.get(node)) { if (!visited.contains(edge.target)) { visited.add(edge.target); queue.offer(edge.target); } } } result.add(level); } return result; }
好友推荐(共同邻居)、最短路径(六度分隔理论验证)
城市间最短路径(Dijkstra/A*)、交通网络分析
模块依赖关系图、拓扑排序检测循环依赖
java经典算法中,递归是问题分解的核心思维范式
public static long factorial(int n) {
if (n <= 1) return 1; // 终止条件
return n * factorial(n - 1); // 递归步骤
}
• 递归:代码简洁,但栈溢出风险高,有函数调用开销
• 迭代:性能稳定,但代码可能冗长
• 优化:尾递归(Java不支持自动优化)、记忆化递归
缓存中间结果,避免重复计算(如斐波那契数列)
将递归调用放在函数末尾(Java不自动优化,需手动转迭代)
用栈模拟调用栈,避免栈溢出(如树的非递归遍历)