【算法设计与分析】—— 分治算法

🎃个人专栏：

🐬 算法设计与分析：算法设计与分析_IT闫的博客-CSDN博客

🐳Java基础：Java基础_IT闫的博客-CSDN博客

🐋c语言：c语言_IT闫的博客-CSDN博客

🐟MySQL：数据结构_IT闫的博客-CSDN博客

🐠数据结构：​​​​​​数据结构_IT闫的博客-CSDN博客

💎C++：C++_IT闫的博客-CSDN博客

🥽C51单片机：C51单片机（STC89C516）_IT闫的博客-CSDN博客

💻基于HTML5的网页设计及应用：基于HTML5的网页设计及应用_IT闫的博客-CSDN博客​​​​​​

🥏python：python_IT闫的博客-CSDN博客

欢迎收看，希望对大家有用！

目录

🎯目的：

🎯问题及代码分析：

🥽1）二分查找的实现：

🎃代码及解析：

💻导入必要的类：

💻 创建 One 类：

💻 在 main 方法中执行二分查找：

💻 binarySearchHelper 方法实现二分查找：

🥽2）最小值问题：求n个元素的最小值：

🎃代码及解析：

💻导入必要的类：

💻 创建 One 类：

💻 在 main 方法中执行查找最小值操作：

💻 findMinmumHelper 方法实现递归查找最小值：

🥽3）幂乘问题： 给定实数a和自然数n，求a^n:

🎃代码及解析：

💻导入了Scanner类：

 💻main函数：

💻power方法：

🥽快速排序的实现：

🎃代码及解析：

💻导入了java.util.Arrays类：

 💻main方法：

💻 快速排序算法：

 💻 分割数组：

💻 交换数组中两个元素的位置：

 🎯总结分治算法的特点：

🎯注：所有完整代码：

---

🎯目的：

1）了解分治策略算法思想及基本原理；

2）掌握使用分治算法求解问题的一般特征；

3）掌握分解、治理的方法；

4）能够针对实际问题，能够正确的分解、治理，设计分治算法；

5）能够正确分析算法的时间复杂度和空间复杂度。

🎯问题及代码分析：

🥽1）二分查找的实现：

🎃代码及解析：

💻导入必要的类：

分析：这行代码导入了 java.util.Scanner 类，用于从控制台读取用户的输入。

import java.util.Scanner;

💻 创建 One 类：

分析：这段代码定义了一个名为 One 的公共类，并包含了 main 方法和 binarySearchHelper 方法。

public class One {public static void main(String[] args) {// ...}public static int binarySearchHelper(int[] arr, int target, int low, int high) {// ...}
}

💻 在 main 方法中执行二分查找：

分析：

        这段代码首先创建了一个 Scanner 对象 scan，用于读取用户的输入。然后，定义了一个有序整数数组 arr，其中包含了数字 1、3、4、7、8 和 10。

        接下来，通过 System.out.println 打印提示信息，要求用户输入一个在 10 以内的数字。然后，使用 scan.nextInt() 从控制台读取用户输入的目标数字，并将其存储在变量 target 中。

        最后，调用 binarySearchHelper 方法进行二分查找，传入数组 arr、目标数字 target、数组的起始索引 0 和结束索引 arr.length - 1。根据返回的索引值，打印相应的结果。

Scanner scan = new Scanner(System.in);
int[] arr = {1, 3, 4, 7, 8, 10};
System.out.println("请输入您要查找的10以内的数字：");
int target = scan.nextInt();
int index = binarySearchHelper(arr, target, 0, arr.length - 1);
if (index < 0) {System.out.println("您输入的数字查找不到！");
} else {System.out.println("输入数字对应为索引为：" + index);
}

💻 binarySearchHelper 方法实现二分查找：

分析：

这段代码定义了一个递归方法 binarySearchHelper，用于在给定的有序整数数组 arr 中查找目标数字 target。方法接受四个参数：数组 arr、目标数字 target、数组的起始索引 low 和结束索引 high。

在方法中，首先检查起始索引是否大于结束索引，如果是，则表示目标数字不在数组中，返回 -1。

否则，计算中间索引 mid，并检查中间元素是否等于目标数字。如果是，返回中间索引 mid。

如果中间元素大于目标数字，则递归调用 binarySearchHelper 方法，在左半部分数组中继续查找目标数字。

如果中间元素小于目标数字，则递归调用 binarySearchHelper 方法，在右半部分数组中继续查找目标数字。

这样，通过递归调用，最终会找到目标数字的索引值或返回 -1，表示目标数字不存在于数组中。

public static int binarySearchHelper(int[] arr, int target, int low, int high) {if (low > high) {return -1;}int mid = (low + high) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] > target) {return binarySearchHelper(arr, target, low, mid - 1);} else {return binarySearchHelper(arr, target, mid + 1, high);}
}

---

🥽2）最小值问题：求n个元素的最小值：

🎃代码及解析：

💻导入必要的类：

分析：这行代码导入了 java.util.Arrays 类，用于打印数组的内容。

import java.util.Arrays;

💻 创建 One 类：

分析：这段代码定义了一个名为 One 的公共类，并包含了 main 方法和 findMinmumHelper 方法。

public class One {public static void main(String[] args) {// ...}public static int findMinmumHelper(int[] arr, int low, int high) {// ...}
}

💻 在 main 方法中执行查找最小值操作：

分析：

这段代码首先定义了一个整型数组 arr，其中包含了一些整数。

接下来，调用 findMinmumHelper 方法进行查找最小值的操作，传入数组 arr、起始索引 0 和结束索引 arr.length - 1。将返回的最小值存储在变量 x 中。

最后，使用 System.out.println 打印数组的内容和最小值。

int[] arr = {90, 40, 50, 10, 99, 20};
int x = findMinmumHelper(arr, 0, arr.length - 1);
System.out.println("在数组" + Arrays.toString(arr));
System.out.println("最小值为:" + x);

💻 findMinmumHelper 方法实现递归查找最小值：

分析：

这段代码定义了一个递归方法 findMinmumHelper，用于在给定的数组 arr 中查找最小值。方法接受三个参数：数组 arr、起始索引 low 和结束索引 high。

在方法中，首先检查起始索引和结束索引是否相等，如果相等，则表示只有一个元素，直接返回该元素作为最小值。

否则，计算中间索引 mid，并分别递归调用 findMinmumHelper 方法，在左半部分数组和右半部分数组中查找最小值。

最后，使用 Math.min 方法比较左半部分数组的最小值 leftMin 和右半部分数组的最小值 rightMin，返回较小的值作为整个数组的最小值。

public static int findMinmumHelper(int[] arr, int low, int high) {if (low == high) {return arr[low];}int mid = (low + high) / 2;int leftMin = findMinmumHelper(arr, low, mid);int rightMin = findMinmumHelper(arr, mid + 1, high);return Math.min(leftMin, rightMin);
}

---

🥽3）幂乘问题： 给定实数a和自然数n，求a^n:

🎃代码及解析：

💻导入了Scanner类：

import java.util.Scanner;

 💻main函数：

分析：

 在main方法中，通过Scanner类获取用户输入的a和n的值，并调用power方法计算a的n次方。

	public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);System.out.println("请输入a的值：");int a=scan.nextInt();System.out.println("请输入数字n的值");int n=scan.nextInt();int x=power(a,n);System.out.println(a+"的"+n+"次方为："+x);}

💻power方法：

分析：

1. power方法是一个递归方法，其参数为底数a和指数n。如果n等于0，则返回1，因为任何数的0次方都等于1。

2. 如果n不等于0，则继续递归计算power(a,n/2)的值，即将指数除以2，以此来减少递归次数。

3. 如果n是偶数，则直接返回temp*temp的值，即将计算结果平方。

4. 如果n是奇数，则需要再乘上a，即返回atemptemp的值。

5. 最终在main方法中输出计算结果。

	public static int power(int a,int n){if(n==0) {return 1;}int temp=power(a,n/2);if(n%2==0) {return temp*temp;}else {return a*temp*temp;}}
}

---

🥽快速排序的实现：

🎃代码及解析：

💻导入了java.util.Arrays类：

import java.util.Arrays;

 💻main方法：

分析：

1. 定义了一个名为One的Java类，并在其中实现了main()方法。

2. 定义了一个整数数组arr，并初始化为{9,10,44,33,4,15}。

3. 使用Arrays.toString()方法将数组转换为字符串，并输出排序前的序列。

4. 调用quickSort()方法对数组进行排序。

5. 使用Arrays.toString()方法将数组转换为字符串，并输出排序后的序列

    public static void main(String[] args) {int [] arr= {9,10,44,33,4,15};System.out.println("排序前的序列为："+Arrays.toString(arr));quickSort(arr,0,arr.length-1);System.out.println("排序后的序列为："+Arrays.toString(arr));}

💻 快速排序算法：

分析：

1. 定义了一个名为quickSort()的方法，用于实现快速排序算法。该方法的参数为要排序的数组、起始位置和结束位置。如果起始位置小于结束位置，说明还需要继续排序。

2. 调用partition()方法将数组分成两部分，返回枢轴元素的下标pivotIndex。

3. 递归调用quickSort()方法对左边的子数组进行排序，即从low到pivotIndex-1。

4. 递归调用quickSort()方法对右边的子数组进行排序，即从pivotIndex到high。

    public static void quickSort(int [] arr,int low,int high) {if(low <high) {int  pivotIndex=partition(arr,low,high);quickSort(arr, low,pivotIndex-1);quickSort(arr, pivotIndex, high);}}

 💻 分割数组：

分析：

1. 定义了一个名为partition()的方法，用于将数组分成两部分，左边的部分小于枢轴元素，右边的部分大于等于枢轴元素。该方法的参数为要排序的数组、起始位置和结束位置。

2. 将枢轴元素设为数组的最后一个元素arr[high]。

3. 定义一个指针i，指向数组的起始位置low-1。

4. 使用for循环遍历数组中从low到high-1的所有元素arr[j]。

5. 如果arr[j]小于枢轴元素pivot，则将i指针向右移动一位，并交换arr[i]和arr[j]的值，以确保左边的部分都小于枢轴元素。

6. 将枢轴元素pivot与arr[i+1]交换位置，并返回i+1作为新的枢轴元素下标。

    public 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++;swap(arr,i,j);}}swap(arr,i+1,high);return i+1;}

💻 交换数组中两个元素的位置：

分析：

定义了一个名为swap()的方法，用于交换数组中两个元素的位置。该方法的参数为要交换的数组和两个元素的下标。

    public static void swap(int [] arr,int i,int j) {int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}

---

 🎯总结分治算法的特点：

分治算法是一种常用的问题解决方法，其特点如下：

1. 分解（Divide）：将原问题划分为若干个子问题，每个子问题的规模较小且结构与原问题相似。

2. 解决（Conquer）：递归地解决每个子问题。如果子问题规模足够小，可以直接求解。

3. 合并（Combine）：将子问题的解合并成原问题的解。

分治算法的特点有以下几个方面：

1. 适用性广泛：分治算法适用于解决各种类型的问题，包括排序、搜索、图算法等。只要问题可以被划分成若干个规模较小的子问题，并且这些子问题的解可以合并成原问题的解，就可以使用分治算法。

2. 提高效率：通过将问题划分为多个子问题并并行处理，分治算法可以显著提高问题的解决效率。子问题之间相互独立，可以同时进行计算，从而充分利用计算资源。

3. 递归思想：分治算法通常使用递归来解决子问题。递归调用使得问题的规模逐渐减小，直到达到基本情况，然后再逐步合并子问题的解来得到原问题的解。

4. 分解与合并的开销：分治算法的效率也受到分解和合并操作的影响。如果分解和合并操作的开销较大，可能会导致算法效率下降。

5. 空间复杂度：分治算法通常需要额外的空间来存储子问题的解，因此在空间复杂度上可能会有一定的开销。

        总的来说，分治算法通过将问题划分为多个子问题，并递归地解决这些子问题，然后将子问题的解合并成原问题的解，从而高效地解决复杂的问题。它是一种重要的算法思想，被广泛应用于各个领域。

🎯注：所有完整代码：

🥏可以关注私信博主，博主可以给友友们发！💛