顾名思义就是分而治之，分治法可以用来解决各种问题，是一种将复杂难解的问题分割成规模和结构相同或者相似的子问题，通过对简单子问题的求解而达到对原问题的求解目的的算法设计方法，在求解一个复杂问题时可以将其分解成若干个子问题，子问题还可以进一步分解成更小的子子问题，直到解决的子问题是一些基本的问题，并且求解方法是已知的，可以直接求解为止。分而治之的策略不但能够使原本复杂的问题变得更加清晰，而且能够将问题的规模缩小而降低问题求解的难度。
分治算法的思想对于一个规模较大的问题，可以将这个规模较大的问题分解为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的记录序列进行排序的算法，基本思想是：待排序记录分成大小大致相同的两个或多个子集合，分别对子集合进行排序，最终将两个排序号的子集合合并成所要求的排序好的集合。
基本步骤 划分中点mid；分别对左右子区间归并排序，归并的结果(是一个有序序列)存放在数组tmp中，tmp是一个临时数组，相当于一个辅助存储空间；用tmp去覆盖原来的数组arr。 快速排序快速排序又称为交换排序，是冒泡排序的一种，在快速排序中，记录的比较和交换是从两端向中间进行的，关键字值较大的记录一次就能交换到后面单元，关键字值小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。
思想：把最左边的元素作为主元，数组一左一右两个指针进行扫描，左边的指针直到找到一个元素比主元大时，便停止左移，右边的指针向左移动，直到找到一个不大于主元的元素，交换两个指针所指向的元素。
注意：这种排序要在左边设置一个较大的值作为哨兵，防止左指针在右移的过程中移出序列之外。
二分搜索算法在一个表中搜索确定一个关键字值为给定的元素，若在表中存在这样的元素，则搜索成功，搜索结果可以返回整个数据的元素，也可以指示该元素在表中的位置，若表中不存在关键字值的元素，则搜索失败。
小结以上就是针对分治算法的详细分析，分治算法在我们解决问题的过程中可以使我们的问题变得简单化，降低时间复杂度，利用分治法解决问题比较稳定。
到此这篇关于Java举例讲解分治算法思想的文章就介绍到这了,更多相关Java分治算法内容请搜索七叶笔记以前的文章或继续浏览下面的相关文章希望大家以后多多支持七叶笔记！
