常用算法模板小总结

判断是否是闰年

bool isleapYear(int y){ return (y%4==0&&y%100!=0)||(y%400==0); }

判断是否是素数

int is_prime(int n) { if(n<=1) return 0; int m=floor(sqrt(n)+0.5); for(int i=2;i<=m;i++) if(n%i==0) return 0; return 1; }

埃拉托尼斯筛法

void Prime() { for (int i=0; i<MAXN; i++) prime[i]=1; //先把每个数都定义为素数 prime[0]=prime[1]=0; for (int i=2; i<MAXN; i++) { if (prime[i]) for (int j=i*2; j<MAXN; j+=i) prime[j] = 0; //将i的倍数标记为合数 } }

欧拉筛 原理：“最小质因数 × 最大因数（非自己） = 这个合数” 判断1~n哪些是素数

//prime[]数组判断是否筛选过，ans[]数组储存质数 void Prime(int n){ int count=0; for(int i=2;i<=n;i++){ if(prime[i]==0) ans[++count]=i; for(int j=1;j<=count&&i*ans[j]<=n;j++){ prime[i*ans[j]]=1; //保证为最小质因数 if(i%ans[j]==0) break; } } }

辗转相除法求最大公约数

long long gcd(long long a,long b){ return b==0?a:gcd(b,a%b); }

因为最大公约数最小公倍数=ab,所以求出最大公约数，便能求出最小公约数。

快速幂

如果将 a自乘一次，就会变成a^2 , 再把a ^2自乘一次就会变成a ^ 4,依次类推。把幂如11表示成（1011）2，就相当于a ^ 11= a ^8 *a ^2 * a.,于是只要循环幂就行。

typedef long long ll; ll quickPower1(int a,int b){ ll ans=1,base=a; while(b>0){//b是个二进制数 //如果二进制最后一位是一则乘上相应数 if(b&1) ans*=base; //自乘 base*=base; b>>=1;//右移一位 } return ans; }

从头开始。若当前 pp 为偶数，咱们不着急，只需把 xx 自乘，然后 p/=2 （即考虑下一层，下几层会帮我们乘上 (x²⁾(p/2）, 若当前 p为奇数，说明 x^p =x∗(x ^2) ^(p−1)/2 那个x存在，ans*=x,然后依次类推

ll quickPower2(int a,int b){ ll ans=1; while(b){ if(b%2==1){ ans*=a; } //一直除以2，最后会等于一 b/=2; //下一个循环a自乘了 a=a*a; } return ans; }

排序

冒泡排序 p是数组名，n为数组大小 时间复杂度为O(n^2) 增加一个flag判断是否已经排好，如果无交换证明排好

bool flag=true; void bubleSort(int *p,int n){ for(int i=0;i<n-1&&flag;i++){ flag=false; for(int j=0;j<n-i-1;j++){ if(*(p+j)>*(p+j+1)){ int t=*(p+j); *(p+j)=*(p+j+1); *(p+j+1)=t; flag=true; } } } }

选择排序 选择排序 时间复杂度为O(n^2)

void selectSort (int *p,int n){ int k; for(int i=0;i<n;i++){ k=i; for(int j=i+1;j<n;j++){ if(*(p+k)>*(p+j)) k=j;//比当前还要小就更新k } if(i!=k){ int t=*(p+k); *(p+k)=*(p+i); *(p+i)=t; } } }

插入排序 时间复杂度O(n^2)

void insertSort(int *p,int n){ int j,t; //假设第一个数已排好 for(int i=1;i<n;i++){ t=*(p+i);//没有排过的数据 for( j=i-1;j>=0&&*(p+j)>t;j--){ *(p+j+1)=*(p+j);//后移一位 } *(p+j+1)=t;//插入 } }

希尔排序 排序算法的突破 思路：先让整个序列局部有序，每次一小段插入排序，再对整体使用插入排序。

//希尔排序 void shellSort(int *p,int n){ int i,j; int t=n;//增量 int temp; do{ t=t/3+1;//减小步长 for(i=t+1;i<n;i++){ temp=*(p+i); for(j=i-t;j>=0&&*(p+j)>temp;j-=t){ *(p+j+t)=*(p+j);//后移 } *(p+j+t)=temp; } } while(t>1); }

归并排序 思想：把整个数组递归分成小数组，给小数组排好序后，在合并排大数组。

//归并排序 //时间复杂度O(nlogn) void merge_sort(int *A,int x,int y,int *T){ if(y-x>1){ //中间 int m=x+(y-x)/2; //p为左边起始 q为右边起始 i为临时数组起始 int p=x,q=m,i=x; merge_sort(A,x,m,T); merge_sort(A,m,y,T); //归并 while(p<m||q<y){ //q大于等于y说明右半部分已经结束 if(q>=y||(p<m && A[p]<=A[q])) T[i++]=A[p++]; //从右半数组复制 else T[i++]=A[q++]; } //临时数组复制到原数组 for(i=x;i<y;i++) A[i]=T[i] ; } }

逆序对问题 给定一列数a1,a2,a3,a4,……an,求他逆序对数，即有多少对（i，j）使得i<j,ai>aj;

在归并排序中，复制右边数组时，左边还没有复制的数就是比右边大的数，所以只要把else T[i++]=A[q++];改成else{T[i++]=A[q++],cnt+=m-p;}

桶排序

把所有的数先按照个位放入队列，再依次取出，再按照十位 放入队列 依次类推

void radixSort(int *A,int n){ // int maxn=*A; //寻找最大的数 for(int i=0;i<n;i++){ if(*(A+i)>maxn) maxn=*(A+i); } //最大数的位数 int maxlength; string a=maxn+""; maxlength=a.length(); //设置数的桶 queue<int> q[10]; for(int i=0,l=1;i<maxlength;i++,l*=10){ //取出每一个数 for(int j=0;j<n;j++){ // int yu=*(A+j)/l%10; q[yu].push(*(A+j)); } //取出 int index=0; for(int k=0;k<10;k++){ while(!q[k].empty()){ *(A+index++)=q[k].front(); q[k].pop(); } } } }

堆排序

堆：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。 或者每个节点的值都小于或等于其左右孩子结点的值，称为小顶堆。

void HeapAdjust(int *A,int s,int m){ //temp储存临时子树节点 int temp,j; temp=*(A+s-1); //子树节点是父节点的两倍 for(j=2*s;j<=m;j*=2){//查找子树 if(j<m&&*(A+j-1)<*(A+j)) ++j;//左子节点小于右节点 if(temp>=*(A+j-1)) break; // *(A+s-1)=*(A+j-1);//子树根节点为大 //子节点点为根 s=j; } //把根节点的值放到需要的地方 *(A+s-1)=temp; } void HeapSort(int *A,int n){ int i; //对非叶子节点 调整为大顶堆 for(int i=n/2;i>0;i--) HeapAdjust(A,i,n); // for(int i=n;i>1;i--){ //将最大的数与末尾交换 int t=*A; *A=*(A+i-1); *(A+i-1)=t; //交换后将剩下的数变为大顶堆 HeapAdjust(A,1,i-1); } }

快速排序 把比一个数小的放右边，大的放左边。

//快速排序 //寻找轴枢的方法 int Partition(int *A,int low,int high){ int pivotkey; //以第一个数为基准 pivotkey=*(A+low); //左指针小于右指针才进行 while(low<high){ //当右边的数大于轴枢的数 while(low<high&&*(A+high)>=pivotkey) high--; //把比轴枢小的数放左边 *(A+low)=*(A+high); while(low<high&&*(A+low)<=pivotkey) low++; *(A+high)=*(A+low); } *(A+low)=pivotkey; return low; } int QuickSort(int *A,int low,int high,int k){ int pivot;//轴枢位置 if(low<high){ pivot=Partition(A,low,high); QuickSort(A,low,pivot-1); QuickSort(A,pivot+1,high); } }

快速选择问题 轴枢编号是几就是第几小

if(k==pivot+1) return *(A+pivot); else if(k<pivot) QuickSort(A,low,pivot-1,k); else QuickSort(A,pivot+1,high,k);

持续更新