Java 算法实战全景

Java 在大规模企业级算法应用中，以强类型安全、JIT 即时编译优化与内存自动回收见长：

• 标准算法工具箱：Collections.sort()、Arrays.binarySearch()、Arrays.parallelSort() 提供高度优化的高性能底座。
• 图论与动态规划：利用标准集合与紧凑状态数组实现工业级算法。

---

📊 算法专题与复杂度

算法专题	典型问题 / 算法	核心思想	时间复杂度	空间复杂度
排序	Dual-Pivot Quicksort / In-Place Sort	双基准快速排序划分	$O(n \log n)$	$O(\log n)$
二分查找	Arrays.binarySearch	变种二分检索	$O(\log n)$	$O(1)$
图遍历	BFS (广度优先遍历)	队列层序遍历与 Set 去重	$O(V + E)$	$O(V)$
动态规划	0/1 背包问题	1D 数组反向遍历更新	$O(N \cdot W)$	$O(W)$

---

1. 排序算法：快速排序 (QuickSort)

public class QuickSortDemo {
    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = arr[high];
            int i = low - 1;
            for (int j = low; j < high; j++) {
                if (arr[j] <= pivot) {
                    i++;
                    int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
                }
            }
            int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
            int pi = i + 1;
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static void main(String[] args) {
        System.out.println("=== Java Dual-Pivot QuickSort & In-Place Sort ===");
        int[] data = {64, 25, 12, 22, 11};
        quickSort(data, 0, data.length - 1);

        for (int i = 0; i < data.length - 1; i++) {
            if (data[i] > data[i + 1]) throw new RuntimeException("Not sorted");
        }
        System.out.println("Java QuickSort tests passed successfully.");
    }
}

🐳 Docker Verified📋eclipse-temurin:21-jdk-alpine

Exit Code: 0

=== Java Dual-Pivot QuickSort & In-Place Sort ===
Java QuickSort tests passed successfully.

---

2. 检索算法：二分查找 (Binary Search)

public class BinarySearchDemo {
    public static void main(String[] args) {
        System.out.println("=== Java Arrays.binarySearch ===");
        int[] arr = {10, 20, 30, 40, 50};
        int idx = java.util.Arrays.binarySearch(arr, 30);
        if (idx != 2) throw new RuntimeException("Search failed");

        System.out.println("Binary search index for 30: " + idx);
        System.out.println("Java Binary Search tests passed successfully.");
    }
}

🐳 Docker Verified📋eclipse-temurin:21-jdk-alpine

Exit Code: 0

=== Java Arrays.binarySearch ===
Binary search index for 30: 2
Java Binary Search tests passed successfully.

---

3. 图论算法：广度优先遍历 (BFS)

import java.util.*;

public class BfsDemo {
    public static void main(String[] args) {
        System.out.println("=== Java Graph BFS Traversal ===");
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(3));
        graph.put(2, Arrays.asList(4));
        graph.put(3, Collections.emptyList());
        graph.put(4, Collections.emptyList());

        List<Integer> order = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        q.offer(0);
        visited.add(0);

        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int v : graph.getOrDefault(u, Collections.emptyList())) {
                if (!visited.contains(v)) {
                    visited.add(v);
                    q.offer(v);
                }
            }
        }

        if (order.size() != 5) throw new RuntimeException("BFS traversal count failed");
        System.out.println("BFS Traversal Order: " + order);
        System.out.println("Java Graph BFS tests passed successfully.");
    }
}

🐳 Docker Verified📋eclipse-temurin:21-jdk-alpine

Exit Code: 0

=== Java Graph BFS Traversal ===
BFS Traversal Order: [0, 1, 2, 3, 4]
Java Graph BFS tests passed successfully.

---

4. 动态规划：0/1 背包问题

public class KnapsackDemo {
    public static int knapsack(int W, int[] weights, int[] values) {
        int[] dp = new int[W + 1];
        for (int i = 0; i < weights.length; i++) {
            for (int w = W; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        System.out.println("=== Java 0/1 Knapsack DP ===");
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int maxVal = knapsack(5, weights, values);

        if (maxVal != 7) throw new RuntimeException("Knapsack assertion failed");
        System.out.println("Max Knapsack Value: " + maxVal);
        System.out.println("Java Knapsack DP tests passed successfully.");
    }
}

🐳 Docker Verified📋eclipse-temurin:21-jdk-alpine

Exit Code: 0

=== Java 0/1 Knapsack DP ===
Max Knapsack Value: 7
Java Knapsack DP tests passed successfully.