面试系列 - 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算法都可以用于找到最小生成树，选择哪个算法取决于具体的问题和图的规模。