用Java实现递归与分治系列（二）

将一个规模为n的问题分解成k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解决这些子问题，然后将各子问题的解合并得到原问题的解。

二分搜索技术利用了元素间的次序关系，采用分治策略，其基本思想是：将n个元素分成个数大致相同的凉拌，取a[n/2]与x作比较。如果x=a[n/2]，则找到x，如果xa[n/2],则只在右半边查找。

public class Binary_Search {

	public static void main(String[] args) {
		Binary_Search bi=new Binary_Search();
		
		int arr[]={1,2,3,4,5,6,7,8,9,10};
		bi.Search(arr, 0, arr.length-1, 5);
	}
	
	public int Search(int arr[],int left,int right,int s) {
	
		int middle=(left+right)/2;

		if(s==arr[middle]) {
			System.out.println(middle);//打印目标值所在数组的下标
			return middle;
		}
		
		if(sarr[middle]) {
			Search(arr,middle+1,right,s);//递归调用，分治
		}
		
		return 1;
	}	
}

问题描述：在一个2k×2k个方格组成的棋盘中，若有一个方格与其他方格不同，则称该方格为特殊方格，且称该棋盘为特殊棋盘。我们要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

思路：用分治策略，可以设计解棋盘覆盖问题的一个简洁的算法。特殊方格必位于4个较小棋盘之一中，其余三个棋盘无特殊方格。为了将这三个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的汇合处。这三个子棋盘被L骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1x1棋盘。
代码如下

public class ChessBoard{
	int tile=1;
	static int board[][]=new int[8][8];
	public static void main(String[] args) {
		ChessBoard cb=new ChessBoard();
		cb.chessboard(0,0,1,1,8);
		for(int i=0;i= tc+s) {
			chessboard(tr,tc+s,dr,dc,s);//特殊方格在该棋盘
		}else {
			board[tr+s-1][tc+s]=t;//特殊方格不在该棋盘
			chessboard(tr,tc+s,tr+s-1,tc+s,s);
		}
			
		//覆盖左下角的棋盘
		if(dr >= tr+s && dc < tc+s) {
			chessboard(tr+s,tc,dr,dc,s);//特殊方格在该棋盘
		}else {
			board[tr+s][tc+s-1]=t;
			chessboard(tr+s,tc,tr+s,tr+s-1,s);
		}
			
		//覆盖右下角的棋盘
		if(dr>=tr+s && dc>=tc+s) {
			chessboard(tr+s,tc+s,dr,dc,s);
		}else {
			board[tr+s][tc+s]=t;
			chessboard(tr+s,tc+s,tr+s,tc+s,s);
		}
		
	}

}	

程序运行结果如下

合并排序算法是用分治策略实现对n个元素进行排序的算法，其基本思想是：将待排序元素分成大小大致相同的两个子集合，然后分别对两个子集合进行排序，最后将两个排好序的子集合并成按要求排序的集合。

public class MergeSort {

	static int arr[]= {23,45,76,3,8,5,46,4};//待排序数组
	static int temp[]=new int[arr.length];//过渡数组
	
	public static void main(String[] args) {
		MergeSort ms=new MergeSort();
		ms.mergesort(arr,temp,0,arr.length-1);
		//打印输出排完序后的情况
		for(int i=0;i 
（四）快速排序 
快速排序算法也是基于分治策略的一个算法，其基本思想是：在数组中选一个基准数（通常为数组第一个）,将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边, 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。即：
 1，分解
 2，递归求解
 3，合并
 
public class QuickSort {
	static int array[]={12,43,6,2,56,5};
	public static void main (String[] args){
			QuickSort qs=new QuickSort();
			qs.quickSort(arr,0,arr.length-1);
			for(int i=0;i=right) {
            return;
        }
        int i = left, j = right,；
        int index = array[i]; //选择第一个数为基准数
        while (i < j) {
            while (i < j && array[j] >= index) { 
                j--;
            }
            if (i < j) {
                array[i++] = array[j]; 
            }
            while (i < j && array[i] < index) {
                i++;
            }
            if (i < j) {
                array[j--] = array[i]; 
            }
        }
        array[i] = index; // 将基准数填入
        quickSort(array, left, i - 1); // 递归调用，分治
        quickSort(array, i + 1, right); // 递归调用，分治
    }