Java常用算法及实现汇总_经典算法解析与代码示例

Java 是一门功能强大的编程语言，广泛应用于各种开发场景。在 Java 中，有许多常用的算法和数据结构，掌握它们对于解决实际问题至关重要。以下是一些 Java 中常用的算法及其实现汇总：

1. 排序算法

排序算法是处理数据的基础，常见的排序算法包括：

（1）冒泡排序（Bubble Sort）

原理：通过多次遍历，每次将相邻两个元素比较并交换，最终将的元素“冒泡”到末尾。
时间复杂度：O(n²)

实现：

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;
        }
    }
}
}

（2）快速排序（Quick Sort）

原理：分治法，选择一个基准值，将数组分为两部分，递归排序。
时间复杂度：O(n log n)（平均），O(n²)（最坏）
实现：
```java
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}

private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
```

（3）归并排序（Merge Sort）

原理：分治法，将数组递归分成两部分，分别排序后合并。
时间复杂度：O(n log n)
实现：
```java
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 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);
}
```

2. 查找算法

查找算法用于在数据集中定位目标元素。

（1）线性查找（Linear Search）

原理：逐个遍历数组，直到找到目标元素。
时间复杂度：O(n)

实现：

public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) return i;
}
return -1; // 未找到
}

（2）二分查找（Binary Search）

原理：在有序数组中，通过不断折半缩小查找范围。
时间复杂度：O(log n)

实现：

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; // 未找到
}

3. 动态规划算法

动态规划用于解决具有重叠子问题和子结构性质的问题。

（1）斐波那契数列

原理：通过保存子问题的解，避免重复计算。

实现：

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];
}

（2）0-1 背包问题

原理：在给定容量下，选择物品使得价值化。

实现：

public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= capacity; w++) {
        if (weights[i - 1] <= w) {
            dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
        } else {
            dp[i][w] = dp[i - 1][w];
        }
    }
}
return dp[n][capacity];
}

4. 图算法

图算法用于解决图相关问题，如最短路径、最小生成树等。

（1）Dijkstra 算法（单源最短路径）

原理：贪心算法，逐步扩展最短路径。
实现（简化版）：
```java
import java.util.*;

public static Map dijkstra(Map> graph, int start) {
Map distances = new HashMap<>();
PriorityQueue a[1]));
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int node = current[0], dist = current[1];
if (distances.containsKey(node)) continue;
distances.put(node, dist);
for (Map.Entry neighbor : graph.getOrDefault(node, new HashMap<>()).entrySet()) {
int nextNode = neighbor.getKey(), weight = neighbor.getValue();
if (!distances.containsKey(nextNode)) {
pq.offer(new int[]{nextNode, dist + weight});
}
}
}
return distances;
}
```