面试系列 - Java常见算法(二)

目录

一、排序算法

1、插入排序（Insertion Sort）

2、归并排序（Merge Sort）

二、图形算法

1、最短路径算法（Dijkstra算法、Floyd-Warshall算法）

Dijkstra算法

Floyd-Warshall算法

2、最小生成树算法（Prim算法、Kruskal算法）

Prim算法

Kruskal算法

一、排序算法

1、插入排序（Insertion Sort）

插入排序（Insertion Sort）是一种简单的排序算法，它的工作原理是逐步构建有序序列。该算法每次将一个未排序的元素插入到已排序序列的适当位置，直到所有元素都被排序为止。插入排序通常是稳定的，适用于小型数据集或基本有序的数据集。

工作原理：

  1. 将第一个元素视为已排序序列。
  2. 从第二个元素开始，将其插入已排序序列的适当位置，以确保已排序序列仍然有序。
  3. 重复步骤2，直到所有元素都被插入到适当的位置，形成完全有序的序列。
public class InsertionSort {public static void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int currentElement = arr[i];int j = i - 1;// 从已排序部分的末尾开始，依次比较并移动元素while (j >= 0 && arr[j] > currentElement) {arr[j + 1] = arr[j]; // 向右移动元素j--;}// 插入当前元素到合适的位置arr[j + 1] = currentElement;}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6};insertionSort(arr);System.out.println("排序后的数组：");for (int num : arr) {System.out.print(num + " ");}}
}

 在这个Java示例中，insertionSort方法实现了插入排序算法。它遍历数组，将每个元素插入已排序部分的适当位置，以保持已排序部分的有序性。

请注意，插入排序是一个稳定的排序算法，适用于小型数据集或基本有序的数据集。然而，对于大型数据集，其时间复杂度为O(n^2)，性能相对较低，可以考虑更高效的排序算法如快速排序或归并排序。

2、归并排序（Merge Sort）

归并排序（Merge Sort）是一种分治算法，它将一个大问题分解为多个小问题，然后将这些小问题的解合并在一起以获得最终的解决方案。归并排序的主要思想是将数组分成两半，递归地对每一半进行排序，然后将两个已排序的子数组合并成一个有序的数组。它是一种稳定的排序算法，时间复杂度为O(nlogn)，适用于各种数据集大小。

public class MergeSort {public static void mergeSort(int[] arr) {if (arr == null || arr.length <= 1) {return; // 如果数组为空或只有一个元素，无需排序}// 计算中间索引int middle = arr.length / 2;// 创建左右子数组int[] left = new int[middle];int[] right = new int[arr.length - middle];// 将元素分配到左右子数组System.arraycopy(arr, 0, left, 0, middle);System.arraycopy(arr, middle, right, 0, arr.length - middle);// 递归地对左右子数组进行排序mergeSort(left);mergeSort(right);// 合并两个已排序的子数组merge(arr, left, right);}public static void merge(int[] result, int[] left, int[] right) {int i = 0, j = 0, k = 0;// 比较并合并左右子数组的元素while (i < left.length && j < right.length) {if (left[i] <= right[j]) {result[k++] = left[i++];} else {result[k++] = right[j++];}}// 处理左子数组中剩余的元素while (i < left.length) {result[k++] = left[i++];}// 处理右子数组中剩余的元素while (j < right.length) {result[k++] = right[j++];}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6, 7};mergeSort(arr);System.out.println("排序后的数组：");for (int num : arr) {System.out.print(num + " ");}}
}

 在上面的Java示例中，mergeSort方法实现了归并排序算法，它递归地将数组分为左右两半，然后合并这两个已排序的子数组。merge方法用于合并两个子数组并将其排序为一个有序数组。

 归并排序是一种高效且稳定的排序算法，适用于各种不同大小的数据集。由于其时间复杂度为O(nlogn)，它在处理大型数据集时表现出色。

二、图形算法

1、最短路径算法（Dijkstra算法、Floyd-Warshall算法）

最短路径算法用于在图中查找两个节点之间的最短路径或最短距离。在网络路由、导航系统、交通规划等领域广泛应用。以下是Dijkstra算法和Floyd-Warshall算法的详细说明：

Dijkstra算法

Dijkstra算法用于计算一个源节点到图中所有其他节点的最短路径。它的基本思想是通过逐步扩展最短路径集合来找到最短路径。

算法步骤：

  1. 初始化一个距离数组dist[]，用于存储从源节点到其他节点的距离估计值。将源节点的距离初始化为0，其他节点初始化为无穷大。

  2. 创建一个空的集合visited[]，用于跟踪已访问的节点。

  3. 重复以下步骤，直到visited[]包含所有节点： a. 从未访问的节点中选择距离最短的节点u。 b. 标记节点u为已访问。 c. 更新与节点u相邻的节点v的距离估计值，如果通过u到v的路径距离更短。

  4. 当所有节点都被访问后，dist[]中存储了从源节点到每个节点的最短距离。

import java.util.*;public class DijkstraAlgorithm {public static int[] dijkstra(int[][] graph, int source) {int n = graph.length;int[] dist = new int[n];boolean[] visited = new boolean[n];Arrays.fill(dist, Integer.MAX_VALUE);dist[source] = 0;for (int count = 0; count < n - 1; count++) {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];}}}return dist;}private static int minDistance(int[] dist, boolean[] visited) {int min = Integer.MAX_VALUE;int minIndex = -1;for (int i = 0; i < dist.length; i++) {if (!visited[i] && dist[i] <= min) {min = dist[i];minIndex = i;}}return minIndex;}public static void main(String[] args) {int[][] graph = {{0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0}};int source = 0;int[] dist = dijkstra(graph, source);for (int i = 0; i < dist.length; i++) {System.out.println("Distance from " + source + " to " + i + ": " + dist[i]);}}
}
 Floyd-Warshall算法

Floyd-Warshall算法用于计算图中所有节点之间的最短路径。它通过动态规划的方式计算所有节点对之间的最短路径。

算法步骤：

  1. 创建一个二维数组dist[][]，其中dist[i][j]表示从节点i到节点j的最短路径距离，初始化为无穷大。

  2. 初始化dist[i][i]为0，表示节点到自身的距离为0。

  3. 对于每一条边(u, v)，将dist[u][v]初始化为边的权重。

  4. 遍历所有节点对(i, j)，对于每对节点，尝试通过节点k（k为0到n-1）来缩短路径dist[i][j]，即dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

  5. 当遍历完所有节点对时，dist[][]中存储了所有节点之间的最短路径。

public class FloydWarshallAlgorithm {public static 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++) {for (int j = 0; j < n; j++) {System.out.println("Shortest distance from " + i + " to " + j + ": " + dist[i][j]);}}}public static void main(String[] args) {int[][] graph = {{0, 5, Integer.MAX_VALUE, 10},{Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE},{Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 1},{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}};floydWarshall(graph);}
}

 Dijkstra算法适用于单源最短路径问题，而Floyd-Warshall算法适用于所有节点对之间的最短路径问题。选择算法取决于问题的规模和要求。

2、最小生成树算法（Prim算法、Kruskal算法）

最小生成树算法（Minimum Spanning Tree Algorithms）用于在一个连通的加权图中找到一个包含所有节点的子图，并且这个子图是树（没有回路），同时具有最小的总权重。两个常用的最小生成树算法是Prim算法和Kruskal算法。

Prim算法

Prim算法从一个初始节点开始，逐步构建最小生成树，每次选择与当前树连接最近的节点，并将其添加到最小生成树中。这个过程持续进行，直到所有节点都包含在生成树中。

算法步骤：

  1. 选择一个起始节点。
  2. 初始化一个空的生成树和一个优先队列（或最小堆）来存储边的权重。
  3. 将起始节点加入生成树。
  4. 将所有与起始节点相邻的边加入优先队列。
  5. 从队列中取出具有最小权重的边（边的一端在生成树中，另一端不在），将其另一端的节点加入生成树，并将与新节点相邻的边加入队列。
  6. 重复步骤5，直到生成树包含了所有节点。
import java.util.*;public class PrimAlgorithm {public static void primMST(int[][] graph) {int n = graph.length;int[] parent = new int[n]; // 用于存储生成树的父节点int[] key = new int[n]; // 用于存储节点到生成树的最小权重boolean[] inMST = new boolean[n]; // 记录节点是否已在生成树中Arrays.fill(key, Integer.MAX_VALUE);key[0] = 0; // 从第一个节点开始for (int i = 0; i < n - 1; i++) {int u = minKey(key, inMST);inMST[u] = true;for (int v = 0; v < n; v++) {if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) {parent[v] = u;key[v] = graph[u][v];}}}printMST(parent, graph);}private static int minKey(int[] key, boolean[] inMST) {int min = Integer.MAX_VALUE;int minIndex = -1;for (int i = 0; i < key.length; i++) {if (!inMST[i] && key[i] < min) {min = key[i];minIndex = i;}}return minIndex;}private static 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]]);}}public static void main(String[] args) {int[][] graph = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};primMST(graph);}
}
Kruskal算法

Kruskal算法首先将所有边按权重排序，然后按照权重递增的顺序逐个加入生成树，但要确保加入的边不会形成回路。它使用并查集数据结构来检测回路。

算法步骤：

  1. 将图中的所有边按权重升序排序。
  2. 初始化一个空的生成树。
  3. 从排序后的边中选择一条最小权重的边。
  4. 检查加入这条边后是否会形成回路。如果不会，将边加入生成树。
  5. 重复步骤3和4，直到生成树包含了所有节点或没有更多的边可供选择。

 

import java.util.*;class Edge implements Comparable<Edge> {int src, dest, weight;public int compareTo(Edge compareEdge) {return this.weight - compareEdge.weight;}
}public class KruskalAlgorithm {public static void kruskalMST(int[][] graph) {int n = graph.length;List<Edge> edges = new ArrayList<>();for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (graph[i][j] != 0) {Edge edge = new Edge();edge.src = i;edge.dest = j;edge.weight = graph[i][j];edges.add(edge);}}}Collections.sort(edges);int[] parent = new int[n];Arrays.fill(parent, -1);List<Edge> mstEdges = new ArrayList<>();int mstWeight = 0;for (Edge edge : edges) {int x = find(parent, edge.src);int y = find(parent, edge.dest);if (x != y) {mstEdges.add(edge);mstWeight += edge.weight;union(parent, x, y);}}printMST(mstEdges);}private static int find(int[] parent, int node) {if (parent[node] == -1) {return node;}return find(parent, parent[node]);}private static void union(int[] parent, int x, int y) {int xRoot = find(parent, x);int yRoot = find(parent, y);parent[xRoot] = yRoot;}private static void printMST(List<Edge> mstEdges) {System.out.println("Edge \tWeight");for (Edge edge : mstEdges) {System.out.println(edge.src + " - " + edge.dest + "\t" + edge.weight);}}public static void main(String[] args) {int[][] graph = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};kruskalMST(graph);}
}

Prim算法和Kruskal算法都可以用于找到最小生成树，选择哪个算法取决于具体的问题和图的规模。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/148960.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

力扣第102题 广度优先搜索 二叉数 c++

力扣第102题 广度优先搜索 二叉数 c++

题目 102. 二叉树的层序遍历 中等 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20…
阅读更多...
CSDN博主粉丝数突破10万：坚持分享的力量与收获

CSDN博主粉丝数突破10万：坚持分享的力量与收获

今天&#xff0c;我在CSDN上看到了一位好友的统计数据&#xff0c;他统计了CSDN上所有粉丝数量排名靠前的博主的排名。虽然这个统计可能存在一些误差&#xff0c;但大体上应该是准确的。我惊讶地发现&#xff0c;截止到2023年10月4日&#xff0c;我的粉丝数量已经达到了101,376…
阅读更多...
uniapp项目实践总结(二十五)苹果 ios 平台 APP 打包教程

uniapp项目实践总结(二十五)苹果 ios 平台 APP 打包教程

导语：当你的应用程序开发完成后，在上架 ios 应用商店之前，需要进行打包操作，下面就简单介绍一下打包方法。 目录 准备工作注册账号生成证书打包配置准备工作 在打包之前，请保证你的 uniapp 应用程序编译到 ios 模拟器或者是真机调试基座环境下是可以正常运行的，苹果打包…
阅读更多...
二叉树题目：路径总和 II

二叉树题目：路径总和 II

文章目录 题目标题和出处难度题目描述要求示例数据范围 前言解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;路径总和 II 出处&#xff1a;113. 路径总和 II 难度 4 级 题目描述 要求 给你二叉树的根结点 root \tex…
阅读更多...
基于三平面映射的地形纹理化【Triplanar Mapping】

基于三平面映射的地形纹理化【Triplanar Mapping】

你可能遇到过这样的地形&#xff1a;悬崖陡峭的一侧的纹理拉伸得如此之大&#xff0c;以至于看起来不切实际。 也许你有一个程序化生成的世界&#xff0c;你无法对其进行 UV 展开和纹理处理。 推荐&#xff1a;用 NSDT编辑器 快速搭建可编程3D场景 三平面映射&#xff08;Trip…
阅读更多...
侯捷 C++ STL标准库和泛型编程 —— 9 STL周围

侯捷 C++ STL标准库和泛型编程 —— 9 STL周围

最后一篇&#xff0c;完结辽&#xff01;&#x1f60b; 9 STL周围 9.1 万用Hash Function Hash Function的常规写法&#xff1a;其中 hash_val 就是万用Hash Function class CustumerHash { public:size_t operator()(const Customer& c) const{ return hash_val(c.fna…
阅读更多...
DevEco Studio设置Nodejs提示路径只能包含英文、数字、下划线等

DevEco Studio设置Nodejs提示路径只能包含英文、数字、下划线等

安装DevEco Studio 3.1.1 Release 设置Nodejs路径使用nodejs默认安装路径 &#xff08;C:\Program Files\nodejs&#xff09; 提示只能包含英文、数字、下划线等 , 不想在安装nodejs请往下看 nodejs默认路径报错 修改配置文件 1、退出DevEco Studio 2、打开配置文件 cmd控制台…
阅读更多...
Visopsys 0.92 发布

Visopsys 0.92 发布

Visopsys 是一个 PC 机的操作系统&#xff0c;系统小型、快速而且开源。有着丰富的图形界面、抢先式多任务机制以及支持虚拟内存。Visopsys 视图兼容很多操作系统&#xff0c;但并不是他们的克隆版本。Visopsys 0.92 现已发布&#xff0c;此维护版本引入了多任务处理程序、文件…
阅读更多...
卸载无用Mac电脑软件应用程序方法教程

卸载无用Mac电脑软件应用程序方法教程

如何在Mac电脑卸载应用程序&#xff1f;Mac OS系统的用户卸载软件时&#xff0c;大部分会选择直接将软件图标拖进废纸篓清倒。这种操作会留下大量程序残余文件占据磁盘空间&#xff0c;手动清理又怕误删文件&#xff0c;有时还会遇到无法移除的恶意/流氓软件。小编今天分享3种可…
阅读更多...
zookeeper选举机制

zookeeper选举机制

全新集群选举 zookeeper 全新集群选举机制网上资料很多说法很模糊&#xff0c;仔细思考了一下&#xff0c;应该是这样 得到票数最多的机器>机器总数半数 具体启动过程中的哪个节点成为 leader 与 zoo.cfg 中配置的节点数有关&#xff0c;下面以3个举例 选举过程如下 server…
阅读更多...
540. 有序数组中的单一元素

540. 有序数组中的单一元素

链接&#xff1a; 540. 有序数组中的单一元素 代码&#xff1a; 方法一&#xff1a;全数组的二分查找 思路和算法 假设只出现一次的元素位于下标 xxx&#xff0c;由于其余每个元素都出现两次&#xff0c;因此下标 xxx 的左边和右边都有偶数个元素&#xff0c;数组的长度是奇…
阅读更多...
【2023年11月第四版教材】第18章《项目绩效域》(第一部分)

【2023年11月第四版教材】第18章《项目绩效域》(第一部分)

第18章《项目绩效域》&#xff08;第一部分&#xff09; 1 章节内容2 干系人绩效域2.1 绩效要点2.2 执行效果检查2.3 与其他绩效域的相互作用 3 团队绩效域3.1 绩效要点3.2 与其他绩效域的相互作用3.3 执行效果检查3.4 开发方法和生命周期绩效域 4 绩效要点4.1 与其他绩效域的相…
阅读更多...
新版校园跑腿独立版小程序源码 多校版本，多模块，适合跑腿，外卖，表白，二手，快递等校园服务

新版校园跑腿独立版小程序源码 多校版本，多模块，适合跑腿，外卖，表白，二手，快递等校园服务

最新校园跑腿小程序源码 多校版本&#xff0c;多模块&#xff0c;适合跑腿&#xff0c;外卖&#xff0c;表白&#xff0c;二手&#xff0c;快递等校园服务 此版本为独立版本&#xff0c;不需要** 直接放入就可以 需要自己准备好后台的服务器&#xff0c;已认证的小程序&#xf…
阅读更多...
MyBatisPlus（九）模糊查询

MyBatisPlus（九）模糊查询

说明 模糊查询&#xff0c;对应SQL语句中的 like 语句&#xff0c;模糊匹配“要查询的内容”。 like /*** 查询用户列表&#xff0c; 查询条件&#xff1a;姓名包含 "J"*/Testvoid like() {String name "J";LambdaQueryWrapper<User> wrapper ne…
阅读更多...
讲讲项目里的仪表盘编辑器（二）

讲讲项目里的仪表盘编辑器（二）

应用场景 正常来说&#xff0c;编辑器应用场景应该包括&#xff1a; 编辑器-预览 编辑器 最终运行时 怎么去设计 上一篇推文&#xff0c;我们已经大概了解了编辑器场景。接下来&#xff0c;我们来看预览时的设计 编辑器-预览 点击预览按钮&#xff0c;执行以…
阅读更多...
Spring Cloud Loadbalancer 实现客户端负载均衡

Spring Cloud Loadbalancer 实现客户端负载均衡

针对 ribbon 负载均衡组件&#xff0c; 官方提出的替换解决方案是 Spring Cloud Loadbalancer。本次主要通过学习示例介绍了 Spring Cloud Loadbalancer 的基础使用。 1&#xff0c;引入pom <dependency><groupId>org.springframework.cloud</groupId><…
阅读更多...
React18入门（第一篇）——JSX、TSX语法详解

React18入门（第一篇）——JSX、TSX语法详解

文章目录 一、JSX 语法简介二、和 HTML 标签的几点不同三、JSX 属性四、JSX 事件4.1 简单点击事件4.2 类型限制4.3 带参数&#xff0c;箭头函数 五、插入 JS 变量六、JSX 中使用条件判断七、循环 一、JSX 语法简介 JSX - 是 JS 的扩展&#xff0c;写在 JS 代码里面&#xff0c…
阅读更多...
ROS（0）命令及学习资源汇总

ROS（0）命令及学习资源汇总

ROS安装命令 参考&#xff1a;Ubuntu20.04.4安装ROS Noetic详细教程 - 知乎 安装C和Python3 sudo apt-get install g sudo apt-get install python3 ROS运行小海龟仿真器 roscore确定ROS是否运行成功rosrun turtlesim turtlesim_node运行小海龟仿真器rosrun turtlesim turtle_…
阅读更多...
【微信小程序开发】一文学会使用CSS控制样式布局与美化

【微信小程序开发】一文学会使用CSS控制样式布局与美化

引言 在微信小程序开发中&#xff0c;CSS样式布局和美化是非常重要的一部分&#xff0c;它能够为小程序增添美感&#xff0c;提升用户体验。本文将介绍如何学习使用CSS进行样式布局和美化&#xff0c;同时给出代码示例&#xff0c;帮助开发者更好地掌握这一技巧。 一、CSS样式布…
阅读更多...
星宿UI2.4资源付费变现小程序源码 支持流量主

星宿UI2.4资源付费变现小程序源码 支持流量主

第一个小程序为星宿小程序 目前是最新版2.0 搭建星宿需要&#xff1a;备用域名 服务器 微信小程序账号 功能&#xff1a;文章展示 文章分类 资源链接下载 轮播图 直接下载附件功能 很多 很适合做资源类分享 源码下载&#xff1a;https://download.csdn.net/download/m0_6604…
阅读更多...
最新文章

Copyright @ 2022~2023