🎯目的：
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 stub Scanner 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方法：
分析：
- power方法是一个递归方法，其参数为底数a和指数n。如果n等于0，则返回1，因为任何数的0次方都等于1。
- 如果n不等于0，则继续递归计算power(a,n/2)的值，即将指数除以2，以此来减少递归次数。
- 如果n是偶数，则直接返回temp*temp的值，即将计算结果平方。
- 如果n是奇数，则需要再乘上a，即返回atemptemp的值。
- 最终在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方法：
分析：
- 定义了一个名为One的Java类，并在其中实现了main()方法。
- 定义了一个整数数组arr，并初始化为{9,10,44,33,4,15}。
- 使用Arrays.toString()方法将数组转换为字符串，并输出排序前的序列。
- 调用quickSort()方法对数组进行排序。
- 使用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)); }
💻 快速排序算法：
分析：
- 定义了一个名为quickSort()的方法，用于实现快速排序算法。该方法的参数为要排序的数组、起始位置和结束位置。如果起始位置小于结束位置，说明还需要继续排序。
- 调用partition()方法将数组分成两部分，返回枢轴元素的下标pivotIndex。
- 递归调用quickSort()方法对左边的子数组进行排序，即从low到pivotIndex-1。
- 递归调用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); } }
💻 分割数组：
分析：
- 定义了一个名为partition()的方法，用于将数组分成两部分，左边的部分小于枢轴元素，右边的部分大于等于枢轴元素。该方法的参数为要排序的数组、起始位置和结束位置。
- 将枢轴元素设为数组的最后一个元素arr[high]。
- 定义一个指针i，指向数组的起始位置low-1。
- 使用for循环遍历数组中从low到high-1的所有元素arr[j]。
- 如果arr[j]小于枢轴元素pivot，则将i指针向右移动一位，并交换arr[i]和arr[j]的值，以确保左边的部分都小于枢轴元素。
- 将枢轴元素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; }
🎯总结分治算法的特点：
分治算法是一种常用的问题解决方法，其特点如下：
- 分解（Divide）：将原问题划分为若干个子问题，每个子问题的规模较小且结构与原问题相似。
- 解决（Conquer）：递归地解决每个子问题。如果子问题规模足够小，可以直接求解。
- 合并（Combine）：将子问题的解合并成原问题的解。
分治算法的特点有以下几个方面：
1.适用性广泛：分治算法适用于解决各种类型的问题，包括排序、搜索、图算法等。只要问题可以被划分成若干个规模较小的子问题，并且这些子问题的解可以合并成原问题的解，就可以使用分治算法。
2.提高效率：通过将问题划分为多个子问题并并行处理，分治算法可以显著提高问题的解决效率。子问题之间相互独立，可以同时进行计算，从而充分利用计算资源。
3.递归思想：分治算法通常使用递归来解决子问题。递归调用使得问题的规模逐渐减小，直到达到基本情况，然后再逐步合并子问题的解来得到原问题的解。
4.分解与合并的开销：分治算法的效率也受到分解和合并操作的影响。如果分解和合并操作的开销较大，可能会导致算法效率下降。
5.空间复杂度：分治算法通常需要额外的空间来存储子问题的解，因此在空间复杂度上可能会有一定的开销。
总的来说，分治算法通过将问题划分为多个子问题，并递归地解决这些子问题，然后将子问题的解合并成原问题的解，从而高效地解决复杂的问题。它是一种重要的算法思想，被广泛应用于各个领域。
