分治算法小结（Java版）

我不是女神ヾ 2022-03-12 10:44 283阅读 0赞

**分治算法（divide and conquer）**

算法设计思想：  
**分（divide）**：递归解决较小的问题（基本情况除外）。  
**治（conquer）**：从子问题的解构建原问题的解。

适合用分治法的问题：  
当求解一个输入规模非常大的问题时，用暴力法效率一般得不到保证，如果问题能满足以下几个条件，就可以采用分治法提高解决效率：

1.  能将这n个数据分解成k个不同的子集合，且得到k个子集合是可以**独立求解**的子集问题，1<k<=n
2.  分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制
3.  在求出**子问题的解可以推出原问题的解**。

**对于一些重叠子问题类的题目，用动态规划是一种较好的解决办法**

典型采用分治算法的例子：二分法查找，归并排序，快速排序，二叉树遍历（先遍历左子树再遍历右子树），二叉排序树的查找等算法。

下面从具体题目中理解分治算法的含义

典型算法之**折半查找**

public class BinarySearch {
    	/**
    	 * 二分查找
    	 * @param num 需要查找的数组(必须为有序数列)
    	 * @param n 待查找的值
    	 * @param left 数组开始下标
    	 * @param right	数组结尾下标
    	 * @return	返回该值在数组中的位置，不存在则返回-1
    	 */
    	public static int Search(int[] num,int n,int left,int right) {
    		int mid = (left + right) / 2;
    		if(n == num[mid])
    			return mid+1;			//若n等于当前中间元素则返回下标
    		if(left<right) {			//如果left小于right，说明没有查找完
    			if(n > num[mid])		//如果大于中间值，则从右半部查找
    				return Search(num,n,mid+1,right);
    			else					//否则从左半部查找
    				return Search(num,n,left,mid-1);
    		}
    		return -1;					//right大于left，n不存在数组中，返回-1
    	}
    	public static void main(String[] args) {
    		int[] nums = new int[10];
    		Scanner sc = new Scanner(System.in);
    		for(int i = 0;i<nums.length;i++) {
    			nums[i] = sc.nextInt();
    		}
    		sc.close();
    		System.out.println(Search(nums,5,0,nums.length-1));
    	}
    
    }
    /**
     * input:1 2 3 4 5 6 7 8 9 10
     * output:5
     */

典型算法之**快速排序**

public class QuickSort {
    	public static void QKsort(int[] arr,int low ,int high) {
    		if(low<high) {
    			int pos = QKpass(arr,low,high);	//划分两个子表
    			QKsort(arr,low,pos-1);			//对左子表快排
    			QKsort(arr,pos+1,high);			//对右子表快排
    		}
    	}
    	/**
    	 * 一趟快速排序算法
    	 * @param arr 待排序数组
    	 * @param low 数组开始下标
    	 * @param high数组结束下标
    	 * @return
    	 */
    	public static int QKpass(int[] arr,int low,int high) {
    		int temp = arr[low];		//先把当前元素作为待排值（一趟排序实际上就是把它放到合适的位置）
    		while(low < high) {			
    			while(low < high && arr[high] >= temp)	//从右向左扫描，找到第一个小于temp的值
    				high--;
    			if(low < high) {						//将此值放入下标为low的数组中
    				arr[low] = arr[high];
    				low++;
    			}	
    			while(low < high && arr[low] <= temp)	//从左向右扫描找到第一个大于temp的值
    				low++;
    			if(low < high) {
    				arr[high] = arr[low];				//放在下标为high的数组中
    				high--;
    			}
    		}
    		arr[low] = temp;							//将此元素放入其准确位置
    		return low;									//返回此次排序完成的值当前下标（即此位置的元素已经排好）
    	}
    	public static void main(String[] args) {
    		int[] arr = new int[10];
    		Scanner sc = new Scanner(System.in);
    		for(int i = 0;i<arr.length;i++)
    			arr[i] = sc.nextInt();
    		sc.close();
    		QKsort(arr,0,arr.length - 1);
    		for(int x:arr) {
    			System.out.print(x + " ");
    		}
    	}
    /**
     * input:10 9 8 7 6 5 4 3 2 1 
     * output:1 2 3 4 5 6 7 8 9 10 
     */
    }

典型算法之**归并排序**

public class MergeSort {
    	/**
    	 * 将arr[low..mid]和arr[mid + 1..high]合并为一个有序序列
    	 * @param arr
    	 * @param low
    	 * @param mid
    	 * @param high
    	 */
    	public static void merg(int[] arr,int low,int mid,int high) {
    		int[] temp = new int[high - low +1];
    		int i = low,j = mid+1,k = 0;
    		while(i<=mid && j<=high) {		//总是将两个序列中较小的赋值给当前数组元素
    			if(arr[i]<=arr[j]) {
    				temp[k] = arr[i];
    				k++;
    				i++;
    			}else {
    				temp[k] = arr[j];
    				k++;
    				j++;
    			}
    		}
    		while(i <= mid) {				//如果一个序列遍历完，则将另一个序列所有元素复制到当前数组
    			temp[k] = arr[i];
    			k++;i++;
    		}
    		while(j<= high) {
    			temp[k] = arr[j];
    			j++;i++;
    		}
    		System.arraycopy(temp, 0, arr, low, temp.length);	//将合并后的序列重新复制给arr
    	}
    	/**
    	 * @param arr	待排序数组
    	 * @param low	开始下标
    	 * @param high	结尾下标
    	 */
    	public static void MSort(int[] arr,int low,int high) {
    		if(low == high)				//如果low等于high说明排序进行完成
    			return;
    		else {
    			int mid = (low + high)/2;
    			MSort(arr,low,mid);		//拆分左边
    			MSort(arr,mid+1,high);	//拆分右边
    			merg(arr,low,mid,high);	//排序合并
    		}
    	}
    	public static void main(String[] args) {
    		int[] arr = new int[10];
    		Scanner sc = new Scanner(System.in);
    		for(int i = 0;i<arr.length;i++)
    			arr[i] = sc.nextInt();
    		sc.close();
    		MSort(arr,0,arr.length - 1);
    		for(int x:arr) {
    			System.out.print(x + " ");
    		}
    	}
    /**
     * input:10 9 8 7 6 5 4 3 2 1 
     * output:1 2 3 4 5 6 7 8 9 10 
     */
    }

**选择问题：要求我们找出N个元素的集合S中第k小的元素。**

public class ChooseQuestion {
    	/**
    	 * 从长度为length的数组中找出第k小的元素
    	 * @param arr	待查找数组
    	 * @param length数组尾下标
    	 * @param k		第k小的元素
    	 * @return		返回第k小的元素的值
    	 */
    	public static int choose(int[] arr,int length,int k) {
    		if(k<0 || k>length)			//如果k不满足要求返回
    			return -65536;
    		else						//否则就用类似快排查找
    			return select(arr,0,arr.length-1,k);
    	}
    	/**
    	 * 从arr中找第k小的元素
    	 * @param arr	数组
    	 * @param left	起始下标
    	 * @param right	结束下标
    	 * @param k		第k小
    	 * @return		返回此值
    	 */
    	public static int select(int[] arr,int left,int right,int k) {
    		/*
    		 * 此种算法类似于快排，但是与快速排序不同的是并不进行完全排序，而是每次只处理其中的一个子问题，查到该值时就返回
    		 */
    		int low = left,high = right, pivot;
    		if(left >= right)
    			return arr[left];
    		pivot = arr[left];
    		while(low < high) {
    			while(low < high && arr[high] > pivot)
    				high--;
    			if(low < high) {
    				arr[low] = arr[high];
    				low++;
    			}
    			while(low < high && arr[low] < pivot)
    				low++;
    			if(low < high) {
    				arr[high] = arr[low];
    				high--;
    			}
    		}
    		arr[low] = pivot;	//到此处为止是一趟快速排序的代码，现在我们只要判断本次排序出来的元素是不是第k小
    		if(low - left + 1 == k)	//如果是，则直接返回此元素，不再往下查找
    			return pivot;
    		if(low - left + 1 <k)	//如果要查找的k比它大，我们再去右边查找
    			return select(arr,low + 1,right,k - low + left - 1);	//从右边查找的时候我们就要查找的是右边的第k减去上一次枢纽值的正确下标值，即(k-(low-left+1))
    		else					//否则就去左边查找
    			return select(arr,left,low-1,k);	
    	}
    	public static void swap(int a,int b) {
    		int temp = a;
    		a = b;
    		b = temp;
    		return; 
    	}
    	public static void main(String[] args) {
    		int[] arr = new int[10];
    		Scanner sc = new Scanner(System.in);
    		for(int i = 0;i<arr.length;i++)
    			arr[i] = sc.nextInt();
    		sc.close();
    		System.out.println(choose(arr,arr.length-1,5));
    	}
    /**
     * input:10 9 8 7 6 5 4 3 2 1 
     * output:5
     */
    }