Java 常见常用算法详解

文章配图

第一部分：开箱即用 — JDK 内置算法

Java 标准库 (java.util 和 java.util.Arrays) 提供了许多现成的算法，它们经过高度优化和严格测试，是日常开发的首选。

1. 排序算法 (Sorting)

核心类： java.util.Collections, java.util.Arrays

Collections.sort(List<T> list)
- 用途： 对 List 集合（如 ArrayList, LinkedList) 进行升序排序。
- 底层实现： 对于对象集合，它使用一种优化的、稳定的归并排序变体 (TimSort)。稳定性意味着相等元素的相对顺序在排序后保持不变。
- 时间复杂度： 保证 O(n log n)。
Arrays.sort(int[] a)
- 用途： 对基本类型数组（如 int[], double[]) 进行排序。
- 底层实现： 使用双轴快速排序 (Dual-Pivot Quicksort)。该算法是对经典快排的改进，在实践中效率极高。
Arrays.sort(T[] a)
- 用途： 对对象数组（如 String[], Integer[]) 进行排序。
- 底层实现： 同样使用 TimSort 算法，保证稳定性和高性能。

示例代码：

import java.util.*;

// 1. 对 List 排序
List<Integer> numbersList = new ArrayList<>(Arrays.asList(23, 5, 42, -1, 99));
Collections.sort(numbersList);
System.out.println("Sorted List: " + numbersList); // 输出：Sorted List: [-1, 5, 23, 42, 99]

// 2. 对数组排序
int[] numbersArray = {23, 5, 42, -1, 99};
Arrays.sort(numbersArray);
System.out.println("Sorted Array: " + Arrays.toString(numbersArray)); // 输出：Sorted Array: [-1, 5, 23, 42, 99]

// 3. 自定义排序规则（使用 Comparator）
List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "David");
// 按字符串长度排序
Collections.sort(names, (a, b) -> a.length() - b.length());
// 或使用方法引用：Collections.sort(names, Comparator.comparingInt(String::length));
System.out.println("Sorted by length: " + names); // 输出：Sorted by length: [Bob, Alice, David, Charlie]

2. 搜索算法 (Searching)

核心类： java.util.Collections, java.util.Arrays

Collections.binarySearch(List, Key) / Arrays.binarySearch(array, key)
- 用途： 在已排序的列表或数组中，使用二分查找算法快速定位元素。
- 重要前提： 集合或数组必须是有序的（通常是升序），否则结果不可预测。
- 返回值： 如果找到，返回元素的索引；如果未找到，返回一个负值，表示应插入的位置 (-(insertion point) - 1)。
- 时间复杂度： O(log n)。

示例代码：

List<Integer> sortedList = Arrays.asList(10, 20, 30, 40, 50);
int index1 = Collections.binarySearch(sortedList, 30);
System.out.println("Index of 30: " + index1); // 输出：2 (找到了)

int index2 = Collections.binarySearch(sortedList, 25);
System.out.println("Index of 25: " + index2); // 输出：-3 (未找到。插入点应为 2, 所以返回 -2-1 = -3)

int[] sortedArray = {10, 20, 30, 40, 50};
int index3 = Arrays.binarySearch(sortedArray, 40);
System.out.println("Index of 40 in array: " + index3); // 输出：3

3. 洗牌、填充与工具算法

核心类： java.util.Collections

Collections.shuffle(List)
- 用途： 随机打乱列表中元素的顺序（洗牌）。
- 底层实现： 使用 Fisher-Yates shuffle 算法的高效变体，能产生均匀的随机排列。
Collections.reverse(List): 反转列表。
Collections.fill(List, obj): 用指定对象填充列表的所有元素。
Collections.copy(destList, srcList): 复制列表。
Collections.max(Collection) / Collections.min(Collection): 根据自然顺序查找最大/最小元素。
Collections.frequency(Collection, Object): 计算某元素出现的频率。

示例代码：

List<Integer> cards = new ArrayList<>();
for (int i = 1; i <= 10; i++) {
    cards.add(i);
}
System.out.println("Original deck: " + cards);
Collections.shuffle(cards);
System.out.println("Shuffled deck: " + cards);

// 其他工具方法
Collections.reverse(cards);
System.out.println("Reversed deck: " + cards);
int max = Collections.max(cards);
int frequencyOfFive = Collections.frequency(cards, 5);
System.out.println("Max card: " + max + ", Frequency of 5: " + frequencyOfFive);

第二部分：核心基础 — 需要掌握的经典算法

虽然 JDK 提供了强大的工具，但许多算法思想需要开发者自己实现来解决特定问题。

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]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

线性搜索 (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. 递归与分治 (Recursion & Divide and Conquer)

许多高效算法基于此思想。

经典案例：斐波那契数列 (Fibonacci Sequence)
- 问题： F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)。

// 简单递归（效率极低，存在大量重复计算）
public static int fibonacciRecursive(int n) {
    if (n <= 1) return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// 使用动态规划（迭代 + 记忆化，高效）
public static int fibonacciDP(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];
}

3. 图算法 (Graph Algorithms)

Java 标准库没有图结构，需要自行建模（使用邻接表或邻接矩阵）并实现算法。

图的表示：

// 使用邻接表（最常用）
// 1. 使用 Map 和 List
Map<Integer, List<Integer>> graph = new HashMap<>();

// 2. 或创建一个 Node 类
class GraphNode {
    int val;
    List<GraphNode> neighbors;
    GraphNode(int x) {
        val = x;
        neighbors = new ArrayList<>();
    }
}

// 使用二维数组（邻接矩阵）表示带权图
int[][] graphMatrix;

广度优先搜索 (BFS) - 寻找最短路径（无权图）
- 思想： 层层扩散，使用队列辅助。

public int bfsShortestPath(Map<Integer, List<Integer>> graph, int start, int end) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    Map<Integer, Integer> distance = new HashMap<>(); // 记录到起点的距离
    
    queue.offer(start);
    visited.add(start);
    distance.put(start, 0);
    
    while (!queue.isEmpty()) {
        int currentNode = queue.poll();
        if (currentNode == end) {
            return distance.get(currentNode);
        }
        for (int neighbor : graph.getOrDefault(currentNode, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
                distance.put(neighbor, distance.get(currentNode) + 1);
            }
        }
    }
    return -1; // 未找到路径
}

4. 动态规划 (Dynamic Programming)

通过存储子问题的解来避免重复计算，从而高效解决复杂问题。

经典案例：爬楼梯问题
- 问题： 每次可以爬 1 或 2 个台阶，爬到 n 阶有多少种不同方法？
- 状态转移方程： dp[i] = dp[i-1] + dp[i-2]

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// 可以进一步优化空间复杂度到 O(1)，只保留前两个状态

总结与实践建议

场景	推荐做法
对集合/数组排序	永远优先使用 `Collections.sort()` 或 `Arrays.sort()`。
在有序数据中查找	使用 `binarySearch()`。
需要随机顺序	使用 `Collections.shuffle()`。
解决特定领域问题 (如最短路径、背包问题)	1. 首先寻找优秀的第三方库 (如 JGraphT for 图算法)。\n2. 其次再考虑自己实现经典算法。
面试与学习	必须掌握如何从零实现各类经典算法 (快排、归并、BFS/DFS、DP 等)。
性能优化	理解算法复杂度 (Big O)，这是选择合适算法和数据结构的根本依据。

核心思想：

不要重复造轮子。 在日常业务开发中，最大限度地利用 JDK 和成熟第三方库提供的稳定高效的算法实现。你的精力应该集中在正确地建模业务问题和选择最合适的工具（算法/数据结构） 上，而不是重新实现一个可能更差的排序算法。然而，深入理解这些轮子是如何造出来的，是你在遇到复杂问题、需要进行底层优化或通过技术面试时的必备能力。

文章配图

第一部分：开箱即用 — JDK 内置算法

Java 标准库 (java.util 和 java.util.Arrays) 提供了许多现成的算法，它们经过高度优化和严格测试，是日常开发的首选。

1. 排序算法 (Sorting)

核心类： java.util.Collections, java.util.Arrays

Collections.sort(List<T> list)
- 用途： 对 List 集合（如 ArrayList, LinkedList) 进行升序排序。
- 底层实现： 对于对象集合，它使用一种优化的、稳定的归并排序变体 (TimSort)。稳定性意味着相等元素的相对顺序在排序后保持不变。
- 时间复杂度： 保证 O(n log n)。
Arrays.sort(int[] a)
- 用途： 对基本类型数组（如 int[], double[]) 进行排序。
- 底层实现： 使用双轴快速排序 (Dual-Pivot Quicksort)。该算法是对经典快排的改进，在实践中效率极高。
Arrays.sort(T[] a)
- 用途： 对对象数组（如 String[], Integer[]) 进行排序。
- 底层实现： 同样使用 TimSort 算法，保证稳定性和高性能。

示例代码：

import java.util.*;

// 1. 对 List 排序
List<Integer> numbersList = new ArrayList<>(Arrays.asList(23, 5, 42, -1, 99));
Collections.sort(numbersList);
System.out.println("Sorted List: " + numbersList); // 输出：Sorted List: [-1, 5, 23, 42, 99]

// 2. 对数组排序
int[] numbersArray = {23, 5, 42, -1, 99};
Arrays.sort(numbersArray);
System.out.println("Sorted Array: " + Arrays.toString(numbersArray)); // 输出：Sorted Array: [-1, 5, 23, 42, 99]

// 3. 自定义排序规则（使用 Comparator）
List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "David");
// 按字符串长度排序
Collections.sort(names, (a, b) -> a.length() - b.length());
// 或使用方法引用：Collections.sort(names, Comparator.comparingInt(String::length));
System.out.println("Sorted by length: " + names); // 输出：Sorted by length: [Bob, Alice, David, Charlie]

2. 搜索算法 (Searching)

核心类： java.util.Collections, java.util.Arrays

Collections.binarySearch(List, Key) / Arrays.binarySearch(array, key)
- 用途： 在已排序的列表或数组中，使用二分查找算法快速定位元素。
- 重要前提： 集合或数组必须是有序的（通常是升序），否则结果不可预测。
- 返回值： 如果找到，返回元素的索引；如果未找到，返回一个负值，表示应插入的位置 (-(insertion point) - 1)。
- 时间复杂度： O(log n)。

示例代码：

List<Integer> sortedList = Arrays.asList(10, 20, 30, 40, 50);
int index1 = Collections.binarySearch(sortedList, 30);
System.out.println("Index of 30: " + index1); // 输出：2 (找到了)

int index2 = Collections.binarySearch(sortedList, 25);
System.out.println("Index of 25: " + index2); // 输出：-3 (未找到。插入点应为 2, 所以返回 -2-1 = -3)

int[] sortedArray = {10, 20, 30, 40, 50};
int index3 = Arrays.binarySearch(sortedArray, 40);
System.out.println("Index of 40 in array: " + index3); // 输出：3

3. 洗牌、填充与工具算法

核心类： java.util.Collections

Collections.shuffle(List)
- 用途： 随机打乱列表中元素的顺序（洗牌）。
- 底层实现： 使用 Fisher-Yates shuffle 算法的高效变体，能产生均匀的随机排列。
Collections.reverse(List): 反转列表。
Collections.fill(List, obj): 用指定对象填充列表的所有元素。
Collections.copy(destList, srcList): 复制列表。
Collections.max(Collection) / Collections.min(Collection): 根据自然顺序查找最大/最小元素。
Collections.frequency(Collection, Object): 计算某元素出现的频率。

示例代码：

List<Integer> cards = new ArrayList<>();
for (int i = 1; i <= 10; i++) {
    cards.add(i);
}
System.out.println("Original deck: " + cards);
Collections.shuffle(cards);
System.out.println("Shuffled deck: " + cards);

// 其他工具方法
Collections.reverse(cards);
System.out.println("Reversed deck: " + cards);
int max = Collections.max(cards);
int frequencyOfFive = Collections.frequency(cards, 5);
System.out.println("Max card: " + max + ", Frequency of 5: " + frequencyOfFive);

第二部分：核心基础 — 需要掌握的经典算法

虽然 JDK 提供了强大的工具，但许多算法思想需要开发者自己实现来解决特定问题。

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]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

线性搜索 (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. 递归与分治 (Recursion & Divide and Conquer)

许多高效算法基于此思想。

经典案例：斐波那契数列 (Fibonacci Sequence)
- 问题： F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)。

// 简单递归（效率极低，存在大量重复计算）
public static int fibonacciRecursive(int n) {
    if (n <= 1) return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// 使用动态规划（迭代 + 记忆化，高效）
public static int fibonacciDP(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];
}

3. 图算法 (Graph Algorithms)

Java 标准库没有图结构，需要自行建模（使用邻接表或邻接矩阵）并实现算法。

图的表示：

// 使用邻接表（最常用）
// 1. 使用 Map 和 List
Map<Integer, List<Integer>> graph = new HashMap<>();

// 2. 或创建一个 Node 类
class GraphNode {
    int val;
    List<GraphNode> neighbors;
    GraphNode(int x) {
        val = x;
        neighbors = new ArrayList<>();
    }
}

// 使用二维数组（邻接矩阵）表示带权图
int[][] graphMatrix;

广度优先搜索 (BFS) - 寻找最短路径（无权图）
- 思想： 层层扩散，使用队列辅助。

public int bfsShortestPath(Map<Integer, List<Integer>> graph, int start, int end) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    Map<Integer, Integer> distance = new HashMap<>(); // 记录到起点的距离
    
    queue.offer(start);
    visited.add(start);
    distance.put(start, 0);
    
    while (!queue.isEmpty()) {
        int currentNode = queue.poll();
        if (currentNode == end) {
            return distance.get(currentNode);
        }
        for (int neighbor : graph.getOrDefault(currentNode, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
                distance.put(neighbor, distance.get(currentNode) + 1);
            }
        }
    }
    return -1; // 未找到路径
}

4. 动态规划 (Dynamic Programming)

通过存储子问题的解来避免重复计算，从而高效解决复杂问题。

经典案例：爬楼梯问题
- 问题： 每次可以爬 1 或 2 个台阶，爬到 n 阶有多少种不同方法？
- 状态转移方程： dp[i] = dp[i-1] + dp[i-2]

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// 可以进一步优化空间复杂度到 O(1)，只保留前两个状态

总结与实践建议

场景	推荐做法
对集合/数组排序	永远优先使用 `Collections.sort()` 或 `Arrays.sort()`。
在有序数据中查找	使用 `binarySearch()`。
需要随机顺序	使用 `Collections.shuffle()`。
解决特定领域问题 (如最短路径、背包问题)	1. 首先寻找优秀的第三方库 (如 JGraphT for 图算法)。\n2. 其次再考虑自己实现经典算法。
面试与学习	必须掌握如何从零实现各类经典算法 (快排、归并、BFS/DFS、DP 等)。
性能优化	理解算法复杂度 (Big O)，这是选择合适算法和数据结构的根本依据。

核心思想：

不要重复造轮子。 在日常业务开发中，最大限度地利用 JDK 和成熟第三方库提供的稳定高效的算法实现。你的精力应该集中在正确地建模业务问题和选择最合适的工具（算法/数据结构） 上，而不是重新实现一个可能更差的排序算法。然而，深入理解这些轮子是如何造出来的，是你在遇到复杂问题、需要进行底层优化或通过技术面试时的必备能力。

Java 常见常用算法详解

1. 排序算法 (Sorting)

2. 搜索算法 (Searching)

3. 洗牌、填充与工具算法

第二部分：核心基础 — 需要掌握的经典算法

1. 排序与搜索基础

2. 递归与分治 (Recursion & Divide and Conquer)

3. 图算法 (Graph Algorithms)

4. 动态规划 (Dynamic Programming)

总结与实践建议

Java 常见常用算法详解

1. 排序算法 (Sorting)

2. 搜索算法 (Searching)

3. 洗牌、填充与工具算法

第二部分：核心基础 — 需要掌握的经典算法

1. 排序与搜索基础

2. 递归与分治 (Recursion & Divide and Conquer)

3. 图算法 (Graph Algorithms)

4. 动态规划 (Dynamic Programming)

总结与实践建议

更多推荐文章

相关免费在线工具

更多推荐文章

相关免费在线工具

Java 常见常用算法详解

1. 排序算法 (Sorting)

2. 搜索算法 (Searching)

3. 洗牌、填充与工具算法

第二部分：核心基础 — 需要掌握的经典算法

1. 排序与搜索基础

2. 递归与分治 (Recursion & Divide and Conquer)

3. 图算法 (Graph Algorithms)

4. 动态规划 (Dynamic Programming)

总结与实践建议

Java 常见常用算法详解

1. 排序算法 (Sorting)

2. 搜索算法 (Searching)

3. 洗牌、填充与工具算法

第二部分：核心基础 — 需要掌握的经典算法

1. 排序与搜索基础

2. 递归与分治 (Recursion & Divide and Conquer)

3. 图算法 (Graph Algorithms)

4. 动态规划 (Dynamic Programming)

总结与实践建议

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具