分治——hyl天梦
分治
什么是分治?
顾名思义,分而治之(废话),他可以把一个复杂的问题简单化,从全部到局部,逐渐缩小问题规模,从而变得更高效。
怎么变得高效
- 下面举两个因为分治而变得高效的排序算法,相信大家也早有耳闻。
快速排序
- 思路:首先##随便##找一个轴值,把所有比轴值小的数排在左边,比轴值大的数排在右边然后再在轴值左边和右边分别递归重复这一步骤。
- 代码:
void qsort(int l,int r) { if(l>=r) return; ll i=l,j=r,mid=a[l+r>>1];//这里把随机弄成取中间数了,也可以去其他数 for(int h=l;h<=r;h++) { if(a[h]>mid) c[j--]=a[h]; if(a[h]<mid) c[i++]=a[h]; } for(int p=i;p<=j;p++) c[p]=mid; for(int h=l;h<=r;h++) a[h]=c[h]; qsort(l,i-1); qsort(j+1,r); }
归并排序
- 思路:把序列平均分成两段,然后归并
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<sstream> #include<queue> #include<vector> #define ll long long #define dd double #define N 2000001 using namespace std; ll a[N],c[N],n; void msort(ll l,ll r) { if(l>=r) return; ll mid=l+r>>1,i=l,j=mid+1,tail=l; msort(l,mid); msort(mid+1,r); while(i<=mid&&j<=r) { if(a[i]<=a[j]) c[tail++]=a[i++]; else c[tail++]=a[j++]; } while(i<=mid) c[tail++]=a[i++]; while(j<=r) c[tail++]=a[j++]; for(int h=l;h<=r;h++) a[h]=c[h]; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; msort(1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" "; return 0; }
相关推荐
Ghero 2020-08-09
数据与算法之美 2020-06-10
风吹夏天 2020-02-17
yishujixiaoxiao 2020-02-02
troysps 2019-12-30
Oudasheng 2019-12-19
shawsun 2019-12-23
baike 2019-12-15
蜗牛慢爬的李成广 2019-12-03
蜗牛慢爬的李成广 2019-11-09
风吹夏天 2019-11-03
seekerhit 2019-10-19
微分 2014-05-25
duyifei0 2019-06-27
wonner 2017-10-05
OpenPI 2019-05-29
linergou 2016-12-26