Java分治算法

时间:2022-06-03 LNORA 人气:0

分治算法

什么是分治算法

顾名思义就是分而治之，分治法可以用来解决各种问题，是一种将复杂难解的问题分割成规模和结构相同或者相似的子问题，通过对简单子问题的求解而达到对原问题的求解目的的算法设计方法，在求解一个复杂问题时可以将其分解成若干个子问题，子问题还可以进一步分解成更小的子子问题，直到解决的子问题是一些基本的问题，并且求解方法是已知的，可以直接求解为止。分而治之的策略不但能够使原本复杂的问题变得更加清晰，而且能够将问题的规模缩小而降低问题求解的难度。

分治算法的思想

对于一个规模较大的问题，可以将这个规模较大的问题分解为n个规模较小的相互独立且与原问题结构相同的子问题进行求解。首先通过递归来解决这些子问题，然后对子问题的解进行合并得到原问题的解，这中求解问题的思路就是分治法。

简单可以理解为

首先将原问题分解为若干个子问题

各子问题的结构基本相似，规模基本相当

递归使分治的工具

递归调用：问题和子问题的分解
递归约束：对子问题的解进行合并

分治法四大基本特征

原问题的规模缩小到一定程度时可以很容易的被求解。
原问题可以分解成若干个规模较小的同构子问题。这是使用分治法的前提，这个特征和递归的思想差不多，满足这个特征的问题通常称这个问题具有最优子结构性质。
各问题的解可以合并为原问题的解
原问题所分出的各个子问题之间是相互独立的，即子问题之间不包含公共的子问题，

分治法求解问题的三个基本步骤

分解(递归调用)：将原问题分解为若干个相互独立，规模较小且与原问题形式相同的一系列子问题。在使用分治算法时，最好使各子问题的规模大致相同。
解决(对子问题求解)：如果子问题的规模小到可以直接被解决则直接解决，否则需要递归求解各个子问题。
合并(递归约束)：将各个子问题的结果合并成原问题的解，有些问题的合并方法比较明显，有些问题的合并方法比较复杂，或者存在多种合并方案，有些问题的合并方案并不明显需要具体问题具体分析。

分治算法解决问题过程的伪代码

divide-and-conquer(p)//阀值
{
if(|p|<n0)adhoc(p);//如果问题可以直接求解，就直接求解。|p|代表问题的规模
divide p into amaller subinstances P1,P2,P3......Pk;//将原问题分解成k个规模较小的子问题，且这些子问题的规模相当结构相似
for(i=1;i<=k;i++)
yi=divide-and-conquer(p)//递归求解各个子问题Pi,若分解的子问题还可以分解成若干个子子问题，就再对子问题进行分解
return merge(y1,y2,y3......yk)//将子问题的解合并成原问题的解
}

关于分治算法的举例

归并排序

归并排序算法是用分治策略实现对规模为n的记录序列进行排序的算法，基本思想是：待排序记录分成大小大致相同的两个或多个子集合，分别对子集合进行排序，最终将两个排序号的子集合合并成所要求的排序好的集合。

package 算法设计与分析;
 public class 归并排序 {
 //arr是存放原始元素的数组，left数组arr的最左边，left是数组的最右边，mid是划分的终点，数组tmp是一个临时数组，就是一个辅助存储空间
         public static void main(String[] args) {
             int[] arr = {49,38,65,97,76,13,27};
             int[] tmp = new int[arr.length];    //新建一个临时数组存放,相当于是一个辅助空间
             mergeSort(arr,0,arr.length-1,tmp);
             for(int i=0;i<arr.length;i++){
                 System.out.print(arr[i]+" ");
             }
         }
         public static void merge(int[] arr,int left,int mid,int right,int[] tmp){
             int i = 0;
             int j = left,k = mid+1;  //左边序列和右边序列起始索引
             while(j <= mid && k <= right){
                 if(arr[j] <= arr[k]){
                     tmp[i++] = arr[j++];
                 }else{
                     tmp[i++] = arr[k++];
                 }
             }
             //若左边序列还有剩余，则将其全部拷贝进tmp[]中
             while(j <= mid){
                 tmp[i++] = arr[j++];
             }
             while(k <= right){
                 tmp[i++] = arr[k++];
             }
             for(int t=0;t<i;t++){
                 arr[left+t] = tmp[t];
             }
         }
         public static void mergeSort(int[] arr,int left,int right,int[] tmp){
             if(left<right){
                 int mid = (left+right)/2;
                 mergeSort(arr,left,mid,tmp); //对左边序列进行归并排序
                 mergeSort(arr,mid+1,right,tmp);  //对右边序列进行归并排序
                 merge(arr,left,mid,right,tmp);    //合并两个有序序列，相当于用tmp覆盖原来的arr
             }
         }
     }

基本步骤

划分中点mid；
分别对左右子区间归并排序，归并的结果(是一个有序序列)存放在数组tmp中，tmp是一个临时数组，相当于一个辅助存储空间；
用tmp去覆盖原来的数组arr。

快速排序

快速排序又称为交换排序，是冒泡排序的一种，在快速排序中，记录的比较和交换是从两端向中间进行的，关键字值较大的记录一次就能交换到后面单元，关键字值小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。

思想：把最左边的元素作为主元，数组一左一右两个指针进行扫描，左边的指针直到找到一个元素比主元大时，便停止左移，右边的指针向左移动，直到找到一个不大于主元的元素，交换两个指针所指向的元素。

注意：这种排序要在左边设置一个较大的值作为哨兵，防止左指针在右移的过程中移出序列之外。

package 算法设计与分析;
 public class 快速排序 {
         public static void quickSort(int[] arr,int left,int right){
             int i,j,temp,t;
             if(left>right){
                 return;
             }
             i=left;
             j=right;
             //temp就是基准位,就是主元，将数组中的第一个元素作为主元
             temp = arr[left];
             while (i<j) {
                 //先看右边，依次往左递减
                 while (temp<=arr[j]&&i<j) {
                     j--;
                 }
                 //再看左边，依次往右递增
                 while (temp>=arr[i]&&i<j) {
                     i++;
                 }
                 //如果满足条件则交换
                 if (i<j) {
                     t = arr[j];
                     arr[j] = arr[i];
                     arr[i] = t;
                 }
             }
             //最后将基准为与i和j相等位置的数字交换
             arr[left] = arr[i];
             arr[i] = temp;
             //递归调用左半数组
             quickSort(arr, left, j-1);
             //递归调用右半数组
             quickSort(arr, j+1, right);
         }
         public static void main(String[] args){
             int[] arr = {72,26,57,88,42,80,72,48,60,};
             quickSort(arr, 0, arr.length-1);
             for (int i = 0; i < arr.length; i++) {
                 System.out.print(arr[i]+ " ");
             }
         }
     }

二分搜索算法

在一个表中搜索确定一个关键字值为给定的元素，若在表中存在这样的元素，则搜索成功，搜索结果可以返回整个数据的元素，也可以指示该元素在表中的位置，若表中不存在关键字值的元素，则搜索失败。

 package 算法设计与分析;
 //用递归的方法解决二分搜索问题
 public class 二分查找 {
     public static void main(String[] args) {
         int[] arr = {-7,-2,0,15,27,54,80,88,102};
         //想要查找的元素
         int key = 80;
         //对查找到的元素进行定位
         int position = Search(arr,key,0,arr.length - 1);
         if(position == -1){
             System.out.println("查找的是"+key+",序列中没有该数！");
         }else{
             System.out.println("查找的是"+key+",找到位置为："+position);
         }
     }
     public static int Search(int[] arr,int key,int left,int right){
         if(key < arr[left] &&key > arr[right] &&left > right){
             return -1;
         }
         int middle = (left + right) / 2;            //初始中间位置
         if(arr[middle] > key){
             //比关键字大则关键字在左区域
             return Search(arr, key, left, middle - 1);
         }else if(arr[middle] < key){
             //比关键字小则关键字在右区域
             return Search(arr, key, middle + 1, right);
         }else {
             return middle;
         }
     }
 }

小结

以上就是针对分治算法的详细分析，分治算法在我们解决问题的过程中可以使我们的问题变得简单化，降低时间复杂度，利用分治法解决问题比较稳定。

加载全部内容