1.归并排序
主要运用到的的思想：分治、递归
功能：1.数组进行排序。
2.计算数组中的逆序对的个数。
时间复杂度：稳定的O（nlogn）
空间复杂度：O（n）
附上模板代码：
#include<bits/stdc++.h>usingnamespacestd;longlongMerge(inta[],intb[],ints,intm,inte){inti=s,j=m+1,k=s;longlongans=0;while(i<=m&&j<=e){if(a[i]<=a[j])b[k++]=a[i++];else{b[k++]=a[j++];//求逆序对ans+=mid-i+1;}}while(i<=m)b[k++]=a[i++];while(j<=e)b[k++]=a[j++];for(intn=s;n<=e;n++)a[n]=b[n];returnans;}voidmergesort(inta[],intb[],ints,inte){longlongans=0;if(s<e){intm=(s+e)/2;mergesort(a,b,s,m);mergesort(a,b,m+1,e);ans+=Merge(a,b,s,m,e);}}inta[100005];intb[100005];intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}mergesort(a,b,1,n);for(inti=1;i<=n;i++){cout<<a[i]<<" ";}return0;}2.冒泡排序
主要思想：不断交换相邻两个逆序的元素。最终将最大排在最后，类似于可乐冒泡。
时间复杂度：O（n²)
空间复杂度：O（n）
#include<bits/stdc++.h>usingnamespacestd;voidbubbleSort(inta[],intn){for(inti=1;i<n;i++){//n-1趟for(intj=1;j<n-i+1;j++){//除去已经排好的i个，所以是枚举n-i+1个if(a[j+1]<a[j]){intt=a[j+1];a[j+1]=a[j];a[j]=t;}}}}inta[100005];intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}bubbleSort(a,n);for(inti=1;i<=n;i++){cout<<a[i]<<" ";}return0;}3.选择排序
主要思想：通过与n次（n为数组的长度）的选择，可以将每次当前为选择的最大（最小）的元素放在相应位置上。
时间复杂度：O（n²)
空间复杂度：O（n）
#include<bits/stdc++.h>usingnamespacestd;voidselectSort(inta[],intn){for(inti=1;i<=n;i++){intMin=i;for(intj=i+1;j<=n;j++){if(a[j]<a[Min]){Min=j;}}intt=a[Min];a[Min]=a[i];a[i]=t;}return;}inta[100005];intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}selectSort(a,n);for(inti=1;i<=n;i++){cout<<a[i]<<" ";}return0;}4.插入排序
主要思想：两层for循环，第一层表示接下来要将前i个排好序，第二个for循环，用于通过比较判断第i个元素应该放在1~i的哪个位置上
时间复杂度：O（n²)
空间复杂度：O（n）
#include<bits/stdc++.h>usingnamespacestd;voidInsertSort(vector<int>&a,intlen){for(inti=1;i<len;++i){inttemp=a[i];for(intj=i-1;j>=0;--j){if(temp<a[j]){a[j+1]=a[j];}else{a[j+1]=temp;break;}}}return;}intmain(){intn;cin>>n;vector<int>a(n);for(inti=0;i<n;++i){cin>>a[i];}InsertSort(a,n);for(inti=0;i<n;++i){cout<<a[i]<<" ";}return0;}5.希尔排序
主要思想：可以认为是插入排序的plus版，内部多了有个增量因子（i=3*i+1），作为每轮插入排序中第二个for‘循环每次结束后的增加量
时间复杂度：O（n^1.5)左右
空间复杂度：O（n）
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintMAXN=100005;inta[MAXN],n;voidinsertionSort(inta[],intn,intg){for(inti=1+g;i<=n;i++){inttemp=a[i],j=i-g;for(;j>=1;j-=g){if(a[j]>temp){a[j+g]=a[j];}elsebreak;}a[j+g]=temp;}}voidshellSort(inta[],intn){vector<int>G;for(inti=1;i<=n;){G.push_back(i);i=3*i+1;}for(inti=G.size()-1;i>=0;i--){insertionSort(a,n,G[i]);}}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d",&a[i]);}shellSort(a,n);for(inti=1;i<=n;i++){printf("%d ",a[i]);}return0;}
