第Java舉例講解分治算法思想目錄分治算法什么是分治算法分治算法的思想分治法四大基本特征分治法求解問題的三個(gè)基本步驟分治算法解決問題過程的偽代碼關(guān)于分治算法的舉例歸并排序基本步驟快速排序二分搜索算法小結(jié)

分治算法

什么是分治算法

顧名思義就是分而治之，分治法可以用來解決各種問題，是一種將復(fù)雜難解的問題分割成規(guī)模和結(jié)構(gòu)相同或者相似的子問題，通過對(duì)簡單子問題的求解而達(dá)到對(duì)原問題的求解目的的算法設(shè)計(jì)方法，在求解一個(gè)復(fù)雜問題時(shí)可以將其分解成若干個(gè)子問題，子問題還可以進(jìn)一步分解成更小的子子問題，直到解決的子問題是一些基本的問題，并且求解方法是已知的，可以直接求解為止。分而治之的策略不但能夠使原本復(fù)雜的問題變得更加清晰，而且能夠?qū)栴}的規(guī)?？s小而降低問題求解的難度。

分治算法的思想

對(duì)于一個(gè)規(guī)模較大的問題，可以將這個(gè)規(guī)模較大的問題分解為n個(gè)規(guī)模較小的相互獨(dú)立且與原問題結(jié)構(gòu)相同的子問題進(jìn)行求解。首先通過遞歸來解決這些子問題，然后對(duì)子問題的解進(jìn)行合并得到原問題的解，這中求解問題的思路就是分治法。

簡單可以理解為

首先將原問題分解為若干個(gè)子問題

各子問題的結(jié)構(gòu)基本相似，規(guī)?；鞠喈?dāng)

遞歸使分治的工具

遞歸調(diào)用：問題和子問題的分解遞歸約束：對(duì)子問題的解進(jìn)行合并

分治法四大基本特征

原問題的規(guī)?？s小到一定程度時(shí)可以很容易的被求解。原問題可以分解成若干個(gè)規(guī)模較小的同構(gòu)子問題。這是使用分治法的前提，這個(gè)特征和遞歸的思想差不多，滿足這個(gè)特征的問題通常稱這個(gè)問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。各問題的解可以合并為原問題的解原問題所分出的各個(gè)子問題之間是相互獨(dú)立的，即子問題之間不包含公共的子問題，

分治法求解問題的三個(gè)基本步驟

分解(遞歸調(diào)用)：將原問題分解為若干個(gè)相互獨(dú)立，規(guī)模較小且與原問題形式相同的一系列子問題。在使用分治算法時(shí)，最好使各子問題的規(guī)模大致相同。解決(對(duì)子問題求解)：如果子問題的規(guī)模小到可以直接被解決則直接解決，否則需要遞歸求解各個(gè)子問題。合并(遞歸約束)：將各個(gè)子問題的結(jié)果合并成原問題的解，有些問題的合并方法比較明顯，有些問題的合并方法比較復(fù)雜，或者存在多種合并方案，有些問題的合并方案并不明顯需要具體問題具體分析。

分治算法解決問題過程的偽代碼

divide-and-conquer(p)//閥值

{

if(|p|n0)adhoc(p);//如果問題可以直接求解，就直接求解。|p|代表問題的規(guī)模

dividepintoamallersubinstancesP1,P2,P3......Pk;//將原問題分解成k個(gè)規(guī)模較小的子問題，且這些子問題的規(guī)模相當(dāng)結(jié)構(gòu)相似

for(i=1;ii++)

yi=divide-and-conquer(p)//遞歸求解各個(gè)子問題Pi,若分解的子問題還可以分解成若干個(gè)子子問題，就再對(duì)子問題進(jìn)行分解

returnmerge(y1,y2,y3......yk)//將子問題的解合并成原問題的解

}

關(guān)于分治算法的舉例

歸并排序

歸并排序算法是用分治策略實(shí)現(xiàn)對(duì)規(guī)模為n的記錄序列進(jìn)行排序的算法，基本思想是：待排序記錄分成大小大致相同的兩個(gè)或多個(gè)子集合，分別對(duì)子集合進(jìn)行排序，最終將兩個(gè)排序號(hào)的子集合合并成所要求的排序好的集合。

package算法設(shè)計(jì)與分析;

publicclass歸并排序{

//arr是存放原始元素的數(shù)組，left數(shù)組arr的最左邊，left是數(shù)組的最右邊，mid是劃分的終點(diǎn)，數(shù)組tmp是一個(gè)臨時(shí)數(shù)組，就是一個(gè)輔助存儲(chǔ)空間

publicstaticvoidmain(String[]args){

int[]arr={49,38,65,97,76,13,27};

int[]tmp=newint[arr.length];//新建一個(gè)臨時(shí)數(shù)組存放,相當(dāng)于是一個(gè)輔助空間

mergeSort(arr,0,arr.length-1,tmp);

for(inti=0;iarr.length;i++){

System.out.print(arr[i]+"");

publicstaticvoidmerge(int[]arr,intleft,intmid,intright,int[]tmp){

inti=0;

intj=left,k=mid+1;//左邊序列和右邊序列起始索引

while(j=midk=right){

if(arr[j]=arr[k]){

tmp[i++]=arr[j++];

}else{

tmp[i++]=arr[k++];

//若左邊序列還有剩余，則將其全部拷貝進(jìn)tmp[]中

while(j=mid){

tmp[i++]=arr[j++];

while(k=right){

tmp[i++]=arr[k++];

for(intt=0;tt++){

arr[left+t]=tmp[t];

publicstaticvoidmergeSort(int[]arr,intleft,intright,int[]tmp){

if(leftright){

intmid=(left+right)/2;

mergeSort(arr,left,mid,tmp);//對(duì)左邊序列進(jìn)行歸并排序

mergeSort(arr,mid+1,right,tmp);//對(duì)右邊序列進(jìn)行歸并排序

merge(arr,left,mid,right,tmp);//合并兩個(gè)有序序列，相當(dāng)于用tmp覆蓋原來的arr

}

基本步驟

劃分中點(diǎn)mid；分別對(duì)左右子區(qū)間歸并排序，歸并的結(jié)果(是一個(gè)有序序列)存放在數(shù)組tmp中，tmp是一個(gè)臨時(shí)數(shù)組，相當(dāng)于一個(gè)輔助存儲(chǔ)空間；用tmp去覆蓋原來的數(shù)組arr。

快速排序

快速排序又稱為交換排序，是冒泡排序的一種，在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字值較大的記錄一次就能交換到后面單元，關(guān)鍵字值小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。

思想：把最左邊的元素作為主元，數(shù)組一左一右兩個(gè)指針進(jìn)行掃描，左邊的指針直到找到一個(gè)元素比主元大時(shí)，便停止左移，右邊的指針向左移動(dòng)，直到找到一個(gè)不大于主元的元素，交換兩個(gè)指針?biāo)赶虻脑亍?/p>

注意：這種排序要在左邊設(shè)置一個(gè)較大的值作為哨兵，防止左指針在右移的過程中移出序列之外。

package算法設(shè)計(jì)與分析;

publicclass快速排序{

publicstaticvoidquickSort(int[]arr,intleft,intright){

inti,j,temp,t;

if(leftright){

return;

i=left;

j=right;

//temp就是基準(zhǔn)位,就是主元，將數(shù)組中的第一個(gè)元素作為主元

temp=arr[left];

while(ij){

//先看右邊，依次往左遞減

while(temp=arr[j]ij){

j--;

//再看左邊，依次往右遞增

while(temp=arr[i]ij){

i++;

//如果滿足條件則交換

if(ij){

t=arr[j];

arr[j]=arr[i];

arr[i]=t;

//最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換

arr[left]=arr[i];

arr[i]=temp;

//遞歸調(diào)用左半數(shù)組

quickSort(arr,left,j-1);

//遞歸調(diào)用右半數(shù)組

quickSort(arr,j+1,right);

publicstaticvoidmain(String[]args){

int[]arr={72,26,57,88,42,80,72,48,60,};

quickSort(arr,0,arr.length-1);

for(inti=0;iarr.length;i++){

System.out.print(arr[i]+"");

}

二分搜索算法

在一個(gè)表中搜索確定一個(gè)關(guān)鍵字值為給定的元素，若在表中存在這樣的元素，則搜索成功，搜索結(jié)果可以返回整個(gè)數(shù)據(jù)的元素，也可以指示該元素在表中的位置，若表中不存在關(guān)鍵字值的元素，則搜索失敗。

package算法設(shè)計(jì)與分析;

//用遞歸的方法解決二分搜索問題

publicclass二分查找{

publicstaticvoidmain(String[]args){

int[]arr={-7,-2,0,15,27,54,80,88,102};

//想要查找的元素

intkey=80;

//對(duì)查找到的元素進(jìn)行定位

intposition=Search(arr,key,0,arr.length-1);

if(position==-1){

System.out.println("查找的是"+key+",序列中沒有該數(shù)！");

}else{

System.out.println("查找的是"+key+",找到位置為："+position);

publicstaticintSearch(int[]arr,intkey,intleft,intright){

if(keyarr[left]keyarr[right]leftright){

return-1;

intmiddle=(left+right)/2;//初始中間位置

if(arr[middle]key){

//比關(guān)鍵字大則關(guān)鍵字在左區(qū)域

returnSearch(arr,key,l