Java常用算法

一、排序算法

排序算法是計算機科學中最基礎的算法之一，用于將一組數據按照特定順序排列。

1.1 冒泡排序（Bubble Sort）

通過重復遍歷列表，比較相鄰元素并交換位置，直到列表有序。
時間復雜度：O(n2)。

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

1.2 選擇排序（Selection Sort）

每次從未排序部分選擇最小元素，放到已排序部分的末尾。
時間復雜度：O(n2)。

public void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {int minIndex = i;for (int j = i+1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}
}

1.3 插入排序（Insertion Sort）

將未排序部分的元素逐個插入到已排序部分的適當位置。
時間復雜度：O(n2)。

public void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j = j - 1;}arr[j+1] = key;}
}

1.4 快速排序（Quick Sort）

采用分治法，選擇一個基準元素，將數組分為兩部分，遞歸排序。
時間復雜度：平均 O(n log n)，最壞 O(n2)。

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

1.5 歸并排序（Merge Sort）

采用分治法，將數組分為兩半，分別排序后合并。
時間復雜度：O(n log n)。

public void mergeSort(int[] arr, int l, int r) {if (l < r) {int m = (l + r) / 2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);}
}private void merge(int[] arr, int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;int[] L = new int[n1];int[] R = new int[n2];for (int i = 0; i < n1; i++) {L[i] = arr[l + i];}for (int j = 0; j < n2; j++) {R[j] = arr[m + 1 + j];}int i = 0, j = 0;int k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}

二、查找算法

查找算法用于在數據結構中查找特定元素。常見的查找算法包括：

2.1 線性查找（Linear Search）

逐個檢查每個元素，直到找到目標元素。
時間復雜度：O(n)。

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

2.2 二分查找（Binary Search）

適用于已排序的數組，通過重復將搜索范圍減半來查找目標元素。
時間復雜度：O(log n)。

public 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 深度優先搜索（DFS）

從起始節點開始，沿著一條路徑盡可能深入，直到無法繼續為止，然后回溯。

public void dfs(int[][] graph, int start, boolean[] visited) {visited[start] = true;System.out.print(start + " ");for (int i = 0; i < graph[start].length; i++) {int next = graph[start][i];if (!visited[next]) {dfs(graph, next, visited);}}
}

3.2 廣度優先搜索（BFS）

從起始節點開始，逐層遍歷所有相鄰節點。

public void bfs(int[][] graph, int start) {boolean[] visited = new boolean[graph.length];Queue<Integer> queue = new LinkedList<>();visited[start] = true;queue.add(start);while (!queue.isEmpty()) {int node = queue.poll();System.out.print(node + " ");for (int i = 0; i < graph[node].length; i++) {int next = graph[node][i];if (!visited[next]) {visited[next] = true;queue.add(next);}}}
}

3.3 Dijkstra 算法

用于計算單源最短路徑，適用于加權圖。

public void dijkstra(int[][] graph, int start) {int n = graph.length;int[] dist = new int[n];boolean[] visited = new boolean[n];Arrays.fill(dist, Integer.MAX_VALUE);dist[start] = 0;for (int i = 0; i < n-1; i++) {int u = minDistance(dist, visited);visited[u] = true;for (int v = 0; v < n; v++) {if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v];}}}printSolution(dist);
}private int minDistance(int[] dist, boolean[] visited) {int min = Integer.MAX_VALUE, minIndex = -1;for (int i = 0; i < dist.length; i++) {if (!visited[i] && dist[i] <= min) {min = dist[i];minIndex = i;}}return minIndex;
}private void printSolution(int[] dist) {System.out.println("Vertex \t Distance from Source");for (int i = 0; i < dist.length; i++) {System.out.println(i + " \t\t " + dist[i]);}
}

四、動態規劃

動態規劃用于解決具有重疊子問題和最優子結構性質的問題。常見的動態規劃問題包括：

4.1 斐波那契數列

使用動態規劃計算斐波那契數列的第 n 項。

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

4.2 背包問題

解決 0-1 背包問題，即在給定容量下選擇物品使總價值最大。

public 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 j = 0; j <= capacity; j++) {if (weights[i-1] <= j) {dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);} else {dp[i][j] = dp[i-1][j];}}}return dp[n][capacity];
}

五、貪心算法

貪心算法在每一步選擇中都采取當前狀態下最優的選擇，希望導致全局最優解。常見的貪心算法問題包括：

5.1 活動選擇問題

選擇最大數量的互不重疊的活動。

public int activitySelection(int[] start, int[] end) {Arrays.sort(end);int count = 1;int lastEnd = end[0];for (int i = 1; i < end.length; i++) {if (start[i] >= lastEnd) {count++;lastEnd = end[i];}}return count;
}

六、回溯算法

回溯算法通過嘗試所有可能的解來解決問題，通常用于組合、排列等問題。常見的回溯算法問題包括：

6.1 N 皇后問題

在 N×N 棋盤上放置 N 個皇后，使其互不攻擊。

public void solveNQueens(int n) {int[] queens = new int[n];Arrays.fill(queens, -1);backtrack(queens, 0, n);
}private void backtrack(int[] queens, int row, int n) {if (row == n) {printQueens(queens);return;}for (int col = 0; col < n; col++) {if (isSafe(queens, row, col)) {queens[row] = col;backtrack(queens, row+1, n);queens[row] = -1;}}
}private boolean isSafe(int[] queens, int row, int col) {for (int i = 0; i < row; i++) {if (queens[i] == col || Math.abs(queens[i] - col) == Math.abs(i - row)) {return false;}}return true;
}private void printQueens(int[] queens) {for (int i = 0; i < queens.length; i++) {for (int j = 0; j < queens.length; j++) {if (queens[i] == j) {System.out.print("Q ");} else {System.out.print(". ");}}System.out.println();}System.out.println();
}

七、字符串匹配算法

字符串匹配算法用于在文本中查找特定模式的子串。常見的字符串匹配算法包括：

7.1 KMP 算法

通過預處理模式串，避免不必要的比較。

public int kmpSearch(String text, String pattern) {int[] lps = computeLPSArray(pattern);int i = 0, j = 0;while (i < text.length()) {if (pattern.charAt(j) == text.charAt(i)) {i++;j++;}if (j == pattern.length()) {return i - j;} else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {if (j != 0) {j = lps[j-1];} else {i++;}}}return -1;
}private int[] computeLPSArray(String pattern) {int[] lps = new int[pattern.length()];int len = 0, i = 1;while (i < pattern.length()) {if (pattern.charAt(i) == pattern.charAt(len)) {len++;lps[i] = len;i++;} else {if (len != 0) {len = lps[len-1];} else {lps[i] = len;i++;}}}return lps;
}

八、數論算法

數論算法用于解決與整數相關的數學問題。常見的數論算法包括：

8.1 歐幾里得算法

用于計算兩個整數的最大公約數（GCD）。

public int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);
}

8.2 素數檢測

判斷一個數是否為素數。

public boolean isPrime(int n) {if (n <= 1) {return false;}for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;
}

九、位運算算法

位運算算法利用位操作來高效解決問題。常見的位運算算法包括：

9.1 計算二進制中 1 的個數

使用位運算計算一個整數的二進制表示中 1 的個數。

public int countSetBits(int n) {int count = 0;while (n > 0) {count += n & 1;n >>= 1;}return count;
}

9.2 判斷一個數是否是 2 的冪

使用位運算判斷一個數是否是 2 的冪。

public boolean isPowerOfTwo(int n) {return n > 0 && (n & (n - 1)) == 0;
}