【写在前面】《Java算法系列》目录如下（更新）：数据结构相关算法八种排序算法：冒泡排序、选择排序、插入排序、希腊语四种搜索算法：首尔排序、快速排序、归并排序、基数排序、堆排序：线性搜索、二分搜索、插值搜索、斐波那契搜索九种常用算法：分治算法、动态规划算法、KMP算法、贪心算法、Prim算法、Kruskal算法、Dijkstra算法、Floyd算法、KnightTravel回溯算法本文是九种常用算法中的分治算法。分而治之算法的步骤分而治之算法在递归的每一层上有三个步骤：分解：将原问题分解为若干个较小的、独立的、与原问题形式相同的子问题。求解：如果子问题小且容易求解，则直接求解；否则，递归地解决每个子问题。合并：将各个子问题的解合并为原问题的解。分治算法经典例子分治算法可以解决的经典问题有：二分查找（待补充）大整数乘法施特拉森矩阵乘法棋盘覆盖归并排序（待补充）快速排序（待补充）线性时间选择最近点对问题RoundrobinscheduleTowerofHanoi下面以“HanoiTowerproblem”为例说明分治算法的思想。汉诺塔问题有A、B、C三个极点，A极点上有若干个盘子，每移动一个盘子，小的只能叠在大的上面。将所有板从A极移动到C极。令n为板的数量。对于n=1的情况，直接将板从A极移动到C极。对于n≥2的情况，问题可以分解为：将n-1块板从A移动到B；将第n个盘子从A移动到C；将n-1个盘子从B移动到C。那么，如何将n-1个磁盘从一个极移到另一个？可以先移动n-2个盘子，再移动第n-1个盘子……这就是分而治之的思想。所以汉诺塔问题的算法很容易写出来：publicclassHanoiTower{publicstaticvoidmain(String[]args){intn=5;hanoiTower(n,'A','B','C');}publicstaticvoidhanoiTower(intnum,chara,charb,charc){//对于n=1，直接将盘子从A极移动到C极。if(num==1){System.out.println("th"+num+"disk:"+a+"->"+c);}//forn≥2else{//把n-1个盘子从A移到B；hanoiTower(num-1,a,c,b);//将第n个盘子从A移动到C；System.out.println("th"+num+"磁盘："+a+"->"+c);//将n-1个圆盘从B移动到C。hanoiTower(num-1,b,a,c);}}}参考上硅谷：Java数据结构与算法分治算法详解及经典实例
