AcWing 107. 超快速排序

2024-03-08 20:12

文章标签 快速排序 acwing 107

本文主要是介绍AcWing 107. 超快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int N=500000+10;//a 是原来的数组，temp 是临时数组
int a[N],temp[N];//因为元素有 500000 个，逆序对的数目可能会非常多
//假设按照降序排列，那么将有 n+(n-1)+(n-2)+...+1
//(1+n)*n/2
//超出了 int 的数据范围，所以需要使用 long long
//下面是归并排序
LL merge(int l,int r)
{if(l>=r)return 0;int mid=(l+r)>>1;//递归处理LL res=merge(l,mid)+merge(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(a[i]<=a[j])temp[k++]=a[i++];else{temp[k++]=a[j++];//左边的数组的下标一定小于右边的数组//此时的元素的数值反而大于右边的元素//符合逆序对的要求//所以添加到答案里面res+=mid-i+1;}}//等一个数组处理完之后，另一个数组大概率是没有处理完的//所以处理一下剩下的数组元素while(i<=mid)temp[k++]=a[i++];while(j<=r)temp[k++]=a[j++];//把临时数组的元素放回原来的数组//表示原来的元素被归并排序了for(i=l,j=0;i<=r;i++,j++)a[i]=temp[j];return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;while(cin>>n){if(n==0)break;for(int i=0;i<n;i++)cin>>a[i];//0 和 n-1 表示的是左右边界cout<<merge(0,n-1)<<endl;}return 0;
}