• 面试系列 - 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，直到所有元素都被插入到适当的位置，形成完全有序的序列。
    1. public class InsertionSort {
    2.     public static void insertionSort(int[] arr) {
    3.         int n = arr.length;
    4.         for (int i = 1; i < n; i++) {
    5.             int currentElement = arr[i];
    6.             int j = i - 1;
    7.             
    8.             // 从已排序部分的末尾开始，依次比较并移动元素
    9.             while (j >= 0 && arr[j] > currentElement) {
    10.                 arr[j + 1] = arr[j]; // 向右移动元素
    11.                 j--;
    12.             }
    13.             
    14.             // 插入当前元素到合适的位置
    15.             arr[j + 1] = currentElement;
    16.         }
    17.     }
    18.  
    19.     public static void main(String[] args) {
    20.         int[] arr = {12, 11, 13, 5, 6};
    21.         insertionSort(arr);
    22.  
    23.         System.out.println("排序后的数组：");
    24.         for (int num : arr) {
    25.             System.out.print(num + " ");
    26.         }
    27.     }
    28. }

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

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

    2、归并排序（Merge Sort）

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

    1. public class MergeSort {
    2.     public static void mergeSort(int[] arr) {
    3.         if (arr == null || arr.length <= 1) {
    4.             return; // 如果数组为空或只有一个元素，无需排序
    5.         }
    6.         
    7.         // 计算中间索引
    8.         int middle = arr.length / 2;
    9.         
    10.         // 创建左右子数组
    11.         int[] left = new int[middle];
    12.         int[] right = new int[arr.length - middle];
    13.         
    14.         // 将元素分配到左右子数组
    15.         System.arraycopy(arr, 0, left, 0, middle);
    16.         System.arraycopy(arr, middle, right, 0, arr.length - middle);
    17.         
    18.         // 递归地对左右子数组进行排序
    19.         mergeSort(left);
    20.         mergeSort(right);
    21.         
    22.         // 合并两个已排序的子数组
    23.         merge(arr, left, right);
    24.     }
    25.  
    26.     public static void merge(int[] result, int[] left, int[] right) {
    27.         int i = 0, j = 0, k = 0;
    28.         
    29.         // 比较并合并左右子数组的元素
    30.         while (i < left.length && j < right.length) {
    31.             if (left[i] <= right[j]) {
    32.                 result[k++] = left[i++];
    33.             } else {
    34.                 result[k++] = right[j++];
    35.             }
    36.         }
    37.         
    38.         // 处理左子数组中剩余的元素
    39.         while (i < left.length) {
    40.             result[k++] = left[i++];
    41.         }
    42.         
    43.         // 处理右子数组中剩余的元素
    44.         while (j < right.length) {
    45.             result[k++] = right[j++];
    46.         }
    47.     }
    48.  
    49.     public static void main(String[] args) {
    50.         int[] arr = {12, 11, 13, 5, 6, 7};
    51.         mergeSort(arr);
    52.  
    53.         System.out.println("排序后的数组：");
    54.         for (int num : arr) {
    55.             System.out.print(num + " ");
    56.         }
    57.     }
    58. }

     在上面的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[]中存储了从源节点到每个节点的最短距离。

    1. import java.util.*;
    2.  
    3. public class DijkstraAlgorithm {
    4.     public static int[] dijkstra(int[][] graph, int source) {
    5.         int n = graph.length;
    6.         int[] dist = new int[n];
    7.         boolean[] visited = new boolean[n];
    8.         Arrays.fill(dist, Integer.MAX_VALUE);
    9.         dist[source] = 0;
    10.  
    11.         for (int count = 0; count < n - 1; count++) {
    12.             int u = minDistance(dist, visited);
    13.             visited[u] = true;
    14.  
    15.             for (int v = 0; v < n; v++) {
    16.                 if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
    17.                     dist[v] = dist[u] + graph[u][v];
    18.                 }
    19.             }
    20.         }
    21.  
    22.         return dist;
    23.     }
    24.  
    25.     private static int minDistance(int[] dist, boolean[] visited) {
    26.         int min = Integer.MAX_VALUE;
    27.         int minIndex = -1;
    28.         for (int i = 0; i < dist.length; i++) {
    29.             if (!visited[i] && dist[i] <= min) {
    30.                 min = dist[i];
    31.                 minIndex = i;
    32.             }
    33.         }
    34.         return minIndex;
    35.     }
    36.  
    37.     public static void main(String[] args) {
    38.         int[][] graph = {
    39.             {0, 4, 0, 0, 0, 0, 0, 8, 0},
    40.             {4, 0, 8, 0, 0, 0, 0, 11, 0},
    41.             {0, 8, 0, 7, 0, 4, 0, 0, 2},
    42.             {0, 0, 7, 0, 9, 14, 0, 0, 0},
    43.             {0, 0, 0, 9, 0, 10, 0, 0, 0},
    44.             {0, 0, 4, 14, 10, 0, 2, 0, 0},
    45.             {0, 0, 0, 0, 0, 2, 0, 1, 6},
    46.             {8, 11, 0, 0, 0, 0, 1, 0, 7},
    47.             {0, 0, 2, 0, 0, 0, 6, 7, 0}
    48.         };
    49.  
    50.         int source = 0;
    51.         int[] dist = dijkstra(graph, source);
    52.         for (int i = 0; i < dist.length; i++) {
    53.             System.out.println("Distance from " + source + " to " + i + ": " + dist[i]);
    54.         }
    55.     }
    56. }
     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[][]中存储了所有节点之间的最短路径。

    1. public class FloydWarshallAlgorithm {
    2.     public static void floydWarshall(int[][] graph) {
    3.         int n = graph.length;
    4.         int[][] dist = new int[n][n];
    5.  
    6.         for (int i = 0; i < n; i++) {
    7.             for (int j = 0; j < n; j++) {
    8.                 dist[i][j] = graph[i][j];
    9.             }
    10.         }
    11.  
    12.         for (int k = 0; k < n; k++) {
    13.             for (int i = 0; i < n; i++) {
    14.                 for (int j = 0; j < n; j++) {
    15.                     if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
    16.                             && dist[i][k] + dist[k][j] < dist[i][j]) {
    17.                         dist[i][j] = dist[i][k] + dist[k][j];
    18.                     }
    19.                 }
    20.             }
    21.         }
    22.  
    23.         for (int i = 0; i < n; i++) {
    24.             for (int j = 0; j < n; j++) {
    25.                 System.out.println("Shortest distance from " + i + " to " + j + ": " + dist[i][j]);
    26.             }
    27.         }
    28.     }
    29.  
    30.     public static void main(String[] args) {
    31.         int[][] graph = {
    32.             {0, 5, Integer.MAX_VALUE, 10},
    33.             {Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE},
    34.             {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 1},
    35.             {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
    36.         };
    37.  
    38.         floydWarshall(graph);
    39.     }
    40. }

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

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

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

    Prim算法

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

    算法步骤：

    1. 选择一个起始节点。
    2. 初始化一个空的生成树和一个优先队列（或最小堆）来存储边的权重。
    3. 将起始节点加入生成树。
    4. 将所有与起始节点相邻的边加入优先队列。
    5. 从队列中取出具有最小权重的边（边的一端在生成树中，另一端不在），将其另一端的节点加入生成树，并将与新节点相邻的边加入队列。
    6. 重复步骤5，直到生成树包含了所有节点。
    1. import java.util.*;
    2.  
    3. public class PrimAlgorithm {
    4.     public static void primMST(int[][] graph) {
    5.         int n = graph.length;
    6.         int[] parent = new int[n]; // 用于存储生成树的父节点
    7.         int[] key = new int[n]; // 用于存储节点到生成树的最小权重
    8.  
    9.         boolean[] inMST = new boolean[n]; // 记录节点是否已在生成树中
    10.         Arrays.fill(key, Integer.MAX_VALUE);
    11.         key[0] = 0; // 从第一个节点开始
    12.  
    13.         for (int i = 0; i < n - 1; i++) {
    14.             int u = minKey(key, inMST);
    15.             inMST[u] = true;
    16.             for (int v = 0; v < n; v++) {
    17.                 if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) {
    18.                     parent[v] = u;
    19.                     key[v] = graph[u][v];
    20.                 }
    21.             }
    22.         }
    23.  
    24.         printMST(parent, graph);
    25.     }
    26.  
    27.     private static int minKey(int[] key, boolean[] inMST) {
    28.         int min = Integer.MAX_VALUE;
    29.         int minIndex = -1;
    30.         for (int i = 0; i < key.length; i++) {
    31.             if (!inMST[i] && key[i] < min) {
    32.                 min = key[i];
    33.                 minIndex = i;
    34.             }
    35.         }
    36.         return minIndex;
    37.     }
    38.  
    39.     private static void printMST(int[] parent, int[][] graph) {
    40.         System.out.println("Edge \tWeight");
    41.         for (int i = 1; i < parent.length; i++) {
    42.             System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
    43.         }
    44.     }
    45.  
    46.     public static void main(String[] args) {
    47.         int[][] graph = {
    48.             {0, 2, 0, 6, 0},
    49.             {2, 0, 3, 8, 5},
    50.             {0, 3, 0, 0, 7},
    51.             {6, 8, 0, 0, 9},
    52.             {0, 5, 7, 9, 0}
    53.         };
    54.  
    55.         primMST(graph);
    56.     }
    57. }
    Kruskal算法

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

    算法步骤：

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

     

    1. import java.util.*;
    2.  
    3. class Edge implements Comparable {
    4.     int src, dest, weight;
    5.  
    6.     public int compareTo(Edge compareEdge) {
    7.         return this.weight - compareEdge.weight;
    8.     }
    9. }
    10.  
    11. public class KruskalAlgorithm {
    12.     public static void kruskalMST(int[][] graph) {
    13.         int n = graph.length;
    14.         List edges = new ArrayList<>();
    15.  
    16.         for (int i = 0; i < n; i++) {
    17.             for (int j = i + 1; j < n; j++) {
    18.                 if (graph[i][j] != 0) {
    19.                     Edge edge = new Edge();
    20.                     edge.src = i;
    21.                     edge.dest = j;
    22.                     edge.weight = graph[i][j];
    23.                     edges.add(edge);
    24.                 }
    25.             }
    26.         }
    27.  
    28.         Collections.sort(edges);
    29.  
    30.         int[] parent = new int[n];
    31.         Arrays.fill(parent, -1);
    32.  
    33.         List mstEdges = new ArrayList<>();
    34.         int mstWeight = 0;
    35.  
    36.         for (Edge edge : edges) {
    37.             int x = find(parent, edge.src);
    38.             int y = find(parent, edge.dest);
    39.  
    40.             if (x != y) {
    41.                 mstEdges.add(edge);
    42.                 mstWeight += edge.weight;
    43.                 union(parent, x, y);
    44.             }
    45.         }
    46.  
    47.         printMST(mstEdges);
    48.     }
    49.  
    50.     private static int find(int[] parent, int node) {
    51.         if (parent[node] == -1) {
    52.             return node;
    53.         }
    54.         return find(parent, parent[node]);
    55.     }
    56.  
    57.     private static void union(int[] parent, int x, int y) {
    58.         int xRoot = find(parent, x);
    59.         int yRoot = find(parent, y);
    60.         parent[xRoot] = yRoot;
    61.     }
    62.  
    63.     private static void printMST(List mstEdges) {
    64.         System.out.println("Edge \tWeight");
    65.         for (Edge edge : mstEdges) {
    66.             System.out.println(edge.src + " - " + edge.dest + "\t" + edge.weight);
    67.         }
    68.     }
    69.  
    70.     public static void main(String[] args) {
    71.         int[][] graph = {
    72.             {0, 2, 0, 6, 0},
    73.             {2, 0, 3, 8, 5},
    74.             {0, 3, 0, 0, 7},
    75.             {6, 8, 0, 0, 9},
    76.             {0, 5, 7, 9, 0}
    77.         };
    78.  
    79.         kruskalMST(graph);
    80.     }
    81. }

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

  • 相关阅读:
    C++11新增特性lambda表达式
    百度Mysql面试题总结
    Pick-a-Pic:An open dataset of user preferences for text-to-image generation
    在Visual Studio Code macOS上尽量用Clang编译C++
    区块链安全应用----压力测试
    Java实现DFA算法进行敏感词过滤
    读懂MCU产品选型表
    【Effect C++ 笔记】（四）设计与声明
    spring整合mybatis
    开源OA开发平台最新教程：新版消息配置
  • 原文地址：https://blog.csdn.net/TreeShu321/article/details/133558995