题目描述
在这个问题中,您必须分析特定的排序算法----超快速排序。
该算法通过交换两个相邻的序列元素来处理 n
个不同整数的序列,直到序列按升序排序。
对于输入序列 9 1 0 5 4,超快速排序生成输出 0 1 4 5 9。
您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。
输入格式
输入包括一些测试用例。
每个测试用例的第一行输入整数 n,代表该用例中输入序列的长度。
接下来 n 行每行输入一个整数ai,代表用例中输入序列的具体数据,第 i 行的数据代表序列中第 i 个数。
当输入用例中包含的输入序列长度为0时,输入终止,该序列无需处。
输出格式
对于每个需要处理的输入序列,输出一个整数op,代表对给定输入排序所需的最小交换操作数,每个整占一行。
数据范围
0≤n<500000
,
一个测试点中,所有 n
的和不超过 500000。
0≤ai≤999999999
样例
输入样例:
5
9
1
0
5
4
3
1
2
3
0
输出样例:
6
0
时间复杂度(nlogn)
参考文献(蓝皮书)
C++ 代码
//题目大致:给定若干个个数组,求出每次排完序后交换次数最少的数量(只能相邻交换)
//思路:每次不交换前,可以设逆序对数量为m,每次交换后为m-1;
// 最后成为升序数组后的逆序对数量为0;
// 所以最少交换次数就是原数组的逆序对个数,由于数量为50w,故采用归并排序(o(nlogn))
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll q[N];
ll tmp[N];
int n;
ll cnt;//总数
void solve(ll q[],int l,int r)//归并排序
{
if(l>=r) return;
int mid=(l+r)>>1;
solve(q,l,mid);//递归左半
solve(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
{
tmp[k++]=q[j++];
cnt+=mid-i+1;//先交换到mid这个点,再递归后继续交换到该有的位置上
}
}
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];//将排完序后的数组装入q
}
int main()
{
while(cin>>n&&n)//只要输入n且n不为0
{
for(int i=0;i<n;i++) scanf("%lld",&q[i]);
cnt=0;//每次计算前清空
solve(q,0,n-1);
printf("%lld\n",cnt);
}
return 0;
}