分治法學(xué)習(xí)總結(jié)
分治法是我們經(jīng)常用到的算法紊撕，合理利用分治算法可以使我們更好的解決問題。我們在使用二分查找赡突、歸并排序的時(shí)候都要用到分治算法对扶。下面我將從三個(gè)方面介紹分治算法区赵，方便我們更好的了解和學(xué)習(xí)分治算法。
1.分治算法介紹
2.分治算法應(yīng)用分析
3.分治算法例題分析
1.分治算法介紹
1.基本概念
分治算法的基本思想是將一個(gè)規(guī)模為N的問題分解為K個(gè)規(guī)模較小的子問題浪南，這些子問題相互獨(dú)立且與原問題性質(zhì)相同笼才。求出子問題的解，就可得到原問題的解络凿。即一種分目標(biāo)完成程序算法骡送，簡單問題可用二分法完成。
2.解題思路
1喷众、原問題可以分解為多個(gè)子問題
這些子問題與原問題相比各谚，只是問題的規(guī)模有所降低，其結(jié)構(gòu)和求解方法與原問題相同或相似到千。
2昌渤、原問題在分解過程中，遞歸地求解子問題
由于遞歸都必須有一個(gè)終止條件憔四，因此膀息，當(dāng)分解后的子問題規(guī)模足夠小時(shí)，應(yīng)能夠直接求解了赵。
3潜支、在求解并得到各個(gè)子問題的解后
應(yīng)能夠采用某種方式、方法合并或構(gòu)造出原問題的解柿汛。
不難發(fā)現(xiàn)冗酿，在分治策略中，由于子問題與原問題在結(jié)構(gòu)和解法上的相似性络断，用分治方法解決的問題裁替，大都采用了遞歸的形式。在各種排序方法中貌笨，如歸并排序弱判、堆排序、快速排序等锥惋，都存在有分治的思想 昌腰。
2.分治算法應(yīng)用分析
先讓我們通過一個(gè)簡單的二分查找來理解分治算法的基本思路。
public static int commonBinarySearch(int[] arr,int key){
int low = 0;
int high = arr.length - 1;
int middle = 0; //定義middle
if(key < arr[low] || key > arr[high] || low > high){
return -1;
}
while(low <= high){
middle = (low + high) / 2;
if(arr[middle] > key){
//比關(guān)鍵字大則關(guān)鍵字在左區(qū)域
high = middle - 1;
}else if(arr[middle] < key){
//比關(guān)鍵字小則關(guān)鍵字在右區(qū)域
low = middle + 1;
}else{
return middle;
}
}
return -1; //最后仍然沒有找到膀跌，則返回-1
}
首先先在排序的數(shù)組找到中間值遭商，定義我們的中間值，找到就返回捅伤，找不到就在符合條件的子問題繼續(xù)二分株婴，直到滿足邊界條件退出循環(huán)。
1.歸并排序
歸并排序（MERGE-SORT）是利用歸并的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解困介，而治(conquer)的階段則將分的階段得到的各答案"修補(bǔ)"在一起，即分而治之)蘸际。
第一, 分解: 把待排序的 n 個(gè)元素的序列分解成兩個(gè)子序列, 每個(gè)子序列包括 n/2 個(gè)元素.
第二, 治理: 對每個(gè)子序列分別調(diào)用歸并排序MergeSort, 進(jìn)行遞歸操作
第三, 合并: 合并兩個(gè)排好序的子序列,生成排序結(jié)果.
public static int[] sort(int[] a,int low,int high){
int mid = (low+high)/2;
if(low<high){
sort(a,low,mid);
sort(a,mid+1,high);
//左右歸并
merge(a,low,mid,high);
}
return a;
}
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high-low+1];
int i= low;
int j = mid+1;
int k=0;
// 把較小的數(shù)先移到新數(shù)組中
while(i<=mid && j<=high){
if(a[i]<a[j]){
temp[k++] = a[i++];
}else{
temp[k++] = a[j++];
}
}
// 把左邊剩余的數(shù)移入數(shù)組
while(i<=mid){
temp[k++] = a[i++];
}
// 把右邊邊剩余的數(shù)移入數(shù)組
while(j<=high){
temp[k++] = a[j++];
}
// 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
for(int x=0;x<temp.length;x++){
a[x+low] = temp[x];
}
}
2.快速排序
給定數(shù)組int[]a={7,5,3,2,9,10,8,4,6,1};
第1步：找基準(zhǔn)值
所謂的基準(zhǔn)值座哩，顧名思義就是以它為基準(zhǔn)進(jìn)行比大小。通常來說粮彤，我們選取數(shù)組的第一個(gè)數(shù)為基準(zhǔn)值根穷。在數(shù)組a里基準(zhǔn)值就是7.
第2步：比大小
先從數(shù)組的最右邊開始往左邊找比基準(zhǔn)值小的第一個(gè)數(shù)，然后從數(shù)組的最左邊開始往右找比基準(zhǔn)值大的第一個(gè)數(shù)导坟。那么為什么要這么找呢屿良？因?yàn)楝F(xiàn)在我們要把數(shù)組從小到大排序，所以要找出比基準(zhǔn)值小的數(shù)放到基準(zhǔn)值的左邊惫周，找出比基準(zhǔn)值的數(shù)放在基準(zhǔn)值的右邊尘惧。
那么在數(shù)組a里，從左往右找递递，第一個(gè)比7大的數(shù)就是9喷橙，我們把它的坐標(biāo)記為i；從右往左找登舞，第一個(gè)比7小的數(shù)就是1贰逾，我們把它的坐標(biāo)記為j。
第3步：交換
找到之后菠秒，如果這個(gè)時(shí)候i<j疙剑，那么就交換這兩個(gè)數(shù)，因?yàn)閕=4,j=9践叠，符合條件言缤，將9和1進(jìn)行交換。現(xiàn)在數(shù)組變成了int[]a={7,5,3,2,1,10,8,4,6,9};
如果j>=i酵熙，那么不做處理
為什么還要判斷i和j的大小呢轧简？就像第二步說的，我們要找出比基準(zhǔn)值小的數(shù)放到基準(zhǔn)值的左邊匾二，找出比基準(zhǔn)值的數(shù)放在基準(zhǔn)值的右邊哮独。所以如果i<j的話，交換就達(dá)到目的了察藐，如果i>=j皮璧，比基準(zhǔn)值小的數(shù)就在基準(zhǔn)值的左邊，比基準(zhǔn)值大的數(shù)已經(jīng)在基準(zhǔn)值的右邊了分飞，這時(shí)候就沒必要交換了悴务。
第4步：繼續(xù)查找
在i<j的前提下，繼續(xù)向右查找比基準(zhǔn)值大的數(shù)，往左找比基準(zhǔn)值小的數(shù)讯檐，然后交換羡疗。
在我們的例子中，10和6别洪、8和4都符合交換的條件叨恨，所以數(shù)組就變成了
int[]a={7,5,3,2,1,6,4,8,10,9};這時(shí)候i=6,j=7
第5步：交換基準(zhǔn)值到合適的位置
當(dāng)查找繼續(xù)進(jìn)行，這時(shí)候i=j=6挖垛，已經(jīng)不滿足繼續(xù)查找和交換的條件了痒钝，那么我們應(yīng)該怎么辦呢？答案就是把a(bǔ)[6]和基準(zhǔn)值交換痢毒，因?yàn)閕=j的時(shí)候說明已經(jīng)到了一個(gè)分界線的位置送矩，分界線左邊的數(shù)比基準(zhǔn)值小，分界線右邊的數(shù)比基準(zhǔn)值大哪替，而這個(gè)分界線就是我們的基準(zhǔn)值栋荸，所以把它和a[i]交換，這時(shí)候數(shù)組就變成：
int[]a={4,5,3,2,1,6,7,8,10,9};
第6步：重復(fù)
對基準(zhǔn)值左右兩邊的兩個(gè)子數(shù)組重復(fù)前面五個(gè)步驟直至排序完成夷家。
