引入
分治
"分而治之"。将原问题划分成了几个可合并的规模更小的问题，分别解决。然后合并。
分治法的具体操作是把原问题分解成若干个较小规模的子问题，对这个子问题分别求解。如果子问题不够小，那么把每个子问题再划分为规模更小的子问题。这样一直分解下去，直到问题足够小，能十分简单地求出子问题的答案为止。
步骤
- 分解
- 解决
- 合并
举例
二分查找
int search(int arr[],int mins,int maxs,int key){
int left = mins;
int right = maxs;
while(left<=right){
int mid=(left+right)/2;
if(arr[mid] == key){
return mid;
}else if(arr[mid] > key){
left=mid+1;
}else{
right=mid-1;
}
}
return -1;
}
复杂度为O(logn)
递归
函数直接或间接地调用自己。
- 递归过程 => 解决问题的方法， 让规模缩小，接近答案
- 终止条件 => 递归边界
举例
求阶乘。
n! = 1 * 2 * 3 * 4 * ... * n-1 * n
n!=(n-1)! * n
int fun(int n){
if(n==1) return 1;
return fun(n-1)*n;
}
快速排序
问题：如何根据分治的思想设计排序算法？
- 分解。
- 解决。
- 合并。
快速排序（升序）思路：把序列分成左、右两部分。使得左边的所有数字都比右边的数小。再按相同的方法，对左右两部分分别进行快速排序。
选取一个数字作为基准数，检查序列中的所有元素，比基准数小的，放在左边，比基准数大的，放在右边。
整体框架
void qSort(int arr[],int left,int right){
if(left >= right) return ;
int privot=divide(left,right);
qSort(arr,left,privot-1);
qSort(arr,privot+1,right);
}
划分策略
Lomuto划分
选取第一个元素作为基准数。将序列分成三段，一段比基准数小，一段比基准数大，一段是待划分序列。
s指向小于基准数段的最后一个元素。
i从未处理段的第一个元素开始向后扫描数组。过程中当i发现比基准数小的，则将s的后一个元素和i进行交换。
void qSort(int arr[],int left,int right){
if(left >= right) return ;
//选取最左边的数作为基准数
int s=left;// s 指向< 基准数序列的最后一个元素
int t=arr[left];//t为基准数
// 目的 ： 使得 比t小的都在t的左边，比t大的都在t的右边
for(int i=left+1,i<=right;i++){//遍历所有的待排序数字
//发现比基准数小的数 ，就将其加入到 < t 的序列中
if(arr[i]<t){
s++;
swap(arr[i],arr[s]);
}
}
// left（< t ）s (>t) i (待排序) right
swap(arr[left],arr[s]);
qSort(arr,left,s-1);
qSort(arr,s+1,right);
}
Hoare划分
将分别从序列的两端进行扫描，并将扫描到的元素与中轴进行比较。
先从序列的右边往左边找，找比基准值小的值；再从左边开始往右边找，找到比基准值大的值。将两者交换，使得左边的一段小于基准值，右边的一段大于基准值。直到两者相遇，相遇位置即基准数应该在的位置。
void qSort(int arr[],int left,int right){
if(left >= right) return ;
//选取最左边的数作为基准数
int i=left,j=right;
int t=arr[left];
while(i<j){
//从右向左扫描 ， 找到第一个比基准数小的值
while(arr[j]>=t&&i<j) j--;
//从左向右扫描，找到第一个比基准数大的值
while(arr[j]<=t&&i<j) i++;
if(i<j){
swap(arr[i],arr[j]);
}
}
swap(arr[left],arr[i]);
qSort(arr,left,i-1);
qSort(arr,i+1,right);
}
小优化
若出现大量相同的数据。上面两种方法用时较长。
有n个相同的元素的序列来说，划分后的两个子序列的长度可能分别时n-1 和 0,从而在扫描了整个数组后只将问题的规模减1.
采用中间数。
void qSort(int arr[],int left,int right){
if(left >= right) return ;
//选取中间数作为基准值
int i=left,j=right,mid=arr[(left+right)/2];
while(i<=j){
while(arr[i]<mid) i++;//从左向右扫描，找第一个大于基准值的
while(arr[j]>mid) j--;//从右向左扫描，找第一个小于基准值的
if(i<=j){
swap(arr[i],arr[j]);
i++,j--;
}
}
if(left < j) qSort(arr,left,j);
if(i<right) qSort(arr,i,right);
}
练习
快速排序模板
https://www.luogu.com.cn/problem/P1177
C++中的sort()
需要添加头文件 algorithm
对整数数组 升序排列
arr[1]~arr[n]
sort(arr+1 ,arr+n+1 );//默认规则为从小到大
对整数数组 降序排列
需要对规则进行自定义
sort(开始位置，结束位置+1,排序规则);
bool cmp(int a,int b){
if(a<b){
return true;
}else{
return false;
}
}
//调用， 对数组a[1]~a[n]从大到小排序
sort(a+1,a+n+1,cmp);
练习
奖学金问题