Java常用的算法有哪些
发布时间：2022-03-17 15:53:12
来源：亿速云
阅读：286
作者：iii
栏目：大数据
Java常用的算法有哪些
目录
引言
排序算法
冒泡排序
选择排序
插入排序
快速排序
归并排序
堆排序
希尔排序
基数排序
查找算法
线性查找
二分查找
插值查找
哈希查找
图算法
深度优先搜索
广度优先搜索
Dijkstra算法
Floyd-Warshall算法
Prim算法
Kruskal算法
动态规划
背包问题
最长公共子序列
最短路径问题
分治算法
归并排序
快速排序
大整数乘法
贪心算法
活动选择问题
霍夫曼编码
回溯算法
八皇后问题
0-1背包问题
字符串匹配算法
朴素字符串匹配
KMP算法
Boyer-Moore算法
Rabin-Karp算法
总结
引言
在计算机科学中，算法是解决问题的一系列步骤或规则。Java作为一种广泛使用的编程语言，提供了丰富的算法库和工具，使得开发者能够高效地实现各种算法。本文将详细介绍Java中常用的算法，包括排序算法、查找算法、图算法、动态规划、分治算法、贪心算法、回溯算法和字符串匹配算法等。
排序算法
冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素并交换它们的位置，直到列表有序。
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;
}
}
}
}
选择排序
选择排序是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
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;
}
}
插入排序
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
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;
}
}
快速排序
快速排序是一种高效的排序算法，采用分治法策略。它通过选择一个“基准”元素，将数组分为两部分，一部分比基准小，另一部分比基准大，然后递归地对这两部分进行排序。
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;
}
归并排序
归并排序是一种稳定的排序算法，采用分治法策略。它将数组分成两半，分别对两半进行排序，然后将排序后的两半合并。
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++;
}
}
堆排序
堆排序是一种基于二叉堆数据结构的排序算法。它首先将数组构建成一个最大堆，然后将堆顶元素（最大值）与堆的最后一个元素交换，再调整堆，重复这个过程直到数组有序。
public void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
private void heapify(int[] arr, int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
希尔排序
希尔排序是插入排序的一种高效版本，也称为缩小增量排序。它通过将数组分成若干个子序列，分别进行插入排序，然后逐步缩小子序列的间隔，最终完成排序。
public void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
基数排序
基数排序是一种非比较型整数排序算法，它通过将整数按位数切割成不同的数字，然后按每个位数分别比较。
public void radixSort(int[] arr) {
int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10)
countSort(arr, exp);
}
private int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
private void countSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
查找算法
线性查找
线性查找是一种简单的查找算法，它从列表的第一个元素开始，逐个检查每个元素，直到找到目标元素或遍历完整个列表。
public int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
二分查找
二分查找是一种高效的查找算法，适用于已排序的数组。它通过将数组分成两半，比较中间元素与目标元素，逐步缩小查找范围，直到找到目标元素或确定目标元素不存在。
public int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
插值查找
插值查找是二分查找的改进版本，适用于均匀分布的数组。它通过计算目标元素在数组中的大致位置，从而更快地缩小查找范围。
public int interpolationSearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
if (arr[pos] == target) {
return pos;
}
if (arr[pos] < target) {
low = pos + 1;
} else {
high = pos - 1;
}
}
return -1;
}
哈希查找
哈希查找是一种基于哈希表的查找算法，它通过哈希函数将键映射到哈希表中的位置，从而实现快速查找。
import java.util.HashMap;
public int hashSearch(HashMap
return map.getOrDefault(target, -1);
}
图算法
深度优先搜索
深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。它从起始节点开始，沿着一条路径尽可能深地搜索，直到到达叶子节点或无法继续前进，然后回溯并继续搜索其他路径。
import java.util.*;
public void dfs(Map
Set
Stack
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited.contains(node)) {
visited.add(node);
System.out.println(node);
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
}
广度优先搜索
广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。它从起始节点开始，逐层扩展搜索，直到找到目标节点或遍历完整个图。
import java.util.*;
public void bfs(Map
Set
Queue
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
if (!visited.contains(node)) {
visited.add(node);
System.out.println(node);
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
queue.add(neighbor);
}
}
}
}
}
Dijkstra算法
Dijkstra算法是一种用于计算单源最短路径的算法，适用于带权图。它通过贪心策略逐步找到从起始节点到其他所有节点的最短路径。
import java.util.*;
public void dijkstra(int[][] graph, int start) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue
pq.add(start);
while (!pq.isEmpty()) {
int u = pq.poll();
for (int v = 0; v < n; v++) {
if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pq.add(v);
}
}
}
System.out.println(Arrays.toString(dist));
}
Floyd-Warshall算法
Floyd-Warshall算法是一种用于计算所有节点对之间最短路径的算法，适用于带权图。它通过动态规划策略逐步更新最短路径。
public void floydWarshall(int[][] graph) {
int n = graph.length;
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
&& dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
for (int i = 0; i < n; i++) {
System.out.println(Arrays.toString(dist[i]));
}
}
Prim算法
Prim算法是一种用于求解最小生成树的算法。它从任意一个节点开始，逐步扩展生成树，每次选择一条权值最小的边连接到生成树中。
import java.util.*;
public void prim(int[][] graph) {
int n = graph.length;
int[] parent = new int[n];
int[] key = new int[n];
boolean[] mstSet = new boolean[n];
Arrays.fill(key, Integer.MAX_VALUE);
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < n - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < n; v++) {
if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printMST(parent, graph);
}
private int minKey(int[] key, boolean[] mstSet) {
int min = Integer.MAX_VALUE, minIndex = -1;
for (int v = 0; v < key.length; v++) {
if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
private void printMST(int[] parent, int[][] graph) {
System.out.println("Edge \tWeight");
for (int i = 1; i < parent.length; i++) {
System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
}
}
Kruskal算法
Kruskal算法是一种用于求解最小生成树的算法。它通过将所有边按权值排序，逐步选择权值最小的边，并确保不形成环，直到生成树包含所有节点。
”`java
import java.util.*;
public void kruskal(int[][] graph) {
int n