1.适用条件
原问题可以归约为独立求解的子问题。子问题要与原问题有相同的类型，即每一个子问题与原问题除了数据的规模不相同外，解决问题的方法完全相同。
特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题;
分解出的子问题的解可以合并为原问题的解；
分解出的各个子问题是相互独立的。
2.典型问题
1.二分检索
https://blog.csdn.net/qq_44766883/article/details/107039935
输入：数组a[]，数组长度len，查找的数值target
输出：查找到元素的下标，若未找到则返回-1
//二分搜索
int binarySearch(int arr[],int len,int target){
int left=0;
int right=len-1;
int mid;
while(left<=right){
mid=(left+right)/2;
if(target<arr[mid]){
right=mid-1;
}else if(target>arr[mid]){
left=mid+1;
}else if(target==arr[mid]){
return mid;
}
}
return -1;
}
2.归并排序
https://blog.csdn.net/doubleguy/article/details/81390951
归并排序
输入：数组a[]，最左端下标left和最右端下标right
void merge(int a[],int temp[],int left,int mid,int right)//排序、合并
//a[]为待排序数组，temp[]为临时数组，left为左边数组的最小下标，right为右边数组的最大下标，mid为左边数组的最大下标，mid+1为右边数组的最小下标
{
int i=left,j=mid+1;//分别记录两个数组第一个数的下标，用作比较
int m=mid,n=right;//分别记录两个数组最后一位的下标，用作限定范围
int k=0;//初始化临时数组指针
while(i<=m&&j<=n)//限定范围
{
//开始作比较
if(a[i]<=a[j]) //如果左边小于右边
temp[k++]=a[i++]; //把左边的数插入临时数组
else //如果右边小于左边
temp[k++]=a[j++]; //把右边的数插入临时数组
}
while(i<=m) //若左边数组还有剩余，把剩下的全都插入temp[]
temp[k++]=a[i++];
while(j<=n) //若右边数组还有剩余，把剩下的全都插入temp[]
temp[k++]=a[j++];
for(i=0;i<k;i++) //将临时数组里以及排好序的数据复制到原数组
a[left+i]=temp[i];
}
void mergesort(int a[],int left,int right)//递归实现归并排序，这个函数主要是“分”的作用
{
if(left<right)//设置递归回归点，即左指针大于（等于）右指针的时候停止向下递归
{
int mid=(left+right)/2;//从中间分开
int b[1000];//临时数组
mergesort(a,left,mid);//向左递归
mergesort(a,mid+1,right);//向右递归
merge(a,b,left,mid,right);//对这一层进行归并，b为临时数组
}
}
3.快排
https://blog.csdn.net/li528405176/article/details/86645708
快排的关键在于如何划分数组，方法多种多样，上面博客讲了三种不同的划分数组的方法，我这边只写一种，即追赶指针法
输入：待排序数组a[]，起始位置left，终止位置right.
void quicksort(int a[],int left,int right)
{
if(left<right)//递归的回归点
{
int h=left,q=left+1,x=a[left];//h,q分别为后指针和前指针，x是快排的基准元素
for(q;q<right;q++)//前指针扫描整个数组
{
if(a[q]<x)//如果遇到小于基准的数
{
h++;//则后指针加一
if(q!=h)swap(a[q],a[h]);//如果前后指针指向的不是一个数，那必然是前指针指向小于基准的，后指针指向大于基准的数，交换
}
}
//扫描结束后，后指针此时必定指向一个小于基准的数（因为已经和前指针交换完毕），这时只需将基准和后指针的数交换即可
swap(a[left],a[h]);
quicksort(a,left,h-1);//递归
quicksort(a,h+1,right);
}
}
