P.S.接下来的空间复杂度均为额外的空间复杂度
第一部分、排序
排序这东西，一般是和贪心搭配食用，因为贪心很多时候都是取最值，需要排个序。
1，冒泡排序
冒泡排序的核心思想是通过相邻元素的比较和交换，使较大（或较小）的值逐步移动到数列的末端。
时间复杂度 O(n^2)
空间复杂度 O(1)
#include<bits/stdc++.h>
using namespace std;
int a[1001],n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];//输入
for(int i=1;i<=n;i++)
for(int j=1;j<=n-i;j++)
if(a[j]>a[j+1]) swap(a[j],a[j+1]);//如果此数大于后面的数，就与后面的数交换
for(int j=1;j<=n;j++) cout<<a[j]<<" ";//输出
}
2,选择排序
选择排序的核心思想是每次从待排序的数据元素中选择最小（或最大）的一个元素，将其放到已排序序列的末尾（或开头）。
时间复杂度 O(n^2)
空间复杂度 O(1)
#include<bits/stdc++.h>
using namespace std;
int a[1001],n,m=pow(10,9)+1,l;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];//输入
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++)
if(a[j]<m){
m=a[j];
l=j;
}//选出从i到n里最小的数
swap(a[l],a[i]);//将最小的数放到开头
m=pow(10,9)+1;
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";//输出
}
3、桶排序
桶排序的核心思想是把数组划分为k个大小相同子区间(桶),每个子区间各自排序,最后合并
(k为元素最大值)
时间复杂度 O(n+k)
空间复杂度 O(n+k)
#include<bits/stdc++.h>
using namespace std;
int n,a[1000001],x;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
a[x]++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=a[i];j++) cout<<i<<" ";
}
}
4，sort排序
…没有核心思想，主打一个脑子不够，函数来凑
时间复杂度 O(n \log_2 n)
空间复杂度 O(1)
#include<bits/stdc++.h>
using namespace std;
int a[10000001],n,m=10000001,l,b;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
}
5、插入排序
#include<bits/stdc++.h>
using namespace std;
int n,x,a[1001];
int main(){
cin>>n;
for(int i=1;i<=n;i++) {
cin>>x;
int j=i-1;
while(j>=0&&a[j]>x){
a[j+1]=a[j];
j--;
}
a[j+1]=x;
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}
O(n^2)
6、归并排序
归并排序的核心思想是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
时间复杂度 O(n \log_2 n)
空间复杂度 O(n)
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],cnt,b[100005];
void guibing_sort(int l,int r){
if(l==r) return ;
int mid=(l+r)/2;
guibing_sort(l,mid);
guibing_sort(mid+1,r);
int i=l,j=mid+1,k=l;
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(int p=l;p<=r;p++) a[p]=b[p],b[p]=0;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
guibing_sort(1,n);
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}
O(n \log_2 n)
7、堆排序
堆排序本质就是把所有数丢进优先队列，通过优先队列自动排序的性质排序。
时间复杂度 O(n \log_2 n)
空间复杂度 O(n)
#include<bits/stdc++.h>
using namespace std;
int n,x;
priority_queue< int,vector<int>,greater<int> >q;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>x,q.push(x);
while(!q.empty()){
cout<<q.top()<<" ";
q.pop();
}
}
8、计数排序
计数排序的核心思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。然后就可以将x直接存放到最终的输出序列的正确位置上
时间复杂度 O(n+k)
空间复杂度 O(n+k)
#include<bits/stdc++.h>
using namespace std;
int a[1005],c[1005],sum[1005],k;
int main() {
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
++c[a[i]];
k=max(k,a[i]);
}
for(int i=1;i<=k;++i) c[i]+=c[i-1];
for(int i=n;i>=1;--i){
sum[c[a[i]]]=a[i];
c[a[i]]--;
}
for(int i=1;i<=n;++i) cout<<sum[i]<<" ";
}
第2部分、高精度
嗯，众所周知，long long的存储范围是 -2^{64} ~ 2^{64}-1，蛋柿如果超过这个范围了怎么办呢？
当然是用long double
当然是用string
当然是凉拌
当然是用高精度啦！
高精度的主要思想就是逐位做运算，比如高精加就是一位位加。
废话不多说，这就上模板！
1，高精加
#include<bits/stdc++.h>
using namespace std;
string a,b;
int c[1001],d[1001],f[1001];
int main(){
cin>>a>>b;
int n=a.length(),m=b.length(),len=max(n,m);
for(int i=0;i<n;i++) c[i]=a[n-i-1]-'0';
for(int i=0;i<m;i++) d[i]=b[m-i-1]-'0';
for(int i=0;i<len;i++){
f[i]+=c[i]+d[i];
f[i+1]+=f[i]/10;
f[i]%=10;
}
if(f[len]) len++;
for(int i=len-1;i>=0;i--) cout<<f[i];
}
3，高精乘
#include<bits/stdc++.h>
using namespace std;
int x1[1001],x2[1001],c[1001];
int main(){
string a,b;
cin>>a>>b;
int lena=a.size(),lenb=b.size();
int lenc=lena+lenb;
for(int i=0;i<lena;i++) x1[lena-i]=a[i]-'0';
for(int i=0;i<lenb;i++) x2[lenb-i]=b[i]-'0';
for(int i=1;i<=lena;i++)
for(int j=1;j<=lenb;j++){
c[i+j-1]+=x1[i]*x2[j];
c[i+j]+=c[i+j-1]/10;
c[i+j-1]%=10;
}
string ans;
while(lenc>1&&c[lenc]==0) lenc--;
for(int i=lenc;i>=1;i--) cout<<c[i];
}
第 X 部分、STL
STL，俗称懒人的福音。
老师：今天我们来讲二分…
我：没事，反正STL里有
老师：今天我们来讲排序…
我，没事，反正STL里有
…
STL一般能减少许多代码量，十分豪用 
1、vector
vector，学名向量or动态数组。
说白了就是个数组，一般只会在写了个代码结果发现系统栈炸了的时候或是懒得算接下来这个该放数组第几位的时候会用。
1、定义
vector<typename>name
typename里可以填任何基本数据类型（还有结构体），如char，string，甚至是再套一层vector。
示例：
vector<int>v;
vector<char>v;
vector<node>v;
vector< vector<int> >v;//两个>之间要加空格，防止识别成>>
2、访问方式
支持下标访问以及迭代器访问。
(1)下标访问
for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
(2)迭代器访问
for(int it:v) cout<<it<<" ";
3、函数
他有这些函数
| 名称 | 作用 | 时间复杂度 | |
|---|---|---|---|
| push_back(x) | 将一个数x插入到vector数组最后 | O(1) | |
| pop_back() | 将vector数组的最后一项删除(弹出) | O(1) | |
| size | 求出vector数组中元素的个数 | O(1) | |
| insert(it，x) | 在迭代器it后插入一个元素x |
O(N) | |
| erase | 删除单个元素或一个区间内的所有元素 | O(N) | |
| clear | 清空vector数组中的元素 | O(N) |
