AcWing基础课学习
排序
1. 快速排序
1. 原理
对于一段无序的数列，若要将其排序，可以以此步骤进行：
- 对于一段的数列，可以先任取一点
mid作为判断点。(其中mid一般为数列中点) - 对于这段数列进行一次遍历，将大于
mid的数放于右端，小于mid的数放于左端。 - 然后对于分配过的序列，选取其
[l,p],[p+1,r]两个子段继续上述操作，直到长度为1。(其中p为上述左右两端的分界点)
2. 具体实现(代码)
本代码思路参考自y总
void quick_sort(int a[],int l,int r){
if(l>=r) return;//设置退出条件
int i=l-1,j+1,mid = a[l+r>>1];//设置判断点
while(i<j){
do i++;while(a[i]<mid);
do j--;while(a[j]>mid);
if(i<j) swap(a[i],a[j]);
}
quick_sort(a,l,j);//继续对子段排序
quick_sort(a,j+1,r);
}
- 时间复杂度：O(N*logN)
3. 相关题目
2. 归并排序
1. 原理
对于一段无序的数列，与快速排序相似，若要将其排序，可以以此步骤进行：
- 对于一段的数列，可以先任取一点
mid作为分割点。(其中mid一般为数列中点) - 先选取其
[l,mid],[mid+1,r]两个子段继续排序，并假定其已经排序完成。 - 然后对于已经排序过的两段子段，按照排序顺序先放入
b数组中，然后再将排序过的数列覆盖原数列。
2. 具体实现(代码)
本代码思路参考自y总
void merge_sort(int a[],int b[],int l,int r){
if(l>=r) return;//设置退出条件
int mid = l+r>>1,i=l,j=mid+1,k=0;//设置分割点
merge_sort(a,b,l,mid);merge_sort(a,b,mid+1,r);//先对子段排序
while(i<=mid&&j<=r)
if(a[i]<=a[j]) b[k++] = a[i++];
else b[k++] = a[j++];
while(i<=mid) b[k++]=a[i++];
while(j<=r) b[k++]=a[j++];
for(i=l,j=0;i<=r;i++,j++) a[i]=b[j];
}
- 时间复杂度：O(N*logN)
3. 相关应用
- 求逆序对
当用归并排序对数组进行排序时，可以发现，当出现a[i]>b[j]时，即出现了逆序对，且对于当前a[j]来说，会出现mid-i+1个逆序对(即a[j]与[i,mid]共mid-i+1个数配对组合成逆序对)。由此我们可以在排序时求出对应数列中存在的逆序对。
long long merge_sort(int a[],int b[],int l,int r){
if(l>=r) return 0;
int mid = l+r>>1,i=l,j=mid+1,k=0;
long long ans = merge_sort(a,b,l,mid)+merge_sort(a,b,mid+1,r);
while(i<=mid&&j<=r)
if(a[i]<=a[j]) b[k++] = a[i++];
else ans += mid-i+1,b[k++]=a[j++];
while(i<=mid) b[k++] = a[i++];
while(j<=r) b[k++] = a[j++];
for(i=l,j=0;i<=r;i++,j++) a[i]=b[j];
return ans;
}
4. 相关题目
二分
1. 整数二分
1.1 算法原理
对于一个单调的队列，我们可以通过其单调的特性，对于要找到的数k可以通过以下方法找到：
- 先确定寻找的范围
l和r- 当
l<r时，先取范围中点mid，将区间[l,r]分为[l,mid]和[mid+1,r]（此时mid=l+r>>1）或[l,mid-1]和[mid,r]（此时mid=l+r+1>>1）- 然后，在
l<r条件下，根据check(mid)函数，对l，r进行更新，直到l>=r
1.2 代码实现
本代码思路参考自y总
//将区间[l,r]分为[l,mid]和[mid+1,r]
int bsearch_1(int l,int r){
while(l<r){
int mid = l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}return l;
}
//将区间[l,r]分为[l,mid-1]和[mid,r]
int bsearch_2(int l,int r){
while(l<r){
int mid = l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1
}
}
1.3 相关题目
2. 浮点数二分
2.1 算法原理
对于一个单调的队列，我们可以通过其单调的特性，与整数二分相似，对于要找到的数k可以通过以下方法找到：
- 先确定寻找的范围
l和r- 当
r-l>eps时，先取范围中点mid，mid=(l+r)/2- 然后，在
r-l>eps条件下，根据check(mid)函数，对l，r进行更新，直到r-l<=eps
2.2 代码实现
本代码思路参考自y总
double bsearch(double l,double r){
while(r-l>eps){
double mid = (l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}return l;
}
京公网安备 11010502036488号