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

本文共 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 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 Order By实现原理分析和Filesort优化
    查看>>
    mysql problems
    查看>>
    mysql replace first,MySQL中处理各种重复的一些方法
    查看>>
    MySQL replace函数替换字符串语句的用法(mysql字符串替换)
    查看>>
    mysql replace用法
    查看>>
    Mysql Row_Format 参数讲解
    查看>>
    mysql select, from ,join ,on ,where groupby,having ,order by limit的执行顺序和书写顺序
    查看>>
    MySQL Server 5.5安装记录
    查看>>
    mysql server has gone away
    查看>>
    mysql slave 停了_slave 停止。求解决方法
    查看>>
    MySQL SQL 优化指南:主键、ORDER BY、GROUP BY 和 UPDATE 优化详解
    查看>>
    MYSQL sql语句针对数据记录时间范围查询的效率对比
    查看>>
    mysql sum 没返回,如果没有找到任何值,我如何在MySQL中获得SUM函数以返回'0'?
    查看>>
    mysql Timestamp时间隔了8小时
    查看>>
    Mysql tinyint(1)与tinyint(4)的区别
    查看>>
    mysql union orderby 无效
    查看>>
    mysql v$session_Oracle 进程查看v$session
    查看>>
    mysql where中如何判断不为空
    查看>>
    MySQL Workbench 使用手册:从入门到精通
    查看>>
    mysql workbench6.3.5_MySQL Workbench
    查看>>