【归并排序】【快速排序】

【归并排序】【快速排序】

详细讲解见以下视频链接
归并排序视频链接
快速排序视频链接

个人理解：

归并排序：先分再排
快速排序：先排再分

归并排序代码：

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;vector<int>vr(500005),vp(500005);intn;voidmsort(intl,intr){if(l==r)return;//终止条件intmid=l+r>>1;msort(l,mid);//先分msort(mid+1,r);inti=l,k=l,j=mid+1;while(i<=mid&&j<=r)//再排{if(vr[i]<=vr[j])vp[k++]=vr[i++];elsevp[k++]=vr[j++];}while(i<=mid)vp[k++]=vr[i++];while(j<=r)vp[k++]=vr[j++];for(intit=l;it<=r;it++)vr[it]=vp[it];}signedmain(){cin>>n;for(inti=1;i<=n;i++)cin>>vr[i];msort(1,n);for(inti=1;i<=n;i++)cout<<vr[i]<<" ";return0;}

例题：

p1908
视频里有详解

代码：

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;vector<int>vr(500005),vp(500005);intn;intcns;voidmsort(intl,intr){if(l==r)return;intmid=l+r>>1;msort(l,mid);msort(mid+1,r);inti=l,k=l,j=mid+1;while(i<=mid&&j<=r){if(vr[i]<=vr[j])vp[k++]=vr[i++];elsevp[k++]=vr[j++],cns+=mid-i+1;//唯一区别}while(i<=mid)vp[k++]=vr[i++];while(j<=r)vp[k++]=vr[j++];for(intit=l;it<=r;it++)vr[it]=vp[it];}signedmain(){cin>>n;for(inti=1;i<=n;i++)cin>>vr[i];msort(1,n);cout<<cns<<endl;return0;}

【快速排序】代码

#include<bits/stdc++.h>usingnamespacestd;inta[100];voidksort(intl,intr){if(l==r)return;inti=l-1,j=r+1,x=a[l+r>>1];while(i<j)//先排{doi++;while(a[i]<x);doj--;while(a[j]>x);if(i<j)swap(a[i],a[j]);}ksort(l,j);//再分ksort(j+1,r);}signedmain(){for(inti=1;i<=10;i++)cin>>a[i];ksort(1,10);for(inti=1;i<=10;i++)cout<<a[i]<<" ";return0;}