首页 > 编程语言 >【数据结构与算法】《Java 算法宝典：探秘从排序到回溯的奇妙世界》

【数据结构与算法】《Java 算法宝典：探秘从排序到回溯的奇妙世界》

时间：2024-10-27 22:18:33浏览次数：6  
标签：arr Java int ++ 算法 探秘 public

在这里插入图片描述

目录

标题：《Java 算法宝典：探秘从排序到回溯的奇妙世界》

摘要： 本文将深入探讨 Java 中的各种基本算法，包括排序、查找、递归、动态规划、图算法、贪心算法、分治算法和回溯算法。通过详细的解释、有趣的例子和可运行的 Java 代码片段，帮助读者轻松掌握这些算法的实现逻辑。无论你是 Java 新手还是经验丰富的开发者，都能从本文中获得宝贵的知识和实用的技巧，提升编程能力。
关键词：Java、算法、排序、查找、递归、动态规划、图算法、贪心算法、分治算法、回溯算法

一、排序算法

1、冒泡排序

  • 原理：重复遍历要排序的数列，比较每对相邻元素的大小，若顺序错误则交换它们的位置。
  • 例子：假设有一组数字 [5, 3, 8, 4, 2]，首先比较 5 和 3，交换位置得到 [3, 5, 8, 4, 2]，接着比较 5 和 8，不交换，再比较 8 和 4，交换得到 [3, 5, 4, 8, 2]，继续比较 8 和 2，交换得到 [3, 5, 4, 2, 8]。这是第一遍遍历的结果，后面继续重复这个过程，直到整个数列有序。
  • Java 代码：
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j] 和 arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

2、选择排序

  • 原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后从剩余未排序元素中继续找最小（大）元素，放到已排序序列的末尾。
  • 例子：对于 [5, 3, 8, 4, 2]，首先找到最小元素 2，放到第一位得到 [2, 3, 8, 4, 5]，然后在剩余元素 [3, 8, 4, 5] 中找到最小元素 3，放到第二位得到 [2, 3, 8, 4, 5]，以此类推。
  • Java 代码：
public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换 arr[i] 和 arr[minIndex]
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

3、插入排序

  • 原理：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
  • 例子：以 [5, 3, 8, 4, 2] 为例，首先将 5 视为有序序列，然后处理 3，将 3 插入到 5 前面得到 [3, 5, 8, 4, 2]，接着处理 8，保持不变得到 [3, 5, 8, 4, 2]，再处理 4，将 4 插入到 3 和 5 之间得到 [3, 4, 5, 8, 2]，最后处理 2，将 2 插入到最前面得到 [2, 3, 4, 5, 8]。
  • Java 代码：
public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

4、快速排序

  • 原理：通过一个基准值将数据分为两部分，一部分数据比基准值小，另一部分数据比基准值大，然后递归地在这两部分数据上重复这个过程。
  • 例子：对于 [5, 3, 8, 4, 2]，选择第一个元素 5 作为基准值，经过一次划分后得到 [3, 4, 2] 和 [8]，然后分别对这两部分继续进行快速排序。
  • Java 代码：
public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

5、归并排序

  • 原理：采用分治法，将已有序的序列合并成一个新的有序序列。
  • 例子：对于 [5, 3, 8, 4, 2]，首先将其分为 [5, 3] 和 [8, 4, 2]，然后分别对这两部分进行归并排序，得到 [3, 5] 和 [2, 4, 8]，最后将这两个有序序列合并得到 [2, 3, 4, 5, 8]。
  • Java 代码：
public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr.length > 1) {
            int mid = arr.length / 2;
            int[] left = new int[mid];
            int[] right = new int[arr.length - mid];
            System.arraycopy(arr, 0, left, 0, mid);
            System.arraycopy(arr, mid, right, 0, arr.length - mid);
            mergeSort(left);
            mergeSort(right);
            merge(arr, left, right);
        }
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }
}

二、查找算法

1、线性查找

  • 原理：从数组的一端开始，逐个检查数组的每个元素，直到找到所需的值。
  • 例子：在 [5, 3, 8, 4, 2] 中查找数字 4，从第一个元素 5 开始，依次比较，直到找到 4。
  • Java 代码：
public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

2、二分查找

  • 原理：在有序数组中查找特定元素，通过比较数组中间的元素来确定所需元素是否在数组的哪一半，然后根据比较结果缩小搜索范围，直到找到元素或范围为空。
  • 例子：在 [2, 3, 4, 5, 8] 中查找数字 4，首先比较中间元素 5，发现 4 比 5 小，所以在左边一半继续查找，中间元素是 3，发现 4 比 3 大，所以在右边一半继续查找，中间元素正好是 4，找到目标。
  • Java 代码：
public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

三、递归算法

原理：递归是一种在问题解决过程中自我调用的算法。它将问题分解为更小的子问题，直到达到基本情况（base case），然后逐步解决这些子问题，最终解决原始问题。
例子：计算阶乘 n!，可以用递归的方式定义为 n! = n * (n - 1)!，当 n = 0 或 1 时，基本情况为 1。
Java 代码：
java
Copy
public class RecursionExample {
public static int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
}

四、动态规划

  • 原理：动态规划是一种将复杂问题分解为更小的子问题，并存储这些子问题的解（通常是在表格中），以避免重复计算的算法。它通常用于求解具有重叠子问题和最优子结构特性的问题。
  • 例子：计算斐波那契数列的第 n 项，可以用动态规划的方法避免重复计算。定义状态 dp [i] 表示斐波那契数列的第 i 项，状态转移方程为 dp [i] = dp [i - 1] + dp [i - 2]。
  • Java 代码：
public class DynamicProgrammingExample {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

标题：《Java 算法奇妙世界：从图算法到回溯，解锁编程新境界》

摘要： 本文将深入探讨 Java 中的基本算法，包括图算法（深度优先搜索 DFS 和广度优先搜索 BFS）、贪心算法、分治算法以及回溯算法。通过详细的解释、有趣的例子和可运行的 Java 代码片段，帮助读者轻松理解这些算法的实现逻辑。无论你是 Java 新手还是经验丰富的开发者，都能从本文中获得宝贵的知识，提升编程技能。快来一起探索 Java 算法的奇妙世界吧！

关键词：Java 算法、图算法、深度优先搜索、广度优先搜索、贪心算法、分治算法、回溯算法

五、图算法

1. 深度优先搜索（DFS）

  • 原理：从图的某个顶点开始，尽可能深地搜索图的顶点，直到达到一个顶点没有未被访问的邻接顶点，然后回溯到上一个顶点继续搜索。
  • 例子：想象你在一个神秘的迷宫中，你的任务是找到出口。你从一个入口开始，沿着一条路径一直走，直到走到死胡同或者已经没有未探索的方向。这时，你就回溯到上一个岔路口，选择另一条路继续探索。这个过程就类似于深度优先搜索。
  • Java 代码：
import java.util.ArrayList;
import java.util.List;

class Graph {
    private int V;
    private List<List<Integer>> adjList;

    Graph(int v) {
        V = v;
        adjList = new ArrayList<>();
        for (int i = 0; i < v; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    void addEdge(int v, int w) {
        adjList.get(v).add(w);
    }

    void DFS(int startVertex) {
        boolean[] visited = new boolean[V];
        DFSUtil(startVertex, visited);
    }

    private void DFSUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");
        List<Integer> neighbors = adjList.get(v);
        for (Integer neighbor : neighbors) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor, visited);
            }
        }
    }
}

2. 广度优先搜索（BFS）

  • 原理：从图的某个顶点开始，逐层遍历图的顶点，使用队列来记录待访问的顶点。
  • 例子：假设你在一个花园中，要找到一朵特定的花。你从一个起点开始，先检查离起点最近的区域，然后再逐步扩大范围。每次检查完一个区域后，将其周围未检查的区域放入队列中，等待下一轮检查。这个过程就像是广度优先搜索。
  • Java 代码：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Graph {
    private int V;
    private List<List<Integer>> adjList;

    Graph(int v) {
        V = v;
        adjList = new ArrayList<>();
        for (int i = 0; i < v; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    void addEdge(int v, int w) {
        adjList.get(v).add(w);
    }

    void BFS(int startVertex) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        visited[startVertex] = true;
        queue.add(startVertex);
        while (!queue.isEmpty()) {
            int currentVertex = queue.poll();
            System.out.print(currentVertex + " ");
            List<Integer> neighbors = adjList.get(currentVertex);
            for (Integer neighbor : neighbors) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

六、贪心算法

  • 原理：贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
  • 例子：想象你在一个超市购物，你有一个预算，并且想要购买尽可能多的商品。你可以选择价格最低的商品，每次购买一个，直到你的预算用完。这种策略就是贪心算法，虽然不能保证得到全局最优解，但在很多情况下可以得到一个较好的结果。
  • Java 代码：
import java.util.Arrays;
import java.util.Comparator;

class Item {
    int value;
    int weight;

    Item(int value, int weight) {
        this.value = value;
        this.weight = weight;
    }
}

class GreedyAlgorithmExample {
    public static double fractionalKnapsack(Item[] items, int capacity) {
        // 按照价值/重量比进行排序
        Arrays.sort(items, Comparator.comparingDouble(i -> (double) i.value / i.weight));
        double totalValue = 0;
        for (Item item : items) {
            if (capacity >= item.weight) {
                totalValue += item.value;
                capacity -= item.weight;
            } else {
                totalValue += (double) capacity / item.weight * item.value;
                break;
            }
        }
        return totalValue;
    }
}

七、分治算法

  • 原理：分治算法是一种将问题分解成多个小问题，递归解决小问题，然后合并结果以解决原来的问题的方法。
  • 例子：想象你要计算一个大型图书馆中所有书籍的总页数。你可以将图书馆分成几个区域，分别计算每个区域的书籍总页数，然后将这些结果合并起来得到整个图书馆的总页数。
  • Java 代码：
public class DivideAndConquerExample {
    public static int sum(int[] arr, int low, int high) {
        if (low == high) {
            return arr[low];
        }
        int mid = low + (high - low) / 2;
        int leftSum = sum(arr, low, mid);
        int rightSum = sum(arr, mid + 1, high);
        return leftSum + rightSum;
    }
}

八、回溯算法

  • 原理：回溯算法是一种通过试错的方式尝试分步解决问题的算法。如果某一步不满足要求，它会回退到上一步，尝试另一种可能的选择。
  • 例子：想象你在玩一个数独游戏。你从一个空的格子开始，尝试填入一个数字。如果填入的数字导致矛盾，你就回退到上一个格子，尝试另一个数字。这个过程就是回溯算法。
  • Java 代码：
public class SudokuSolver {
    public static boolean solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if (isValid(board, i, j, k)) {
                            board[i][j] = k;
                            if (solveSudoku(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean isValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num || board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num) {
                return false;
            }
        }
        return true;
    }
}

嘿，小伙伴们！看完了这篇博客，是不是对 Java 中的这些基本算法有了更深入的理解呢？快来评论区分享你在使用这些算法时的经验和心得吧！让我们一起在编程的海洋中畅游，共同进步！

标签：arr,Java,int,++,算法,探秘,public
From： https://blog.csdn.net/u010425839/article/details/143275301

相关文章

  • 【设计模式】Java创建型设计模式之工厂模式魔法：打造灵活的冰箱工厂
    标题：《Java工厂模式魔法：打造灵活的冰箱工厂》摘要：本文深入探讨Java中的创建型设计模式之工厂模式。通过一个冰箱工厂的示例，详细解释工厂模式的概念、实现方法以及其带来的好处。读者将了解到如何使用工厂模式创建不同品牌和大小的冰箱，同时体会到该模式在提高代码可维......
  • java基于springboot的助学兼职系统(源码+vue+部署文档+前后端分离等)
    收藏关注不迷路！！......
  • 你不知道的JavaScript（中卷）
    书pan.baidu.com/s/14cPqfkAgg3VLKETfDcoVew?pwd=953k一些关键技术：一、类型和语法JavaScript的内置类型JavaScript有七种内置类型，分别是：null、undefined、boolean、number、string、object和symbol（ES6中新增）。除object之外，其他类型统称为“基本类型”。可以使用typeof运算符......
  • 异步游戏环境下该如何使用强化学习算法进行训练
    在使用强化学习算法进行训练时默认的都是使用同步的游戏环境，即agent手段environment的一个observation后environment是不继续向下执行的而是等待agent返回执行动作后再继续执行的，这种agent和environment在运行时保持着同步串行方式的运行模式则是同步游戏环境，而如果environment发......
  • java计算机毕业设计基于web的青少年编程课程评价系统（开题+程序+论文）
    本系统（程序+源码）带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、研究背景随着信息技术的迅猛发展，编程教育在青少年教育中的地位日益凸显。如今，编程被视为一项关键技能，对青少年的逻辑思维、创造力和问题解决能力有着积极......
  • 低功耗4G模组：RSA算法示例
    ​今天我们学习合宙低功耗4G模组Air780EP_LuatOS_rsa示例，文末【阅读原文】获取最新资料。一、简介RSA算法的安全性基于：将两个大质数相乘很容易，但是想要将其乘积分解成原始的质数因子却非常困难。关联文档和使用工具：LuatOS固件获取rsa-demoLuatools下载调试工具......
  • java计算机毕业设计基于web的校园互助系统设计（开题+程序+论文）
    本系统（程序+源码）带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、研究背景随着互联网技术的飞速发展，Web应用在各个领域的普及程度不断提高。在校园环境中，学生们面临着各种各样的需求，如学习资料共享、生活经验交流、兴趣......
  • java计算机毕业设计基于的冬奥会科普平台（开题+程序+论文）
    本系统（程序+源码）带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、研究背景随着冬奥会的成功举办以及冰雪运动在全球范围内的日益普及，人们对于冬奥会相关知识的需求不断增加。冬奥会包含众多的项目、运动员、赛事历史等丰......
  • java计算机毕业设计在线阅读（开题+程序+论文）
    本系统（程序+源码）带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容一、研究背景随着互联网技术的不断发展，人们的阅读习惯发生了巨大的转变。传统的纸质阅读逐渐向在线阅读过渡，这种转变不仅是技术进步的结果，更是社会发展和人们......
  • Java 中的动态语言支持是什么？
    在Java中，动态语言支持主要是指Java虚拟机（JVM）对非Java语言的支持，让开发者能够在JVM平台上使用其他动态语言进行开发。这一支持通过Java语言中的`invokedynamic`指令实现，该指令于Java7中引入、提高了JVM对动态类型语言的执行效率。动态语言支持的核心要素包括动态类型的语言运行时......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99