程序员都会的五大算法之分治算法，恶补

　　一、算法概述
　　分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。二、分治策略的基本思想
　　简单来说，分治算法就是分而治之，即就是讲一个规模很大很复杂的问题分成若干份相同或相似的更小的子问题，直到最后可以简单的直接求解，将所有子问题的解合并即得到原问题的解。
　　此处，需要注意：子问题与原问题的性质相同子问题必须可以独立求解递归停止时，子问题必须能够直接求解三、时间复杂性
　　在分治算法中，假设原问题总规模为n，我们假设分解和合并所用时间为C（n）和D（n），假设W（x）为处理一个规模为x的问题所用的时间。每一个子问题是原问题规模的1a。
　　如果原问题规模最小子问题的规模，既可以直接求解，那么其时间复杂度是一个常数。否则，W（n）aW（na）C（n）D（n）；四、分治精髓
　　分治法的精髓：分将问题分解为规模更小的子问题；治将这些规模更小的子问题逐个击破；合将已解决的子问题合并，最终得出母问题的解；五、经典例子：二分归并排序汉诺塔5。1二分归并排序
　　设计思想：
　　1、将规模为n的原问题划分为规模为n2的子问题；2、继续划分，划分至规模为n4的，继续一直到规模为1，可以直接求解，这块分治就结束了；3、从规模1到n2依次陆续归并排好序的子数组，直到原始数组。
　　伪代（pseudocode）：
　　算法MergeSort（A，p，r）
　　输入：数组A〔p。。。。。。r〕
　　输出：元素按从小到大排序的数组A1。ifpr2。thenq（pr）2问题规模划分3。MergeSort（A，p，q）子问题14。MergeSort（A，q1，r）子问题25。Merge（A，p，q，r）综合解
　　程序代码实现（Java实现）：publicstaticvoidmergeSort（int〔〕nums，intbegin，intend）｛intlengthendbegin1；if（length1）｛｝分intmid（beginend）2；mergeSort（nums，begin，mid）；mergeSort（nums，mid1，end）；治merge（nums，begin，mid，end）；｝publicstaticvoidmerge（int〔〕nums，intbegin，intmid，inrend）｛if（midend）｛｝intlengthendbegin1；int〔〕tempnewint〔length〕；intk0；intjmid1；while（imidjend）｛if（num〔i〕num〔j〕）｛temp〔k〕num〔i〕；i；｝else｛temp〔k〕num〔j〕；j；｝k；｝传进来前部分已经排完序if（imid）｛while（jend）｛temp〔k〕nums〔j〕；j；k；｝｝if（jend）｛while（imid）｛temp〔k〕num〔i〕；i；k｝｝重新存进原数组for（intm0；m）｛num〔beginm〕temp〔m〕；｝｝
　　图解：
　　时间复杂度分析：
　　假设原问题规模为n，二分归并排序最坏情况：W（n）2W（n2）n1其中子问题最小规模为1，W（1）1；
　　W（n）nlognn1时间复杂度为O（nlogn）5。2汉诺塔
　　游戏介绍：
　　在汉诺塔游戏中，有三个塔座：A、B、C。几个大小各不相同，从小到大一次编号的圆盘，每个圆盘中间有一个小孔。最初，所有的圆盘都在A塔座上，其中最大的圆盘在最下面，然后是第二大，以此类推。
　　汉诺塔示意
　　该游戏的目的是将所有的圆盘从A塔移到B塔；C塔用来放置临时圆盘，游戏的规则如下：一次只能移动一个圆盘任何时候都不能将一个较大的圆盘压在较小的圆盘上面。除了第二条限制，任何塔座的最上面的圆盘都可以移动到其他塔座上。
　　设计思想：始终将较小的盘当做是一个整体
　　游戏完成过程：
　　在上述图中：我们将盘子由小到大分别记为1，2，3，4，5。
　　先将1挪到B，2挪到C，再将1从B挪到C，此时A上有3，4，5，B为空，C上有1，2。
　　再将3挪到B，C上的1也挪到A，C上的2挪到B，A上的1再挪到B，此时A上有45，B上有123，C为空
　　再将4挪到C，B上的1挪到A，B上的2移到C上，A上的1挪到C上，B上的3挪到A上，C上面的1挪到B上，有1234
　　最后将
　　伪码（pesudocode）：
　　算法Hanoi（A，C，n）n个盘子从A到C1。ifn1thenmove（A，C）2。elseHanoi（A，B，n1）3。move（A，C）4。Hanoi（B，C，n1）设n个盘子的移动次数为T（n）T（n）2T（n1）1T（1）1
　　程序：publicstaticvoidsolve（intn）｛hanoi（n，A，B，C）；｝privatestaticvoidhanoi（intn，Stringa，Stringb，Stringc）｛if（n1）｛move（n，a，c）；｝else｛hanoi（n1，a，c，b）；将前n1个圆盘从a挪到c，借助bmove（n，a，c）；将第n个直接移到chanoi（n1，b，a，c）；将前n1个圆盘从b挪到c，借助啊｝｝privatestaticvoidmove（intn，Stringi，Stringj）｛Systtem。out。println（第n个盘，从i塔移动到j塔）；｝
　　时间复杂度分析：
　　hanoi塔游戏的递推公式为T（n）2T（n1）1，时间复杂度为O（2n）六、分治法联系（C语言）6。1求一组数据中最大的两个数和最小的两个数
　　输入输出实例：10代表10个数13579108642max110max29min11min22
　　代码实现：includestdio。hvoidmaxtwo（int〔〕，int，int，int，int）；voidmintwo（int〔〕，int，int，int，int）；intmain（）｛intnum，i；scanf（d，num）；inta〔num〕；for（i0；i）scanf（d，a〔i〕）；Beginintmax1，max2，min1，min2；maxtwo（a，0，num1，max1，max2）；printf（max1dmax2d，max1，max2）；mintwo（a，0，num1，min1，min2）；printf（min1dmin2d，min1，min2）；End｝voidmaxtwo（inta〔〕，inti，intj，intmax1，intmax2）｛intlmax1，lmax2，rmax1，rmax2；if（ij）｛max1a〔i〕；max2a〔i〕；｝elseif（ij2）｛if（a〔i〕a〔i1〕a〔i1〕a〔i2〕）｛max1a〔i〕；max2a〔i1〕；｝elseif（a〔i〕a〔i2〕a〔i2〕a〔i1〕）｛max1a〔i〕；max2a〔i2〕；｝elseif（a〔i1〕a〔i〕a〔i〕a〔i2〕）｛max1a〔i1〕；max2a〔i〕；｝elseif（a〔i1〕a〔i2〕a〔i2〕a〔i〕）｛max1a〔i1〕；max2a〔i2〕；｝elseif（a〔i2〕a〔i〕a〔i〕a〔i1〕）｛max1a〔i2〕；max2a〔i〕；｝else｛max1a〔i2〕；max2a〔i1〕；｝｝else｛mid（ij）2；maxtwo（a，i，mid，lmax1，lmax2）；maxtwo（a，mid1，j，rmax1，rmax2）；if（lmax1rmax1）｛max1lmax1；if（lmax2rmax2）｛max2lmax2；｝else｛max2rmax1；｝｝else｛max1rmax1；if（rmax2lmax2）｛max2rmax2；｝else｛max2lmax1；｝｝｝｝voidmintwo（inta〔〕，inti，intj，intmin1，intmin2）｛intlmin1，lmin2，rmin1，rmin2；if（ij）｛min1a〔i〕；min2a〔i〕；｝elseif（ij2）｛if（a〔i〕a〔i1〕a〔i1〕a〔i2〕）｛min1a〔i〕；min2a〔i1〕；｝elseif（a〔i〕a〔i2〕a〔i2〕a〔i1〕）｛min1a〔i〕；min2a〔i2〕；｝elseif（a〔i1〕a〔i〕a〔i〕a〔i2〕）｛min1a〔i1〕；min2a〔i〕；｝elseif（a〔i1〕a〔i2〕a〔i2〕a〔i〕）｛min1a〔i1〕；min2a〔i2〕；｝elseif（a〔i2〕a〔i〕a〔i〕a〔i1〕）｛min1a〔i2〕；min2a〔i〕；｝else｛min1a〔i2〕；min2a〔i1〕；｝｝else｛mid（ij）2；mintwo（a，i，mid，lmin1，lmin2）；mintwo（a，mid1，j，rmin1，rmin2）；if（lmin1rmin1）｛min1lmin1；if（lmin2rmin2）｛min2lmin2；｝else｛min2rmin1；｝｝else｛min1rmin1；if（rmin2lmin2）｛min2rmin2；｝else｛min2lmin1；｝｝｝｝6。2分治法求一组数据的和
　　输入输出示例：8代表8个数18381687277431100分治法求出数组元素的和为：229
　　代码实现：includestdio。hBeginintcalculatesum（int〔〕，int，int）；intmain（）｛inti，num，scanf（d，num）；inta〔num〕；for（i0；i）｛scanf（d，a〔i〕）；｝sumcalculatesum（a，0，num1）；printf（分治法求出数组元素的和为：d，sum）；｝Endintcalculatesum（inta〔〕，inti，intj）｛intmid，leftsum，if（ij）｛returna〔i〕；｝elseif（j11）｛returna〔i〕a〔j〕；｝else｛mid（ij）2；leftsumcalculatesum（a，i，mid）；rightsumcalculatesum（a，mid1，j）；｝｝6。3求一组数据中第k小的数
　　输入输出示例：105代表10个数据，求第5个小的元素34955067738138101170第5小的元素是10
　　代码实现：includestdio。hdefineArrLen20voidmergeSort（int〔〕，int，int）；voidmerge（int〔〕，int，int，int）；intmain（）｛inti，num，k；scanf（dd，num，k）；inta〔num〕；for（i0；i）｛scanf（d，a〔i〕）；｝mergeSort（a，0，num1）；printf（第d小的元素是d，k，a〔k1〕）；return0；｝voidmerge（intarr〔〕，intstart，intmid，intend）｛intresult〔ArrLen〕；intk0；intjmid1；while（imidjend）｛if（arr〔i〕arr〔j〕）｛result〔k〕arr〔i〕；｝else｛result〔k〕arr〔j〕；｝｝if（imid1）｛while（jend）result〔k〕arr〔j〕；｝if（jend1）｛while（imid）result〔k〕arr〔i〕；｝for（j0，i，j）｛arr〔i〕result〔j〕；｝｝voidmergeSort（intarr〔〕，intstart，intend）｛if（startend）intmid（startend）2；mergeSort（arr，start，mid）；mergeSort（arr，mid1，end）；merge（arr，start，mid，end）；｝