分治法
分治法概述
设计思想
将规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
分治法所能解决的问题一般具有以下几个特征：
- 该问题的规模缩小到一定的程度就可以容易地解决。
- 该问题可以分解为若干个规模较小的相同问题。
- 利用该问题分解出的子问题的解可以合并为该问题的解。
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
求解步骤
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
- 求解子问题：若子问题规模较小而容易被解决则直接求解，否则递归地求解各个子问题。
- 合并：将各个子问题的解合并为原问题的解。
分治法的一般的算法设计框架如下：
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);
分治策略：
- 分解：将原序列a[s…t]分解成两个子序列a[s…i-1]和a[i+1…t]，其中i为划分的基准位置。
- 求解子问题：若子序列的长度为0或为1，则它是有序的，直接返回；否则递归地求解各个子问题。
- 合并：由于整个序列存放在数组中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，即归并操作在相邻的多个有序子表中
进行，则叫多路归并排序。
分治策略： 循环⌈log2n⌉次，length依次取1、2、…、log2n。每次执行以下步骤：
- 分解：将原序列分解成length长度的若干子序列。
- 求解子问题：将相邻的两个子序列调用Merge算法合并成一个有序子序列。
- 合并：由于整个序列存放在数组中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;
}
运行结果