分治法

• 分治法概述
• • 设计思想
  • 求解步骤
• 求解排序问题
• • 快速排序
  • 归并排序
  • 求解查找问题

分治法概述

设计思想

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

分治法所能解决的问题一般具有以下几个特征：

1. 该问题的规模缩小到一定的程度就可以容易地解决。
2. 该问题可以分解为若干个规模较小的相同问题。
3. 利用该问题分解出的子问题的解可以合并为该问题的解。
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

求解步骤

1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
2. 求解子问题：若子问题规模较小而容易被解决则直接求解，否则递归地求解各个子问题。
3. 合并：将各个子问题的解合并为原问题的解。

分治法的一般的算法设计框架如下：

divide-and-conquer(P)
{  if |P|≤n0 return adhoc(P);
   将P分解为较小的子问题 P1，P2，…，Pk;
   for(i=1;i<=k;i++)			//循环处理k次
      yi=divide-and-conquer(Pi);	//递归解决Pi
　　return merge(y1，y2，…，yk);	//合并子问题
}

求解排序问题

快速排序

基本思想：在待排序的n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入最终位置后，整个数
据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，
并把基准排在这两个子序列的中间，这个过程称作划分。
然后对两个子序列分别重复上述过程，直至每个子序列内只有一个记录或空为止。

f(a,s,t) ≡ 不做任何事情		当a[s..t]中长度小于2
f(a,s,t) ≡ i=Partition(a,s,t);	其他情况
           f(a,s,i-1);
           f(a,i+1,t); 

分治策略：

1. 分解：将原序列a[s…t]分解成两个子序列a[s…i-1]和a[i+1…t]，其中i为划分的基准位置。
2. 求解子问题：若子序列的长度为0或为1，则它是有序的，直接返回；否则递归地求解各个子问题。
3. 合并：由于整个序列存放在数组中a中，排序过程是就地进行的，合并步骤不需要执行任何操作。

快排code：

#include<iostream>
using namespace std;
int partition(int a[],int s,int t){
	int i=s,j=t,vot=a[s];
	while(i!=j){
		while(j>i&&a[j]>=vot){
			j--;
		}
		a[i]=a[j];
		while(j>i&&a[i]<=vot){
			i++;
		}
		a[j]=a[i];
	}
	a[i]=vot;
	return i;
}
void quik_sort(int a[],int s,int t){
	if(s<t){
		int i = partition(a,s,t);
		quik_sort(a,s,i-1);
		quik_sort(a,i+1,t);
	}
}
int main(){
	int a[]={9,8,6,7,45,1,3,4};
	quik_sort(a,0,7);
	for(int i=0;i<8;i++){
		cout<<a[i]<<" ";
	}
	return 0;
} 

运行结果

归并排序

基本思想：首先将a[0..n-1]看成是n个长度为1的有序表，将相邻的k（k≥2）个有序子表成对归并，得到n/k个长度
为k的有序子表；然后再将这些有序子表继续归并，得到n/k2个长度为k2的有序子表，如此反复进行下去，最后得到
一个长度为n的有序表。
若k=2，即归并在相邻的两个有序子表中进行的，称为二路归并排序。若k>2，即归并操作在相邻的多个有序子表中
进行，则叫多路归并排序。

分治策略： 循环⌈log₂n⌉次，length依次取1、2、…、log₂n。每次执行以下步骤：

1. 分解：将原序列分解成length长度的若干子序列。
2. 求解子问题：将相邻的两个子序列调用Merge算法合并成一个有序子序列。
3. 合并：由于整个序列存放在数组中a中，排序过程是就地进行的，合并步骤不需要执行任何操作。

归并code：

#include<iostream>
#include<malloc.h>
using namespace std;
void merge(int a[],int low,int mid,int high){
	int *temp;
	int k=0,i=low,j=mid+1;
	temp=(int*)malloc(sizeof(int)*(high-low+1));
	while(i<=mid&&j<=high){
		if(a[i]<a[j]){
			temp[k++]=a[i++];
		}else{
			temp[k++]=a[j++];
		}
	}
	while(i<=mid){
		temp[k++]=a[i++];
	}
	while(j<=high){
		temp[k++]=a[j++];
	}
	for(k=0,i=low;i<=high;k++,i++){
		a[i]=temp[k];
	}
	free(temp);
}
void merge_pass(int a[],int length,int n){
	//一趟二路归并 
	int i;
	for(i=0;i+2*length-1<n;i=i+2*length){
		merge(a,i,i+length-1,i+2*length-1); 
	}
	if(i+length-1<n){//余下2个子表，后一子表长度小于length
		merge(a,i,i+length-1,n-1); 
	}
}
void merge_sort(int a[],int n){//2路归并算法 
	int length;
	for(length=1;length<n;length=length*2){
		merge_pass(a,length,n);
	}
} 
int main(){
	int a[]={9,5,6,2,3,4,7,1,8};
	merge_sort(a,9);
	for(int i=0;i<9;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

运行结果

求解查找问题

例：查找最大和次大元素

#include<iostream>
#include<algorithm>
#include<limits.h> 
using namespace std;
void solve(int a[],int low,int high,int &max1,int &max2){
	if(low==high){
		max1=a[low];
		max2=INT_MIN;
	}else if(low==high-1){
		max1=max(a[low],a[high]);
		max2=min(a[low],a[high]);
	}else{
		int mid=(low+high)/2;
		int lmax1,lmax2;
		solve(a,low,mid,lmax1,lmax2);
		int rmax1,rmax2;
		solve(a,mid+1,high,rmax1,rmax2);
		if(lmax1>rmax1){
			max1=lmax1;
			max2=max(lmax2,rmax1);
		}else{
			max1=rmax1;
			max2=max(rmax2,lmax1);
		}
	}
}
int main(){
	int a[]={8,69,4,12,6,3,5,7};
	int max1,max2;
	solve(a,0,7,max1,max2);
	cout<<" 最大值："<<max1<<endl; 
	cout<<" 次大值："<<max2<<endl;
	return 0;
}

运行结果

例：寻找一个序列中第k小元素
思路：使用快排，每一趟快排把一个元素放在最终位置，每将一个元素放到最终位置，判断其下标是否为k-1，是的话便找到第k小元素。

#include<iostream>
using namespace std;
int quick_select(int a[],int s,int t,int k){
	int i=s,j=t,vot;
	if(s<t){
		vot=a[s];
		while(i!=j){
			while(i<j&&a[j]>=vot){
				j--;
			}
			a[i]=a[j];
			while(i<j&&a[i]<=vot){
				i++;
			}
			a[j]=a[i];	
		}
		a[i]=vot;
		if(k-1==i){
			return a[i];
		}
		else if(k-1<i){
			return quick_select(a,s,i-1,k);
		}else{
			return quick_select(a,i+1,t,k);
		}
	}else if(s==t&&s==k-1){
		return a[k-1];
	}
}
int main(){	
	int a[]={9,5,6,3,2,1,4,7};
	int k=4;
	cout<<" 第"<<k<<" 小元素：";
	int q = quick_select(a,0,7,k);
	cout<<q;
	return 0;
}

运行结果