快捷導(dǎo)航

Java舉例講解分治算法思想

更新時(shí)間：2022年04月29日 10:32:43 作者：LNORA

分治算法的基本思想是將一個(gè)規(guī)模為N的問題分解為K個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解，本篇文章我們就用分治算法來實(shí)現(xiàn)歸并排序快速排序以及二分搜索算法

分治算法

什么是分治算法

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

分治算法的思想

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

簡(jiǎn)單可以理解為

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

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

遞歸使分治的工具

遞歸調(diào)用：?jiǎn)栴}和子問題的分解
遞歸約束：對(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ī)模
divide p into amaller subinstances P1,P2,P3......Pk;//將原問題分解成k個(gè)規(guī)模較小的子問題，且這些子問題的規(guī)模相當(dāng)結(jié)構(gòu)相似
for(i=1;i<=k;i++)
yi=divide-and-conquer(p)//遞歸求解各個(gè)子問題Pi,若分解的子問題還可以分解成若干個(gè)子子問題，就再對(duì)子問題進(jìn)行分解
return merge(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ì)與分析;
 public class 歸并排序 {
 //arr是存放原始元素的數(shù)組，left數(shù)組arr的最左邊，left是數(shù)組的最右邊，mid是劃分的終點(diǎn)，數(shù)組tmp是一個(gè)臨時(shí)數(shù)組，就是一個(gè)輔助存儲(chǔ)空間
         public static void main(String[] args) {
             int[] arr = {49,38,65,97,76,13,27};
             int[] tmp = new int[arr.length];    //新建一個(gè)臨時(shí)數(shù)組存放,相當(dāng)于是一個(gè)輔助空間
             mergeSort(arr,0,arr.length-1,tmp);
             for(int i=0;i<arr.length;i++){
                 System.out.print(arr[i]+" ");
             }
         }
         public static void merge(int[] arr,int left,int mid,int right,int[] tmp){
             int i = 0;
             int j = left,k = mid+1;  //左邊序列和右邊序列起始索引
             while(j <= mid && k <= 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(int t=0;t<i;t++){
                 arr[left+t] = tmp[t];
             }
         }
         public static void mergeSort(int[] arr,int left,int right,int[] tmp){
             if(left<right){
                 int mid = (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ì)與分析;
 public class 快速排序 {
         public static void quickSort(int[] arr,int left,int right){
             int i,j,temp,t;
             if(left>right){
                 return;
             }
             i=left;
             j=right;
             //temp就是基準(zhǔn)位,就是主元，將數(shù)組中的第一個(gè)元素作為主元
             temp = arr[left];
             while (i<j) {
                 //先看右邊，依次往左遞減
                 while (temp<=arr[j]&&i<j) {
                     j--;
                 }
                 //再看左邊，依次往右遞增
                 while (temp>=arr[i]&&i<j) {
                     i++;
                 }
                 //如果滿足條件則交換
                 if (i<j) {
                     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);
         }
         public static void main(String[] args){
             int[] arr = {72,26,57,88,42,80,72,48,60,};
             quickSort(arr, 0, arr.length-1);
             for (int i = 0; i < arr.length; i++) {
                 System.out.print(arr[i]+ " ");
             }
         }
     }

二分搜索算法

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

 package 算法設(shè)計(jì)與分析;
 //用遞歸的方法解決二分搜索問題
 public class 二分查找 {
     public static void main(String[] args) {
         int[] arr = {-7,-2,0,15,27,54,80,88,102};
         //想要查找的元素
         int key = 80;
         //對(duì)查找到的元素進(jìn)行定位
         int position = Search(arr,key,0,arr.length - 1);
         if(position == -1){
             System.out.println("查找的是"+key+",序列中沒有該數(shù)！");
         }else{
             System.out.println("查找的是"+key+",找到位置為："+position);
         }
     }
     public static int Search(int[] arr,int key,int left,int right){
         if(key < arr[left] &&key > arr[right] &&left > right){
             return -1;
         }
         int middle = (left + right) / 2;            //初始中間位置
         if(arr[middle] > key){
             //比關(guān)鍵字大則關(guān)鍵字在左區(qū)域
             return Search(arr, key, left, middle - 1);
         }else if(arr[middle] < key){
             //比關(guān)鍵字小則關(guān)鍵字在右區(qū)域
             return Search(arr, key, middle + 1, right);
         }else {
             return middle;
         }
     }
 }