目錄

• 歸并排序
• 逆序?qū)Φ臄?shù)量
• 超快速排序

歸并排序

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N=1e5+10; int a[N],temp[N],n; void merge_sort(int l,int r) {if(l>=r) return;int mid=l+r>>1;merge_sort(l,mid),merge_sort(mid+1,r);int k=0;int i=l;int j=mid+1;while(i<=mid&&j<=r){if(a[i]<=a[j]) temp[k++]=a[i++];else temp[k++]=a[j++];}while(i<=mid) temp[k++]=a[i++];while(j<=r) temp[k++]=a[j++];for(int i=l,j=0;i<=r;i++) a[i]=temp[j++]; } int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>a[i];merge_sort(0,n-1);for(int i=0;i<n;i++) cout<<a[i]<<" ";return 0; }

逆序?qū)Φ臄?shù)量

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N=1e5+10; int a[N],temp[N],n; long long int res=0; void merge_sort(int l,int r) {if(l>=r) return;int mid=l+r>>1;merge_sort(l,mid),merge_sort(mid+1,r);int k=0;int i=l;int j=mid+1;while(i<=mid&&j<=r){if(a[i]<=a[j]) temp[k++]=a[i++];else res+=mid-i+1,temp[k++]=a[j++];}while(i<=mid) temp[k++]=a[i++];while(j<=r) temp[k++]=a[j++];for(int i=l,j=0;i<=r;i++) a[i]=temp[j++]; } int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>a[i];merge_sort(0,n-1);cout<<res<<endl;return 0; }

超快速排序

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N=1e5*5+10; int a[N],temp[N],n; long long int res; void merge_sort(int l,int r) {if(l>=r) return;int mid=l+r>>1;merge_sort(l,mid),merge_sort(mid+1,r);int k=0;int i=l;int j=mid+1;while(i<=mid&&j<=r){if(a[i]<=a[j]) temp[k++]=a[i++];else res+=mid-i+1,temp[k++]=a[j++];}while(i<=mid) temp[k++]=a[i++];while(j<=r) temp[k++]=a[j++];for(int i=l,j=0;i<=r;i++) a[i]=temp[j++]; } int main(void) {while(cin>>n,n){for(int i=0;i<n;i++) cin>>a[i];merge_sort(0,n-1);cout<<res<<endl;res=0;}return 0; } 《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的【AC Saber】归并排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。