JAVA进阶技术之十二：JAVA 与算法的碰撞
在 Java 开发的广阔天地中，算法犹如隐藏其中的魔法钥匙，解锁着高效、智能与创新的大门。对于中高级 Java 程序员而言，深入理解算法与 Java 的融合，不仅能优化代码质量，更能拓展技术视野，应对复杂多变的开发需求。今天咱们来探索精彩的算法实例。
一、排序算法——Java 中的经典演绎
排序是编程世界里最基础却又至关重要的操作。以冒泡排序为例，它的思想简单直观：多次遍历数组，相邻元素两两比较，将较大（或较小）的元素往后“冒泡”。
算法说明：
在每一轮遍历中，从数组的起始位置开始，比较相邻的两个元素。若顺序不符合要求（如升序排列时前一个元素大于后一个元素），则交换它们的位置。经过一轮遍历，数组末尾的元素便是当前未排序部分的最大值（或最小值）。如此反复，直到整个数组有序。
应用场景：
当需要对小规模数据进行简单排序时，冒泡排序就有用武之地。比如在小型项目的数据预处理阶段，对一些配置参数按照特定顺序排列，方便后续的读取与处理。 Java 代码实现：
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(array);
for (int num : array) {
System.out.print(num + " ");
}
}
}
在这段代码中，外层循环控制排序的轮数，内层循环负责每一轮中的相邻元素比较与交换。通过两层嵌套循环，实现了冒泡排序的逻辑，最终在主函数中打印出排序后的数组。
二、搜索算法——在海量数据中精准定位
二分搜索算法极大地提高了搜索效率，前提是数据已排序。
算法说明：
它每次都从数组的中间元素开始查找。如果目标值等于中间元素，则查找成功；若目标值小于中间元素，则在数组的左半部分继续查找；反之，在右半部分查找。重复这个过程，直到找到目标值或者确定目标值不存在。
应用场景：
在数据库查询优化、海量日志文件中查找特定记录等场景下，二分搜索能快速定位所需信息，节省大量时间。比如电商系统中，根据用户输入的商品 ID 从已排序的商品列表里快速检索商品详情。
Java 代码实现：
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int 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[] sortedArray = {10, 20, 30, 40, 50, 60};
int targetValue = 30;
int result = binarySearch(sortedArray, targetValue);
if (result!= -1) {
System.out.println("元素在数组中的索引为： " + result);
} else {
System.out.println("未找到该元素。");
}
}
}
这里，通过不断调整搜索区间（由 left 和 right 界定），并依据中间元素与目标值的比较结果，持续逼近目标值，最终返回其索引或表示未找到的标识。
三、动态规划——解决复杂优化问题的利器
动态规划常用于解决具有重叠子问题和最优子结构性质的问题，以斐波那契数列计算为例。
算法说明：
斐波那契数列的定义是：F(n) = F(n - 1) + F(n - 2)，初始值 F(0) = 0，F(1) = 1。传统的递归计算方式会存在大量重复计算，动态规划则采用自底向上的方式，先计算较小规模的子问题，保存结果，后续直接使用，避免重复求解。
应用场景：
在资源分配、路径规划等领域广泛应用。例如，计算不同步数下到达楼梯顶端的方法数，就类似斐波那契数列的模型，每一步的走法取决于前一步和前两步的状态。
Java 代码实现：
public class FibonacciDP {
public static int fibonacci(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 void main(String[] args) {
int n = 10;
System.out.println("斐波那契数列第 " + n + " 项的值为： " + fibonacci(n));
}
}
代码中，创建数组 dp 存储中间结果，按照斐波那契数列的递推公式依次计算并存储，最后返回指定项的值，大大提高了计算效率。
四、贪心算法 —— 局部最优求全局最优
贪心算法在每一步决策时都选择当前状态下的最优解，期望最终得到全局最优解，虽然它并不总是能保证得到绝对最优，但在很多场景下效率极高。
算法说明：
以找零问题为例，假设有各种面值的货币，如 1 元、5 元、10 元、20 元等，要找给顾客给定金额的零钱。贪心算法的做法是，优先使用面值大的货币，尽可能多地用大面值去凑目标金额，直到无法再用大面值凑足时，再使用次大面值，依次类推。
应用场景：
在任务调度、资源分配等方面广泛应用。比如在操作系统的进程调度中，优先安排短作业优先执行，以期望整体的平均周转时间最短；在网络传输中，优先传输重要性高、体积小的数据块，提升传输效率。
Java 代码实现（找零问题）：
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class GreedyChange {
private static final List<Integer> denominations = Arrays.asList(20, 10, 5, 1);
public static List<Integer> makeChange(int amount) {
int[] counts = new int[denominations.size()];
for (int i = 0; i < denominations.size(); i++) {
counts[i] = amount / denominations.get(i);
amount %= denominations.get(i);
}
return IntStream.range(0, counts.length)
.mapToObj(i -> Collections.nCopies(counts[i], denominations.get(i)))
.flatMap(Collection::stream)
.collect(Collectors.toList());
}
public static void main(String[] args) {
int amount = 57;
List<Integer> change = makeChange(amount);
System.out.println("找零组合： " + change);
}
}
这里，首先定义了可用的货币面值列表，然后按照贪心策略，依次计算每种面值所需的数量，最后返回找零的组合列表。
五、深度优先搜索（DFS）—— 遍历图与树的有力武器
深度优先搜索沿着一条路径尽可能深地探索，直到无法继续，再回溯到上一个未完全探索的节点，继续探索其他路径。
算法说明：
对于一个图结构（或树结构，可看作特殊的图），从起始节点开始，标记已访问，然后选择一个邻接节点深入访问，如果该邻接节点还有未访问的邻接节点，继续递归深入，直到遇到叶子节点或所有邻接节点都已访问，回溯到上一层节点，重复这个过程，直到所有节点都被访问。
应用场景：
常用于路径查找、拓扑排序、解决迷宫问题等。例如在游戏地图的自动寻路功能中，通过深度优先搜索探索从起点到终点的可行路径；在编译器对代码语法树的分析中，利用 DFS 遍历语法结构。
Java 代码实现（简单图的 DFS 遍历）：
import java.util.ArrayList;
import java.util.List;
class Graph {
private int V;
private List<List<Integer>> adjList;
public Graph(int vertices) {
V = vertices;
adjList = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int source, int destination) {
adjList.get(source).add(destination);
adjList.get(destination).add(source);
}
public void DFSUtil(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
List<Integer> neighbors = adjList.get(v);
for (Integer neighbor : neighbors) {
if (!visited[neighbor]) {
DFSUtil(neighbor, visited);
}
}
}
public void DFS(int startVertex) {
boolean[] visited = new boolean[V];
DFSUtil(startVertex, visited);
}
}
public class DFSExample {
public static void main(String[] args) {
Graph graph = new Graph(7);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(2, 6);
graph.DFS(0);
}
}
这段代码先构建了一个图的数据结构，包含节点数和邻接表，然后实现了深度优先搜索的核心方法 DFSUtil，通过递归深入邻接节点并标记访问状态，最后从指定起始节点开始启动 DFS 遍历。
六、广度优先搜索（BFS）—— 层层递进找目标
与深度优先搜索不同，广度优先搜索从起始节点开始，逐层地向外扩展，先访问距离起始节点近的节点，再依次访问距离更远的节点。
算法说明：
利用队列数据结构，首先将起始节点入队并标记已访问，然后循环取出队首节点，将其未访问的邻接节点入队并标记，如此循环，直到队列为空，确保按照节点到起始节点的距离顺序进行遍历。
应用场景：
在社交网络分析中，查找两个人之间的最短关系路径；在地图导航的实时路况更新时，从当前位置向外扩散，快速获取周边区域的路况信息。
Java 代码实现（简单图的 BFS 遍历）：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class GraphBFS {
private int V;
private List<List<Integer>> adjList;
public GraphBFS(int vertices) {
V = vertices;
adjList = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int source, int destination) {
adjList.get(source).add(destination);
adjList.get(destination).add(source);
}
public void BFS(int startVertex) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[startVertex] = true;
queue.add(startVertex);
while (!queue.isEmpty()) {
int currentVertex = queue.poll();
System.out.print(currentVertex + " ");
List<Integer> neighbors = adjList.get(currentVertex);
for (Integer neighbor : neighbors) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
}
public class BFSExample {
public static void main(String[] args) {
GraphBFS graph = new GraphBFS(7);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(2, 6);
graph.BFS(0);
}
}
这里构建图结构后，在 BFS 方法中借助队列实现广度优先搜索，依次将同层节点出队处理并将下一层邻接节点入队，从而完成按层遍历。
算法世界丰富多彩，这些不同类型的算法与 Java 结合，能解决各式各样的复杂问题。持续钻研，让算法成为我们 Java 编程路上的得力伙伴，助力我们攻克更多难关，书写更优质的代码。
后续我还会分享更多 Java 开发相关的知识，记得关注怡格网，别错过精彩篇章哦！
最近一直在研究AI公众号爆文的运维逻辑，也在学习各种前沿的AI技术，加入了不会笑青年和纯洁的微笑两位大佬组织起来的知识星球，也开通了自己的星球：
怡格网友圈，地址是：https://wx.zsxq.com/group/51111855584224
这是一个付费的星球，暂时我还没想好里面放什么，现阶段不建议大家付费和进入我自己的星球，即使有不小心付费的，我也会直接退费，无功不受禄。如果你也对AI特别感兴趣，推荐你付费加入他们的星球：
AI俱乐部，地址是：https://t.zsxq.com/mRfPc 。
建议大家先加
微信号:yeegee2024
或者关注微信公众号:yeegeexb2014
咱们产品成型了之后，咱们再一起进入星球，一起探索更美好的未来！