Java舉例講解分治算法思想

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

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

分治算法

什么是分治算法

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

分治算法的思想

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

簡單可以理解為

首先將原問題分解為若干個子問題

各子問題的結構基本相似，規(guī)模基本相當

遞歸使分治的工具

遞歸調用：問題和子問題的分解
遞歸約束：對子問題的解進行合并

分治法四大基本特征

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

分治法求解問題的三個基本步驟

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

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

divide-and-conquer(p)//閥值
{
if(|p|<n0)adhoc(p);//如果問題可以直接求解，就直接求解。|p|代表問題的規(guī)模
divide p into amaller subinstances P1,P2,P3......Pk;//將原問題分解成k個規(guī)模較小的子問題，且這些子問題的規(guī)模相當結構相似
for(i=1;i<=k;i++)
yi=divide-and-conquer(p)//遞歸求解各個子問題Pi,若分解的子問題還可以分解成若干個子子問題，就再對子問題進行分解
return merge(y1,y2,y3......yk)//將子問題的解合并成原問題的解
}

關于分治算法的舉例

歸并排序

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

package 算法設計與分析;
 public class 歸并排序 {
 //arr是存放原始元素的數(shù)組，left數(shù)組arr的最左邊，left是數(shù)組的最右邊，mid是劃分的終點，數(shù)組tmp是一個臨時數(shù)組，就是一個輔助存儲空間
         public static void main(String[] args) {
             int[] arr = {49,38,65,97,76,13,27};
             int[] tmp = new int[arr.length];    //新建一個臨時數(shù)組存放,相當于是一個輔助空間
             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++];
                 }
             }
             //若左邊序列還有剩余，則將其全部拷貝進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); //對左邊序列進行歸并排序
                 mergeSort(arr,mid+1,right,tmp);  //對右邊序列進行歸并排序
                 merge(arr,left,mid,right,tmp);    //合并兩個有序序列，相當于用tmp覆蓋原來的arr
             }
         }
     }

基本步驟

劃分中點mid；
分別對左右子區(qū)間歸并排序，歸并的結果(是一個有序序列)存放在數(shù)組tmp中，tmp是一個臨時數(shù)組，相當于一個輔助存儲空間；
用tmp去覆蓋原來的數(shù)組arr。

快速排序

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

思想：把最左邊的元素作為主元，數(shù)組一左一右兩個指針進行掃描，左邊的指針直到找到一個元素比主元大時，便停止左移，右邊的指針向左移動，直到找到一個不大于主元的元素，交換兩個指針所指向的元素。

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

package 算法設計與分析;
 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就是基準位,就是主元，將數(shù)組中的第一個元素作為主元
             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;
                 }
             }
             //最后將基準為與i和j相等位置的數(shù)字交換
             arr[left] = arr[i];
             arr[i] = temp;
             //遞歸調用左半數(shù)組
             quickSort(arr, left, j-1);
             //遞歸調用右半數(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]+ " ");
             }
         }
     }

二分搜索算法

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

 package 算法設計與分析;
 //用遞歸的方法解決二分搜索問題
 public class 二分查找 {
     public static void main(String[] args) {
         int[] arr = {-7,-2,0,15,27,54,80,88,102};
         //想要查找的元素
         int key = 80;
         //對查找到的元素進行定位
         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){
             //比關鍵字大則關鍵字在左區(qū)域
             return Search(arr, key, left, middle - 1);
         }else if(arr[middle] < key){
             //比關鍵字小則關鍵字在右區(qū)域
             return Search(arr, key, middle + 1, right);
         }else {
             return middle;
         }
     }
 }