本文共 9360 字,大约阅读时间需要 31 分钟。
今天我想和大家分享一些经典的算法知识,这些算法在编程中经常被用到,了解它们的逻辑和应用场景对你的职业发展很有帮助。
简介:又叫折半查找,用于有序数据集快速查找特定元素。其时间复杂度为O(logn),适用于数组查找。
应用场景:常用于查找数组中的元素,前提是数组必须预先排好序。
步骤:
代码示例:
public static int biSearch(int[] array, int a) { int lo = 0; int hi = array.length - 1; int mid; while (lo <= hi) { mid = (lo + hi) / 2; if (array[mid] == a) { return mid; } else if (array[mid] > a) { hi = mid - 1; } else { lo = mid + 1; } } return -1; // 表示无找到}
简介:通过比较相邻元素并交换位置,逐步将最大的元素“沉淀”到数组末尾。
应用场景:适用于数据量不大且要求稳定性的场景。
步骤:
代码示例:
public static void bubbleSort(int[] a, int n) { boolean swapped; for (int i = 0; i < n; i++) { swapped = false; for (int j = 1; j < n - i; j++) { if (a[j - 1] > a[j]) { // 交换位置 int temp = a[j - 1]; a[j - 1] = a[j]; a[j] = temp; swapped = true; } } if (!swapped) { break; } }}
简介:通过构建有序序列,将未排序元素从后向前插入适当位置。
应用场景:适用于数据量不大且对稳定性有要求的场景。
步骤:
代码示例:
public class InsertSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); for (int i = 1; i < arr.length; i++) { int tmp = arr[i]; int j = i; while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } if (j != i) { arr[j] = tmp; } } return arr; }}
简介:以某个元素为基准,将比基准小的元素放在左边,比基准大的放在右边。
应用场景:适用于数据量大且不考虑稳定性的场景。
步骤:
代码示例:
public void sort(int[] a, int low, int high) { int start = low; int end = high; int key = a[low]; while (end > start) { while (end > start && a[end] >= key) { end--; } if (a[end] <= key) { int temp = a[end]; a[end] = a[start]; a[start] = temp; } while (start < end && a[start] <= key) { start++; } if (a[start] >= key) { int temp = a[start]; a[start] = a[end]; a[end] = temp; } } if (start > low) { sort(a, low, start - 1); } if (end < high) { sort(a, center + 1, right); }}
简介:将数组分成若干个子数组,每个子数组进行直接插入排序。
应用场景:适用于数据量较大且对空间有要求的场景。
步骤:
代码示例:
private void shellSort(int[] a) { int dk = a.length / 2; while (dk >= 1) { shellInsertSort(a, dk); dk = dk / 2; }}private void shellInsertSort(int[] a, int dk) { for (int i = dk; i < a.length; i++) { if (a[i] < a[i - dk]) { int j; for (j = i - dk; j >= 0 && a[j] > a[i]; j--) { a[j + 1] = a[j]; } a[j + 1] = a[i]; } }}
简介:将数组分成若干个子数组,分别进行归并,合并成一个有序数组。
应用场景:适用于内存有限且需要并行计算的场景。
步骤:
代码示例:
public class MergeSortTest { public static void main(String[] args) { int[] data = new int[]{5, 3, 6, 2, 1, 9, 4, 8, 7}; print(data); mergeSort(data); System.out.println("排序后的数组:"); print(data); } public static void mergeSort(int[] data) { sort(data, 0, data.length - 1); } private static void sort(int[] data, int left, int right) { if (left >= right) { return; } int center = (left + right) / 2; sort(data, left, center); sort(data, center + 1, right); merge(data, left, center, right); print(data); } private static void merge(int[] data, int left, int center, int right) { int[] tmpArr = new int[data.length]; int mid = center + 1; int third = left; int tmp = left; while (left < center && mid < right) { if (data[left] <= data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } while (mid < right) { tmpArr[third++] = data[mid++]; } while (left < center) { tmpArr[third++] = data[left++]; } for (int i = 0; i < third; i++) { data[tmp + i] = tmpArr[i]; } } private static void print(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + "\t"); } System.out.println(); }}
简介:在搜索过程中,通过判断条件避免不必要的遍历,减少计算量。
应用场景:常用于DFS和BFS搜索算法中,提前剪枝搜索路径。
步骤:
代码示例:
class Solution { public ListcombinationSum(int[] candidates, int target) { Arrays.sort(candidates); List track = new LinkedList<>(); combinationSum(candidates, 0, target, track); return track; } private void combinationSum(int[] candidates, int start, int target, List track) { if (target < 0) { return; } else if (target == 0) { result.add(new LinkedList<>(track)); return; } for (int i = start; i < candidates.length; i++) { if (target < candidates[i]) { break; } track.add(candidates[i]); combinationSum(candidates, i, target - candidates[i], track); track.remove(); } }}
简介:从起始点出发,找到到达目标点的路径中权值之和最小的路径。
应用场景:常用于网络路由、机器人探路和交通导航等。
步骤(Dijkstra算法示例):
代码示例:
static int[] pathSrc = new int[9];static int[] shortPath = new int[9];static void shortestPath_DijkStra(MGraph m, int v0) { int[] finalPath = new int[9]; int[] distances = new int[9]; boolean[] visited = new boolean[9]; distances[v0] = 0; finalPath[v0] = 1; PriorityQueuequeue = new PriorityQueue<>(); for (int i = 0; i < m.numNodes; i++) { if (i != v0) { queue.add(m.nodes[v0].getEdge(i)); } } while (!queue.isEmpty()) { Edge e = queue.poll(); Node current = e.getDest(); if (visited[current.getIndex()]) { continue; } visited[current.getIndex()] = true; finalPath[current.getIndex()] = 1; for (int neighbor = 0; neighbor < m.numNodes; neighbor++) { if (!visited[neighbor] && e.getWeight() + distances[current.getIndex()] < distances[neighbor]) { distances[neighbor] = e.getWeight() + distances[current.getIndex()]; finalPath[neighbor] = finalPath[current.getIndex()]; queue.add(m.nodes[current.getIndex()].getEdge(neighbor)); } } }}
简介:找到数组中和最大的连续子数组。
应用场景:常用于股票价格分析,找到最佳买入和卖出点。
步骤:
代码示例:
class Solution { public int maxSubArray(int[] nums) { if (nums.length <= 0) { return 0; } int max = Integer.MIN_VALUE; int current = 0; for (int num : nums) { current = current < 0 ? num : current + num; max = Math.max(max, current); } return max; }}
简介:找到两个或多个序列中的最长公共子序列。
应用场景:广泛应用于版本控制工具如Git,以及生物信息学中的序列比对。
步骤:
代码示例:
class Solution { public int longestCommonSubsequence(String text1, String text2) { int len1 = text1.length(); int len2 = text2.length(); int[][] a = new int[len1 + 1][len2 + 1]; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { a[i][j] = a[i - 1][j - 1] + 1; } else { a[i][j] = Math.max(a[i - 1][j], a[i][j - 1]); } } } return a[len1][len2]; }}
简介:在带权无向图中找到权重和最小的生成树。
应用场景:常用于网络拓扑学中的最小成本生成树问题。
步骤(Prim算法示例):
代码示例:
public ListgenerateMinTreePrim(T first) { List result = new LinkedList<>(); Map edgeMap = new HashMap<>(); for (Vertex vertex : getVertexIterator()) { edgeMap.put(vertex, new Edge(vertex, vertex, Double.MAX_VALUE)); } Vertex startVertex = vertexMap.get(first); if (startVertex == null) { System.out.println("没有节点:" + first); return result; } while (!edgeMap.isEmpty()) { Vertex vertex = edgeMap.keySet().iterator().next(); Edge edge = edgeMap.get(vertex); result.add(edge); edgeMap.remove(vertex); if (vertex.getLabel().equals(first)) { result.remove(edge); } for (Vertex now : edgeMap.keySet()) { Edge newEdge = edgeMap.get(now); Edge newEdgeToVertex = now.hasNeighbourVertex(vertex); if (newEdgeToVertex != null && newEdgeToVertex.getWeight() < edge.getWeight()) { edgeMap.remove(now); edgeMap.put(now, newEdgeToVertex); } } } return result;}
通过学习这些经典算法,你可以更好地理解编程的核心思想,提升你的技术能力。在面试中,这些算法也是评估你的重要内容。如果你对某些算法还有疑问,可以继续深入研究,或者在实际项目中多多实践。希望这些内容对你有所帮助!
转载地址:http://twbfz.baihongyu.com/