当前位置: 代码迷 >> 综合 >> 【数据结构】【归并排序】
  详细解决方案

【数据结构】【归并排序】

热度:118   发布时间:2023-09-07 05:36:47.0
#include<bits/stdc++.h>
using namespace std;
int k,n,ans=0;
int a[500100],b[500100];
void merge_sort(int l,int r) {if(l==r)return ;//一个数不用排int m=(l+r)>>1;merge_sort(l,m);merge_sort(m+1,r);int i=l,j=m+1,k=0;//i左边最小位置,j右边最小位置while(i<=m&&j<=r)if(a[i]<=a[j])b[++k]=a[i++];else ans+=m-i+1,b[++k]=a[j++];//加入右半段时,逆序对数增加while(i<=m)b[++k]=a[i++];//加入左边剩余的数while(j<=r)b[++k]=a[j++];//加入右边剩余的数for(i=1; i<=k; i++)a[l+i-1]=b[i];
}
int main() {scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d",&a[i]);merge_sort(1,n);for(int i=1;i<=n;i++)printf("%d ",b[i]);return 0;
}

 

  相关解决方案