提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

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;}