C++ 分治
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
目录
1.分治法
2.二分搜索
函数传参——数组
3.棋盘覆盖
4.合并排序
5.快速排序
提示：以下是本篇文章正文内容，下面案例可供参考
1.分治法
基本思想：1.将规模为n的问题分解为k个规模较小的子问题，这些问题相互独立且与原问题相同;2.递归地解这些子问题;3.将各子问题的解合并得到原问题的解。
2.二分搜索
问题描述：从单调不减的一组元素中找到特定的元素x
#include <iostream>
using namespace std;
const int n=10;
int a[n]={0,1,2,4,5,8,9,10,20,40};
int BinarySearch(int x)
{
int left=0;
int right=n-1;
while(left<=right)
{
int middle=(left+right)/2;
if(x==a[middle]) return middle;
if(x>a[middle]) left=middle+1;//右半边查找
else right=middle-1;//左半边查找
}
return -1;
}
int main()
{
int x;
cin>>x;
cout<<BinarySearch(x);
}函数传参——数组
#include <iostream>
using namespace std;const int n=10;
int BinarySearch(int a[],int x)
{……}
int main()
{
int a[n]={0,1,2,4,5,8,9,10,20,40};
int x;
cin>>x;
cout<<BinarySearch(a,x);
}
3.棋盘覆盖
方格规模为size*size，size=2的k次方（k为整数）
代码如下（示例）：
#include<iostream>
#include<iomanip>
using namespace std;
int tile=0;
int Board[1024][1024]={};
void ChessBoard(int tr ,int tc,int dr,int dc,int size)
{//tr棋盘左上角行号，tc期盼左上角列号，dr被覆盖的行号，dc被覆盖的列号
if(size==1) return;//2*2时往下走，特殊方格之外的三个都将被覆盖，至此覆盖完成
int t=++tile;
int s=size/2; //分割棋盘
//左上
if(dr<tr+s&&dc<tc+s) ChessBoard(tr,tc,dr,dc,s);//特殊方格在 ，继续划分
else{ //不在
Board[tr+s-1][tc+s-1]=t;//覆盖右下角，创造出特殊方格
ChessBoard(tr,tc,tr+s-1,tc+s-1,s);//这部分棋盘右下角有特殊方格，继续划分
}
//右上
if(dr<tr+s&&dc>=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,tc+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);
}
}
int main()
{
int size=0;
cin>>size;
int tr=0,tc=0;
int dr=0,dc=0;
cin>>dr>>dc;//特殊方格坐标
ChessBoard(tr,tc,dr,dc,size);
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
cout<<setw(2)<<Board[i][j]<<' ';//setw(n)预设宽度
}
cout<<endl;
}
} 
4.合并排序
void merge(vector<int>& nums,vector<int>& arr,int l,int mid,int r)
{
if(l==r) return;
int a=l,b=mid+1,index=l;
while(a<=mid&&b<=r)
{
if(nums[a]<=nums[b]) arr[index]=nums[a],a++;
else arr[index]=nums[b],b++;
index++;
}
while(a<=mid) arr[index]=nums[a],a++,index++;
while(b<=r) arr[index]=nums[b],b++,index++;
for(int i=l;i<=r;i++) nums[i]=arr[i];
}
void Mergesort(vector<int>& nums,vector<int>& arr,int l,int r)
{
if(l==r) return;
int mid=(l+r)/2;
Mergesort(nums,arr,l,mid);//左半部分
Mergesort(nums,arr,mid+1,r);//右半部分
merge(nums,arr,l,mid,r);//合并排序
}
vector<int> sortArray(vector<int>& nums) {
vector<int> arr(nums);
int n=nums.size();
Mergesort(nums,arr,0,n-1);
return nums;
}5.快速排序
void Swap(int* a,int* b)
{
int temp=*b;
*b=*a;
*a=temp;
}
int Partition(vector<int>& nums,int p,int r)
{
int i=p,j=r+1;
int x=nums[p];
while(1)
{
while(nums[++i]<x && i<r);
while(nums[--j]>x);
if(i>=j) break;
Swap(&nums[i],&nums[j]);
}
Swap(&nums[p],&nums[j]);
return j;
}
void Quicksort(vector<int>& nums,int p,int r)
{
if(p<r)
{
int q=Partition(nums,p,r);
Quicksort(nums,p,q-1);//左半部分
Quicksort(nums,q+1,r);//右半部分
}
}
vector<int> sortArray(vector<int>& nums) {
int n=nums.size();
Quicksort(nums,0,n-1);
return nums;
}