Java開發(fā)中的常見常用算法詳解
總結
Java 作為一門工業(yè)級編程語言，其強大的標準庫和生態(tài)系統(tǒng)內置了大量高效、穩(wěn)定的算法。同時，理解并能夠實現經典算法是程序員的核心能力。本文將從 “直接用” 和 “自己寫” 兩個維度，系統(tǒng)梳理 Java 開發(fā)中的常見算法。
第一部分：開箱即用 — JDK 內置算法
Java 標準庫 (java.util 和 java.util.Arrays) 提供了許多現成的算法，它們經過高度優(yōu)化和嚴格測試，是日常開發(fā)的首選。
1. 排序算法 (Sorting)
核心類： java.util.Collections, java.util.Arrays
Collections.sort(List<T> list)用途： 對
List集合（如ArrayList,LinkedList) 進行升序排序。底層實現： 對于對象集合，它使用一種優(yōu)化的、穩(wěn)定的歸并排序變體 (TimSort)。穩(wěn)定性意味著相等元素的相對順序在排序后保持不變。
時間復雜度： 保證 O(n log n)。
Arrays.sort(int[] a)用途： 對基本類型數組（如
int[],double[]) 進行排序。底層實現： 使用雙軸快速排序 (Dual-Pivot Quicksort)。該算法是對經典快排的改進，在實踐中效率極高。
Arrays.sort(T[] a)用途： 對對象數組（如
String[],Integer[]) 進行排序。底層實現： 同樣使用 TimSort 算法，保證穩(wěn)定性和高性能。
示例代碼：
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. 自定義排序規(guī)則（使用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); // 輸出: 33. 洗牌、填充與工具算法
核心類： 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 提供了強大的工具，但許多算法思想需要開發(fā)者自己實現來解決特定問題。
1. 排序與搜索基礎
理解這些基礎算法的實現有助于深入理解算法思想。
冒泡排序 (Bubble Sort)
思想： 重復遍歷列表，比較相鄰元素，如果順序錯誤就交換它們。
復雜度： O(n²)。（僅用于教學，實際開發(fā)切勿使用?。?/strong>
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)。適用于小規(guī)模或未排序的數據。
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);
}
// 使用動態(tài)規(guī)劃（迭代+記憶化，高效）
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. 或創(chuàng)建一個 Node 類
class GraphNode {
int val;
List<GraphNode> neighbors;
GraphNode(int x) { val = x; neighbors = new ArrayList<>(); }
}
// 使用二維數組（鄰接矩陣）表示帶權圖
int[][] graphMatrix;廣度優(yōu)先搜索 (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. 動態(tài)規(guī)劃 (Dynamic Programming)
通過存儲子問題的解來避免重復計算，從而高效解決復雜問題。
經典案例：爬樓梯問題
問題： 每次可以爬 1 或 2 個臺階，爬到 n 階有多少種不同方法？
狀態(tài)轉移方程：
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];
}
// 可以進一步優(yōu)化空間復雜度到 O(1)，只保留前兩個狀態(tài)總結與實踐建議
| 場景 | 推薦做法 |
|---|---|
| 對集合/數組排序 | 永遠優(yōu)先使用 Collections.sort() 或 Arrays.sort()。 |
| 在有序數據中查找 | 使用 binarySearch()。 |
| 需要隨機順序 | 使用 Collections.shuffle()。 |
| 解決特定領域問題 (如最短路徑、背包問題) | 1. 首先尋找優(yōu)秀的第三方庫 (如 JGraphT for 圖算法)。 2. 其次再考慮自己實現經典算法。 |
| 面試與學習 | 必須掌握如何從零實現各類經典算法 (快排、歸并、BFS/DFS、DP等)。 |
| 性能優(yōu)化 | 理解算法復雜度 (Big O)，這是選擇合適算法和數據結構的根本依據。 |
核心思想：
不要重復造輪子。 在日常業(yè)務開發(fā)中，最大限度地利用 JDK 和成熟第三方庫提供的穩(wěn)定高效的算法實現。你的精力應該集中在正確地建模業(yè)務問題和選擇最合適的工具（算法/數據結構） 上，而不是重新實現一個可能更差的排序算法。然而，深入理解這些輪子是如何造出來的，是你在遇到復雜問題、需要進行底層優(yōu)化或通過技術面試時的必備能力。
到此這篇關于Java開發(fā)中的常見常用算法詳解的文章就介紹到這了,更多相關Java常見算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
在本文里小編給大家整理了關于java數據結構和算法中數組的簡單入門知識點整理，需要的朋友們學習下。2019-06-06
本文將基于Spring Boot介紹兩種生成二維碼的實現方式，一種是基于Google開發(fā)工具包，另一種是基于Hutool來實現，下面我們將基于Spring Boot，并采用兩種方式實現二維碼的生成，對于每一種方式還提供兩種類型的二維碼返回形式,需要的朋友可以參考下2023-09-09
這篇文章主要為大家詳細介紹了Spring實現默認標簽解析流程，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
在使用SpringBoot進行開發(fā)時，我們經常需要對Spring容器的生命周期進行了解和掌握，本文將介紹SpringBoot容器的生命周期，包括容器的創(chuàng)建、初始化、銷毀等過程，并提供相應的代碼示例2023-06-06
這篇文章主要介紹了Java編程實現的模擬行星運動,涉及java基于swing組建繪制動態(tài)效果及數值運算相關操作技巧,并總結分析了java面向對象的相關特性,需要的朋友可以參考下2018-04-04
在日常的開發(fā)過程中,為了提高代碼的可靠性和健壯性,同時也是檢測代碼的質量,減少測試環(huán)節(jié)的問題,會對完成的業(yè)務功能代碼編寫單元測試,在本文中,將分享一些單元測試的實踐和心得,需要的朋友可以參考下2023-11-11
RocketMQ生產者一個應用不能發(fā)送多個NameServer消息解決
這篇文章主要為大家介紹了RocketMQ生產者一個應用不能發(fā)送多個NameServer消息原因及解決方法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-11-11
解決springboot項目找不到resources目錄下的資源問題
這篇文章主要介紹了解決springboot項目找不到resources目錄下的資源問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
這篇文章主要為大家詳細介紹了java實現順時針打印矩陣的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03
這篇文章主要為大家詳細介紹了Java OpenCV實現圖像鏡像翻轉效果，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-07-07