AcWing 107. 超快速排序
原题链接
简单
作者:
JY_ZKY
,
2022-02-25 12:57:12
,
所有人可见
,
阅读 130
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 501000;
int q[N],tmp[N],n,k;
ll merge_sort(int q[],int l ,int r)
{
if(l >= r) return 0;
int mid = l + r >> 1;
ll res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
int i = l,j = mid + 1,k = 0;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k ++] = q[i ++];
else
{
res += mid - i + 1;
tmp[k ++] = q[j ++];
}
}
while(i <= mid) tmp[k ++ ] = q[i ++];
while(j <= r) tmp[k ++ ] = q[j ++];
for(int i = l,j = 0; i <= r; i++ ,j ++)
q[i] = tmp[j];
return res;
}
int main()
{
while(cin >> n && n != 0)
{
for(int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
cout << merge_sort(q, 0, n-1) << endl;
}
return 0;
}