分治法5思维导图

先将整个数组进行排序，然后运用到一个叫双指针的东西，即一个指针从第一个开始一直向右，第二个指针从最后一个开始一直向左。当第一个指针与第二个重合或超过第二个指针时，循环退出。

int s=1,x=n; while(s<x){ if(a[s]+a[x]==m){ cout<<a[s]<<" "<<a[x]; return 0; } else if(a[s]+a[x]>m) x--; else if(a[s]+a[x]<m) s++; }

先把这题可以分解为两个小问题：1.将前n-1个数排好序2.将第n个数插进去

void isort(int x){ //解决基本情况：当x==1时直接返回 if(x==1) return ; //子问题1：将前n-1个数排好序 isort(x-1); //子问题2：将第x个整数插入进去 int t=a[x],i; for(i=x-1;i>=1;i--){ if(a[i]>t) a[i+1]=a[i]; else break; } a[i+1]=t; }

void merge(int l,int mid,int r){ int i,j,k; i=l;j=mid+1;k=l; while(i<=mid&&j<=r){ if(a[i]<=a[j]) b[k++]=a[i++];//b数组暂时存放一下里面的值,a[i]和a[j]哪个小放哪个 else b[k++]=a[j++]; } while(i<=mid) b[k++]=a[i++];//检查是否有遗漏 while(j<=r) b[k++]=a[j++]; for(int i=l;i<=r;i++)a[i]=b[i];//重新赋值给a } void msort(int l,int r){ int mid=(l+r)/2; if(l==r) return;//边界 msort(l,mid);//先把起始点到中间的找到 msort(mid+1,r);//再把中间到最后的找到 merge(l,mid,r);//合并，排序 }