您现在的位置是：首页 >技术杂谈 >Java中令人惊艳的五大算法，你知道多少？网站首页技术杂谈
Java中令人惊艳的五大算法，你知道多少？
✅作者简介：2022年博客新星 第八。热爱国学的Java后端开发者，修心和技术同步精进。
?个人主页：Java Fans的博客
?个人信条：不迁怒，不贰过。小知识，大智慧。
?当前专栏：前端案例分享专栏
✨特色专栏：国学周更-心性养成之路
?本文内容：Java中令人惊艳的五大算法，你知道多少？
1、快速排序算法
这是一种高效的排序算法，它的平均时间复杂度为O(nlogn)。它的基本思想是通过分治的方式将一个大问题分解成若干个小问题，然后递归地解决这些小问题。
具体来说，快速排序算法的实现过程如下：
- 选择一个基准元素，通常选择第一个元素或者最后一个元素。
- 将数组中小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边。
- 对左右两个子数组分别递归地进行快速排序。
- 合并左右两个子数组。
Java中实现快速排序算法的代码如下：
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && arr[i] < pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
int temp = arr[left];
arr[left] = arr[j];
arr[j] = temp;
return j;
}
在这段代码中，partition方法用来将数组分成左右两个子数组，并返回基准元素的位置。quickSort方法则用来递归地进行快速排序。
2、哈希表算法
哈希表是一种高效的数据结构，它可以在常数时间内完成插入、查找和删除操作。它的基本思想是将关键字映射到一个固定的位置，然后在该位置上存储相应的值。
具体来说，哈希表算法的实现过程如下：
- 定义一个哈希函数，将关键字映射到一个固定的位置。
- 在哈希表中查找或插入元素时，先通过哈希函数计算出关键字对应的位置。
- 如果该位置上已经有元素，则进行冲突处理，通常采用链表或开放地址法。
- 如果该位置上没有元素，则直接插入元素。
Java中实现哈希表算法的代码如下：
public class MyHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private Entry<K, V>[] table;
private int size;
private int capacity;
private float loadFactor;
public MyHashMap() {
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public MyHashMap(int capacity, float loadFactor) {
this.capacity = capacity;
this.loadFactor = loadFactor;
this.table = new Entry[capacity];
}
public void put(K key, V value) {
int index = hash(key);
Entry<K, V> entry = table[index];
while (entry != null) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
entry = entry.next;
}
Entry<K, V> newEntry = new Entry<>(key, value);
newEntry.next = table[index];
table[index] = newEntry;
size++;
if (size > capacity * loadFactor) {
resize();
}
}
public V get(K key) {
int index = hash(key);
Entry<K, V> entry = table[index];
while (entry != null) {
if (entry.key.equals(key)) {
return entry.value;
}
entry = entry.next;
}
return null;
}
private int hash(K key) {
return key.hashCode() % capacity;
}
private void resize() {
Entry<K, V>[] oldTable = table;
capacity *= 2;
table = new Entry[capacity];
size = 0;
for (Entry<K, V> entry : oldTable) {
while (entry != null) {
put(entry.key, entry.value);
entry = entry.next;
}
}
}
private static class Entry<K, V> {
K key;
V value;
Entry<K, V> next;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
}
在这段代码中，MyHashMap类实现了哈希表的基本操作，包括put、get、hash和resize方法。其中，put方法用来插入元素，get方法用来查找元素，hash方法用来计算哈希值，resize方法用来扩容哈希表。Entry类则用来表示哈希表中的一个键值对。
3、动态规划算法
动态规划是一种高效的算法，它可以用来解决很多复杂的问题，如最长公共子序列、最短路径等。它的基本思想是将一个大问题分解成若干个小问题，然后递归地解决这些小问题，并将它们的解合并起来得到大问题的解。
具体来说，动态规划算法的实现过程如下：
定义状态：将原问题分解成若干个子问题，定义状态表示子问题的解。定义状态转移方程：根据子问题之间的关系，定义状态转移方程，将子问题的解合并起来得到大问题的解。初始化：将最简单的子问题的解初始化。计算顺序：按照计算顺序递推计算出所有子问题的解。求解原问题：根据子问题的解，计算出原问题的解。
Java中实现动态规划算法的代码如下：
public static int longestCommonSubsequence(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
在这段代码中，longestCommonSubsequence方法用来求解两个字符串的最长公共子序列。它使用了动态规划算法，定义了状态dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子序列的长度。然后，根据子问题之间的关系，定义了状态转移方程，最后按照计算顺序递推计算出所有子问题的解，得到原问题的解。
4、KMP算法
KMP算法是一种高效的字符串匹配算法，它的时间复杂度为O(n+m)，其中n和m分别是文本串和模式串的长度。它的基本思想是利用已经匹配的信息来避免重复匹配。
具体来说，KMP算法的实现过程如下：
预处理模式串：计算出模式串的前缀函数，即next数组。在文本串中匹配模式串：从文本串的第一个字符开始，依次比较文本串和模式串的每个字符，如果匹配成功，则继续比较下一个字符，否则根据next数组移动模式串的指针。根据next数组移动模式串的指针：如果模式串的某个字符与文本串的某个字符不匹配，则根据next数组移动模式串的指针，使得模式串的前缀与文本串的后缀匹配。
Java中实现KMP算法的代码如下：
public static int kmp(String s, String p) {
int n = s.length();
int m = p.length();
int[] next = getNext(p);
int i = 0, j = 0;
while (i < n && j < m) {
if (j == -1 || s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == m) {
return i - j;
} else {
return -1;
}
}
public static int[] getNext(String p) {
int m = p.length();
int[] next = new int[m];
next[0] = -1;
int i = 0, j = -1;
while (i < m - 1) {
if (j == -1 || p.charAt(i) == p.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
在这段代码中，kmp方法用来在文本串s中匹配模式串p，getNext方法用来计算模式串的前缀函数next数组。在kmp方法中，i和j分别表示文本串和模式串的指针，如果匹配成功，则i和j都向后移动一位，否则根据next数组移动模式串的指针j。在getNext方法中，i和j分别表示前缀和后缀的指针，如果前缀和后缀匹配成功，则i和j都向后移动一位，否则根据next数组移动后缀的指针j。
5、最小生成树算法
最小生成树算法是一种用来求解无向图的最小生成树的算法，它的时间复杂度为O(nlogn)。它的基本思想是通过贪心的方式选择边，使得生成树的权值最小。
具体来说，最小生成树算法的实现过程如下：
初始化：将所有边按照权值从小到大排序。选择边：从权值最小的边开始，依次选择边，如果该边的两个端点不在同一个连通分量中，则将它们合并成一个连通分量，并将该边加入生成树中。终止条件：当生成树中有n-1条边时，停止选择边。
Java中实现最小生成树算法的代码如下：
public static List<Edge> kruskal(int n, List<Edge> edges) {
List<Edge> result = new ArrayList<>();
UnionFind uf = new UnionFind(n);
Collections.sort(edges);
for (Edge edge : edges) {
int u = edge.u;
int v = edge.v;
if (uf.find(u) != uf.find(v)) {
uf.union(u, v);
result.add(edge);
if (result.size() == n - 1) {
break;
}
}
}
return result;
}
public static class Edge implements Comparable<Edge> {
int u;
int v;
int w;
public Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(w, o.w);
}
}
public static class UnionFind {
int[] parent;
int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) {
return;
}
if (rank[px] > rank[py]) {
parent[py] = px;
} else if (rank[px] < rank[py]) {
parent[px] = py;
} else {
parent[py] = px;
rank[px]++;
}
}
}
在这段代码中，kruskal方法用来求解无向图的最小生成树，Edge类用来表示图中的一条边，UnionFind类用来实现并查集。在kruskal方法中，首先将所有边按照权值从小到大排序，然后依次选择边，如果该边的两个端点不在同一个连通分量中，则将它们合并成一个连通分量，并将该边加入生成树中。最后，当生成树中有n-1条边时，停止选择边。
码文不易，本篇文章就介绍到这里，如果想要学习更多Java系列知识，点击关注博主，博主带你零基础学习Java知识。与此同时，对于日常生活有困扰的朋友，欢迎阅读我的第四栏目：《国学周更—心性养成之路》，学习技术的同时，我们也注重了心性的养成。
站长推荐
- stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述