一 主要内容
- 快速排序 0.00
- 归并排序 30.00
- 二分 50.00 (整数和浮点数)
二 快速排序
1 思路:
- 选择一个位置作为枢纽(分界点)
- 操作使得该枢纽左边的数据小于等于枢纽值,使得枢纽右边的数据大于等于枢纽
- 递归处理左右两端。
2 模板回顾 原题链接
#include <iostream>
using namespace std;
const int N=100010;
void quick_sort(int q[],int l,int r){
if (l>=r) return ;
int i=l-1,j=r+1;
int x=q[l+r>>1];
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if (i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j),quick_sort(q,j+1,r);
}
int q[N];
int main(){
int n;
scanf("%d",&n);
for (int i=0;i<n;i++)scanf("%d",&q[i]);
quick_sort(q,0,n-1);
for (int i=0;i<n;i++)printf("%d ",q[i]);
}
三 归并排序
1 思路
- 以中间位置的点为分割点,将数组分为两部分
- 递归归并排序左右两部分
- 将左右两部分的元素进行合并,这里两部分头元素进行比较,哪边小作为加入合并数组,并后移,直到全部合并。
2 模板回顾 原题链接
#include <iostream>
using namespace std;
const int N=1e5+10;
int q[N],m[N];
void merge_sort(int q[],int l,int r){
if (l>=r) return ;
int mid=l+r>>1;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int i=l,j=mid+1,p=l;
while(i<=mid && j<=r){
if (q[i]<=q[j]) m[p++]=q[i++];
else m[p++]=q[j++];
}
while(i<=mid)m[p++]=q[i++];
while(j<=r)m[p++]=q[j++];
while(--p>=l)q[p]=m[p];
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for(int i=0;i<n;i++)printf("%d ",q[i]);
}
四 二分(整数)
1 简要描述
单调一定可以二分,但是二分不一定单调,二分的核心思想是边界。整数二分的难点在于边界,不然可能陷入死循环,请谨慎操作。
两种模板:
i
- 确定mid=l+r+1>>1(右偏)
- 检查mid是否满足,满足l=mid,即[mid,r];不满足r=mid-1,即[l,mid-1]
- 继续循环
ii
- 确定mid=l+r>>(左偏);
- 检查mid是否满足性质,满足r=mid [l,mid];不满足l=mid,即[mid+1,r]
3。 继续循环
2 样例模板
解题思路
这道题麻烦点在于存在重复的数,即>=x的部分和<=的部分有重叠区域,如下图
所以实际求解时,我们只需要求出x1和x2
对于x1,我们可以理解为: >=x 的最左侧端点 因此套用检查条件q[mid]>=x
对于x2,我们可以理解为: <=x的最右侧端点 因此套用检查条件q[mid]<=x
实现部分参考原模板即可。
代码回顾 acw789题目链接
#include <iostream>
using namespace std;
const int N=1e5+10;
int q[N];
void two_divide(int q[],int n,int x){
int l=0,r=n-1,mid;
while(l<r){ //先求x1
mid=l+r>>1;
if (q[mid]>=x) r=mid;
else l=mid+1;
}
if (q[l]==x) printf("%d ",l); //检查是否存在元素,不存在就直接结束了
else {
printf("-1 -1\n");
return ;
}
l=0,r=n-1;
while(l<r){//再求x2
mid=l+r+1>>1;
if (q[mid]<=x)l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
int main(){
int n,k,x;
scanf("%d%d",&n,&k);
for (int i=0;i<n;i++)scanf("%d",&q[i]);
while(k--){
scanf("%d",&x);
two_divide(q,n,x);
}
}
五 二分(浮点数)
关于浮点数,没什么好说的,需要自行查看原题解
膜大佬!