AcWing 107. 超快速排序
原题链接
简单
作者:
KaiWings-X
,
2024-07-27 00:17:45
,
所有人可见
,
阅读 5
/* 序列排序的最小交换操作数 == 原序列中的逆序对数 */
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 500010;
int q[N], tmp[N]; // tmp为辅助数组,用于暂存局部归并的序列
int n; // 每次输入的长度
LL res = 0; // 存储每次序列排序时元素交换的次数
// 采用归并排序求逆序对个数最高效
LL merge_sort(int q[], int l, int r)
{
// 递归临界条件
if (l == r) return 0;
// l != r 时,进行归并处理
else
{
// ①找中点
int mid = l + r >> 1;
// ②进行左子区间和右子区间的递归
LL ans = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
// ③归并操作,将每次递归过程中的左右子区间排序合并
int k = l, i = l, j = mid + 1;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k++] = q[i++];
else
{
tmp[k++] = q[j++];
ans += mid - i + 1;
}
}
// 扫尾处理
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(int i = l; i <= r; i++) q[i] = tmp[i];
return ans;
}
}
int main()
{
ios :: sync_with_stdio(false); // 关闭同步,提高cin和cout的效率
while(cin >> n && n) // 获取每次输入的长度,直到输入0,退出循环
{
for(int i = 0; i < n; i++) cin >> q[i];
res = merge_sort(q, 0, n - 1);
cout << res <<endl;
}
return 0;
}