逆序对(归并排序)
Description
在这个问题中,你需要分析一个对n个不同数排序的算法。该算法主要通过交换相邻数直到序列有序(升序)。比如:对输入序列
9 1 0 5 4
经过一系列交换后变成有序序列
0 1 4 5 9
你的任务是计算将序列变成有序最少需要经过多少次交换。
Input
输入包含多组测试数据。每组第一个是整数n<500,000,表示输入序列的长度,接下来是n行,每行有一个整数ai。当n=0时表示结束。
Output
对每一组输入,输出该序列变成有序所需要交换的最少的次数。
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
解题思路:看到这个题按照题目意思“要通过交换相邻数直到序列有序(升序)”这是什么?冒泡排序?虽然冒泡排序就是基于这种思想,可是O(n^2)的时间
复杂度并不允许我这么搞,那该怎么办?
模拟原始做法:
对于数组:4 8 2 7 5 6 1 3
1 4 8 2 7 5 6 3------>6次
1 2 4 8 7 5 6 3------>2次
1 2 3 4 8 7 5 6------>5次
1 2 3 4 5 8 7 6------>2次
1 2 3 4 5 6 8 7------>2次
1 2 3 4 5 6 7 8------>1次
在模拟过程中,我们发现每次都是找到一个最小的然后移到最前面,但是除了这个最小的,其他数的相对次序并没有改变,所以我们可以将原始做法换一种表述方式:
找到最小的,统计它前面有多少个数比它大,然后加入结果,将这个最小的删去。如此反复。
1.归并排序是利用归并的思想实现的排序方法,在这里插入图片描述该算法采用经典的分治策略
2.归并排序是稳定排序
3.归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。
例子:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
#define maxn 500010
LL a[maxn];
LL temp[maxn];
LL sum;
void Merge(int l,int r,int m)
{
int i=l;
int j=m+1;
int k=l;
while(i<=m&&j<=r)
{
if(a[i]>a[j])
{
sum+=m-i+1;
temp[k++]=a[j++];
}
else
{
temp[k++]=a[i++];
}
}
while(i<=m)
{
temp[k++]=a[i++];
}
while(j<=r)
{
temp[k++]=a[j++];
}
for(i=l; i<=r; i++)
{
a[i]=temp[i];
}
}
void mergesort(int l,int r)
{
if(l<r)
{
int mid=(l+r)/2;
mergesort(l,mid);
mergesort(mid+1,r);
Merge(l,r,mid);
}
}
int main()
{
int n,i;
while(~scanf("%d",&n))
{
if(n==0)
break;
for(i=0; i<n; i++)
{
cin>>a[i];
}
sum=0;
mergesort(0,n-1);
cout<<sum<<endl;
}
return 0;
}