几种算法简介(一)
1.快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e6+5; ll A[maxn]; int part(ll a[],int lo,int hi) //返回分界点 { swap(a[lo],a[lo+rand()%(hi-lo+1)]); ll temp=a[lo]; int u=lo; while(lo<hi) { if(a[lo]<=temp&&a[hi]>=temp) { lo++; hi--; } else if(a[lo]<=temp) lo++; else if(a[hi]>=temp) hi--; else swap(a[lo],a[hi]); } lo=(a[lo]<=temp)?lo:lo-1; swap(a[lo],a[u]); return lo; } void quick_sort(ll a[],int lo,int hi) { if(lo>=hi) return; int r=part(a,lo,hi); quick_sort(a,lo,r-1); quick_sort(a,r+1,hi); } |
2.归并排序与有序数列合并
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e6+5; ll A[maxn]; void Merge(ll a[],int lo,int mid,int hi) { if(a[mid]<=a[mid+1]) return; ll* B=new ll[mid-lo+1]; for(int i=0;i<mid-lo+1;i++) B[i]=a[lo+i]; int i=0,j=mid+1,k=0; while(i<=mid-lo&&j<=hi) a[lo+k++]=(B[i]<=a[j])?B[i++]:a[j++]; while(i<=mid-lo) a[lo+k++]=B[i++]; } void mergesort(ll a[],int lo,int hi) { if(lo>=hi) return; int mid=(lo+hi)>>1; mergesort(a,lo,mid); mergesort(a,mid+1,hi); Merge(a,lo,mid,hi); } |
3.求逆序对个数(sum记录逆序对个数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e6+5; ll A[maxn],sum=0; void Merge(ll a[],int lo,int mid,int hi) { if(a[mid]<=a[mid+1]) return; ll* B=new ll[mid-lo+1]; for(int i=0;i<mid-lo+1;i++) B[i]=a[lo+i]; int i=0,j=mid+1,k=0; while(i<=mid-lo&&j<=hi) { if(B[i]<=a[j]) a[lo+k++]=B[i++]; else { a[lo+k++]=a[j++]; sum+=mid-lo-i+1; } } while(i<=mid-lo) a[lo+k++]=B[i++]; } void mergesort(ll a[],int lo,int hi) { if(lo>=hi) return; int mid=(lo+hi)>>1; mergesort(a,lo,mid); mergesort(a,mid+1,hi); Merge(a,lo,mid,hi); } |
