772 字
2 分钟
排序 二分学习
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;}2.3 相关题目
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时
相关文章 智能推荐
1
高精度 学习记录
algorithm 高精度运算包括加法、减法、乘法和除法，适用于处理超出常规数据类型范围的大数。加法和减法通过模拟手动计算实现，乘法和除法则依次处理每位数字，注意前导零的去除。提供了相关的例题和参考代码以帮助理解和实现这些运算。
2
位运算、离散化和区间合并 算法学习
algorithm 介绍了位运算、离散化和区间合并的算法。位运算用于处理二进制数，离散化用于优化稀疏数据的存储和查询，区间合并则通过排序和覆盖判断快速合并多个区间。提供了相关例题和参考代码以帮助理解这些算法的应用。
3
前缀和、差分和双指针 算法学习
algorithm 介绍了前缀和、差分和双指针算法的原理和应用。前缀和用于快速计算数组区间和，差分用于高效处理区间更新，双指针法通过维护指针来优化查询效率。提供了相关例题及参考代码以帮助理解和应用这些算法。
4
面试算法学习1
algorithm 包含多个算法面试题及其解法，包括蛇形矩阵填充、单链表快速排序、寻找峰值、极小值、鸡蛋硬度问题、支持最小值检索的栈以及链表中环的入口节点的查找。每个题目附有详细描述、输入输出格式和示例代码。
5
JavaScript学习
FRONTEND JavaScript是一种动态、弱类型的解释型语言，具有轻量级、跨平台和事件驱动的特点。核心概念包括变量与数据类型、控制流、函数及异步编程。JavaScript可在浏览器和Node.js环境中运行，支持多种数据类型和操作，如对象、数组、解构赋值和模块化。异步编程使用回调函数、Promise和async/await来处理任务。