冒泡排序 核心思想是相邻元素之间两两比较，将较大(或较小)的元素逐渐“冒泡”到待排序序列的末尾。具体来说，在第i轮排序中，从下标1开始遍历整个数组，对相邻的元素a[j]和a[j+1]进行比较，如果a[j]>a[j+1]，则交换它们的位置。循环执行n-1轮即可完成排序。
需要注意的，在冒泡排序中，如果在某一轮排序中没有进行任何元素交换，说明当前数组已经有序，可以直接退出循环，避免不必要的比较。
void bubbleSort(int a[],int n){//从小到大对数组a进行排序
for(int i=1;i<n; i++) {//比较n-1轮
bool flag=0; //标记本轮是否进行过交换
for(int j=1;j<=n-i;j++) { //第i轮比较n-i次
if(a[j]>a[j+1]){ //相邻元素比较
swap(a[j],a[j+1]); // 元素交换
flag=1; //进行了交换，则标记为1
}
}
if(flag==0) break;//本轮没有交换，则数组已经有序
}
}选择排序 核心思想是每次在待排序序列中找到最大(或小)值，将其放到有序区间的末尾。
void selectSort(int a[],int n){//从小到大对数组a进行排序
for(int i=1;i<n;i++) {
for(int j=i+1;j<=n;j++){//每轮下来，a[i]是最小值
if(a[i]>a[j]){
swap(a[i],a[j]);//元素交换
}
}
}
}插入排序 核心思想是将待排序序列分成前后2块，前一块：有序区间；后一块：无序区间。每次从无序区间中选择第一个元素，插入到有序区间中的合适位置，使得插入后有序区间仍然有序。
void insertSort(int a[],int n){
for(int i=2;i<=n;i++){
int curr=a[i]; //选择无序区间的第一个元素
for(int j=i-1;j>=1;j--){//找到有序区间的合适位置
if(a[j]<curr){
a[j+1]=curr;//插入到合适位置
break;
}
a[j+1]=a[j];
if(j==1){//如果到了数组头部，不再往前比较
a[1]=tmp;break;
}
}
}
}桶排序 桶排序也叫箱排序。工作原理是：统计每个元素出现的次数，然后利用桶的下标已经有序的原理，按照每个数出现的次数循环输出，因此，桶排序要求数组元素数值必须是小范围内的数！
for(int i=1;i<=n;i++){ //假设输入n个数字
cin>>x;
a[x]++; //统计x出现的次数
maxNum=max(a[x],maxNum);//找到最大的数字
}
for(int i=0;i<=maxNum;i++){//maxNum是输入的最大数字
while(a[i]--){
cout<<i<<' '; //排序结果
}
}计数排序 计数排序的思想：1、计算每个数出现了几次；2、求出每个数出现次数的前缀和；3、利用出现次数的前缀和从右边至左计算每个数的排名。
for(int i=1;i<=n;i++){ //假设输入n个数字
cin>>a[i];
cnt[a[i]]++; //统计a[i]出现的次数
maxNum=max(a[i],maxNum);//找到最大的数字
}
for(int i=1;i<=maxNum;i++){//maxNum是输入的最大数字
cnt[i]=cnt[i-1]+cnt[i]; //出现次数的前缀和
}
for(int i=n;i>=1;i--){//逆序求出每个数正确的排序位置
b[cnt[a[i]]--]=a[i]; //逆序是为了保证稳定性
}
for(int i=1;i<=n;i++) cout<<b[i]<<' ';//排序结果快速排序 选择一个参考值，将数组一分为二，使得数组的左侧都<=mid，数组的右侧都>=mid；然后继续对每个区间重复上述步骤，直到整个数组有序。
void qsort(int a[],int l,int r){ //快速排序
if(l>=r) return;
int mid=a[(l+r)/2],i=l,j=r;//mid是参考值选取
while(i<=j){
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j){
swap(a[i],a[j]);
i++;j--;
}
}
qsort(l,j);
qsort(i,r);
}快排可以直接调用<algorithm>中的sort()函数。
sort(begin(), end(), cmp);
begin() 是待排序数组的首地址
end() 是待排序数组的尾地址的下一个
cmp 是排序规则，默认是升序
归并排序 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
void msort(int a[],int b[],int l,int r){//归并排序
if(l>=r)return;
int mid=(l+r)/2,i=l,j=mid+1,k=l;//将数组一分为二
msort(l,mid);
msort(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],k++,i++;
while(j<=r)b[k]=a[j],k++,j++;
for(int i=l;i<=r;i++)a[i]=b[i];
}堆排序 堆排序是指利用堆这种数据结构所设计的一种排序算法。
（1）将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
（2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
（3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
#include<iostream>
using namespace std;
const int N=1e6+10;
int n,a[N],b[N],k=0; //k当前的堆的长度
void push(int x){ //插入数字
a[++k]=x;
int i=k;
while(i>1&&a[i]<a[i/2]){ //小于父节点
swap(a[i],a[i/2]);
i=i/2;
}
}
void pop(){ //删除最小数
a[1]=a[k];
k--;
int i=1;
while(i<=k&&2*i<=k){ //存在左孩子
if(2*i+1<=k&&a[2*i+1]<a[2*i]&&a[2*i+1]<a[i]){//右孩子更小
swap(a[i],a[2*i+1]);
i=2*i+1; //继续处理右孩子
}else if(a[2*i]<a[i]){ //只有左孩子更小
swap(a[i],a[2*i]);
i=2*i; //继续处理左孩子
}else{
break; //如果不比孩子小
}
}
}
void heapsort(){ //堆排序：从小到大
for(int i=1;i<=n;i++){
b[i]=a[1]; //获取队首
pop();//队首出队
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
push(x); //插入元素到优先队列
}
heapsort();
for(int i=1;i<=n;i++) printf("%d\n",b[i]);
return 0;
}整数二分
bool check(int x){/* ... */} // 检查x是否满足某种性质
//区间[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;//check()判断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;//check()判断mid是否满足性质
else r=mid-1;
}
return l;
}浮点数二分
bool check(double x){/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r){
const double eps=1e-6;//eps表示精度，取决于题目对精度的要求
while(r-l>eps){
double mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
return l;
}高精度加法 以字符串形式读入高精度数字，分别逆序存储到vector<int>中，通过高精度加法得到结果。
//C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A,vector<int> &B){
if(A.size()<B.size()) return add(B, A);
vector<int> C;
int t=0;
for(int i=0;i<A.size();i++ ){
t+=A[i];
if(i<B.size()) t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(t);
return C;
}高精度减法
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B){
vector<int> C;
for (int i=0,t=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size()) t-=B[i];
C.push_back((t+10)%10);
if(t<0) t=1;
else t=0;
}
while(C.size()>1&&C.back()==0) C.pop_back();//去前导0
return C;
}高精度乘低精度
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b){
vector<int> C;
int t=0;
for(int i=0;i<A.size()||t;i++ ){
if(i<A.size()) t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0) C.pop_back();//去前导0
return C;
}高精度除以低精度
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A,int b,int &r){
vector<int> C;
r=0;
for(int i=A.size()-1;i>=0;i-- ){
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());//反转
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}一维前缀和
S[i]=a[1]+a[2]+...+a[i]
a[l]+...+a[r]=S[r]-S[l-1] //区间[[l,r]的和一维差分
给区间[l, r]中的每个数加上c：B[l]+=c, B[r+1]-=c位运算
求n的第k位数字: n>>k&1
返回n的最后一位1：lowbit(n)=n&-n双指针算法
for(int i=0,j=0;i<n;i++ ){
while(j<i&&check(i,j)) j++ ;
//具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作