請關注微信公眾號：拾荒的小海螺
博客地址：http://lsk-ww.cn/
1、簡述
在軟件開發過程中，算法扮演著關鍵的角色。它們用于解決各種問題，從數據處理到搜索、排序等。本文將介紹幾種常見的算法及其 Java 實現，包括排序算法、搜索算法以及圖算法。
2、排序算法
2.1 冒泡排序（Bubble Sort）
冒泡排序是一種簡單的排序算法。它重復地遍歷待排序的數列，依次比較兩個相鄰的元素，如果它們的順序錯誤就交換它們的位置。遍歷數列的工作重復進行直到沒有相鄰元素需要交換為止。
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]) {// 交換 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[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println("排序后的數組:");for (int num : arr) {System.out.print(num + " ");}}
}
2.1 快速排序（Quick Sort）
快速排序是分治法的一種，它通過選擇一個基準元素，將數組分為兩部分，比基準小的元素放在左邊，比基準大的元素放在右邊，然后對這兩部分分別進行遞歸排序。
public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 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++;// 交換 arr[i] 和 arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 交換 arr[i+1] 和 arr[high]int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);System.out.println("排序后的數組:");for (int num : arr) {System.out.print(num + " ");}}
}
3、搜索算法（二分查找（Binary Search））
二分查找是一種高效的查找算法，適用于已經排序的數組。它通過將數組一分為二，反復縮小查找范圍來找到目標值。
public class BinarySearch {public static int binarySearch(int[] arr, int x) {int low = 0, high = arr.length - 1;while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] == x)return mid;if (arr[mid] < x)low = mid + 1;elsehigh = mid - 1;}return -1; // 未找到返回 -1}public static void main(String[] args) {int[] arr = {2, 3, 4, 10, 40};int x = 10;int result = binarySearch(arr, x);if (result == -1)System.out.println("元素未找到");elseSystem.out.println("元素在索引 " + result);}
}
4、 圖算法
4.1 深度優先搜索（Depth-First Search, DFS）
深度優先搜索是一種用于遍歷或搜索圖的算法。它從圖的某個起始節點開始，沿著一條路徑走到底，然后回溯，繼續探索新的路徑。
import java.util.*;public class GraphDFS {private int V; // 頂點個數private LinkedList<Integer> adj[]; // 鄰接表GraphDFS(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList();}void addEdge(int v, int w) {adj[v].add(w); // 添加邊}void DFSUtil(int v, boolean visited[]) {visited[v] = true;System.out.print(v + " ");Iterator<Integer> i = adj[v].listIterator();while (i.hasNext()) {int n = i.next();if (!visited[n])DFSUtil(n, visited);}}void DFS(int v) {boolean visited[] = new boolean[V];DFSUtil(v, visited);}public static void main(String args[]) {GraphDFS g = new GraphDFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("從頂點 2 開始的深度優先搜索:");g.DFS(2);}
}
4.2 廣度優先搜索（Breadth-First Search, BFS）
廣度優先搜索是一種用于遍歷或搜索圖的算法。它從圖的某個起始節點開始，首先訪問距離最近的節點，然后逐層向外擴展。
import java.util.*;public class GraphBFS {private int V; // 頂點個數private LinkedList<Integer> adj[]; // 鄰接表GraphBFS(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList();}void addEdge(int v, int w) {adj[v].add(w); // 添加邊}void BFS(int s) {boolean visited[] = new boolean[V];LinkedList<Integer> queue = new LinkedList<>();visited[s] = true;queue.add(s);while (queue.size() != 0) {s = queue.poll();System.out.print(s + " ");Iterator<Integer> i = adj[s].listIterator();while (i.hasNext()) {int n = i.next();if (!visited[n]) {visited[n] = true;queue.add(n);}}}}public static void main(String args[]) {GraphBFS g = new GraphBFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("從頂點 2 開始的廣度優先搜索:");g.BFS(2);}
}
5、總結
本文介紹了幾種常見的算法及其 Java 實現，包括冒泡排序、快速排序、二分查找、深度優先搜索和廣度優先搜索。這些算法在實際開發中非常有用，通過掌握它們，可以解決許多常見的編程問題。希望這篇文章能幫助你更好地理解和使用這些算法。
