博客
关于我
算法很美,听我讲完这些Java经典算法包你爱上她
阅读量:459 次
发布时间:2019-03-06

本文共 9614 字,大约阅读时间需要 32 分钟。

今天我想和大家分享一些经典的算法知识,这些算法在编程中经常被用到,了解它们的逻辑和应用场景对你的职业发展很有帮助。

二分查找

简介:又叫折半查找,用于有序数据集快速查找特定元素。其时间复杂度为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 List
    combinationSum(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算法示例):

  • 初始化所有节点的距离为无穷大,起始点距离为0。
  • 使用优先队列选择当前最小距离的节点。
  • 遍历该节点的所有邻居,更新它们的最短距离。
  • 重复直到找到目标点或队列为空。
  • 代码示例

    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;
    PriorityQueue
    queue = 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 List
    generateMinTreePrim(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/

    你可能感兴趣的文章
    Mysql 学习总结(86)—— Mysql 的 JSON 数据类型正确使用姿势
    查看>>
    Mysql 学习总结(87)—— Mysql 执行计划(Explain)再总结
    查看>>
    Mysql 学习总结(88)—— Mysql 官方为什么不推荐用雪花 id 和 uuid 做 MySQL 主键
    查看>>
    Mysql 学习总结(89)—— Mysql 库表容量统计
    查看>>
    mysql 实现主从复制/主从同步
    查看>>
    mysql 审核_审核MySQL数据库上的登录
    查看>>
    mysql 导入 sql 文件时 ERROR 1046 (3D000) no database selected 错误的解决
    查看>>
    mysql 导入导出大文件
    查看>>
    MySQL 导出数据
    查看>>
    mysql 将null转代为0
    查看>>
    mysql 常用
    查看>>
    MySQL 常用列类型
    查看>>
    mysql 常用命令
    查看>>
    Mysql 常见ALTER TABLE操作
    查看>>
    MySQL 常见的 9 种优化方法
    查看>>
    MySQL 常见的开放性问题
    查看>>
    Mysql 常见错误
    查看>>
    mysql 常见问题
    查看>>
    MYSQL 幻读(Phantom Problem)不可重复读
    查看>>
    mysql 往字段后面加字符串
    查看>>