归并排序 （求逆序数）
归并排序：递归+合并+排序
时间复杂度：O（n logn） 空间复杂度：O（n）
用途：1.排序 2.求逆序对数
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence9 1 0 5 4 , Ultra-QuickSort produces the output0 1 4 5 9 . Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence. Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0 题意：
给出长度为n的无序序列，每次只能交换相邻的两个数，求至少要交换多少次才使得该序列为递增序列。 分析：
1.根据时间范围估计时间复杂度，归并排序的时间复杂度一般为O（n logn）
2.算法步骤： 1.划分问题：把序列分为元素个数尽量相等的两半
2.递归求解：把两半元素分别排序
3.合并问题：把两个有序表合成一个
3.保存时，用long long 类型，否则会wa的 代码：
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=; int a[maxn],b[maxn];
long long ans; void merge(int l,int m,int r) //归并排序
{
int i=l,j=m+,t=;
while(i<=m&&j<=r) //从小到大排序
{
if(a[i]>a[j])
{
b[t++]=a[j++];
ans+=m-i+;
}
else b[t++]=a[i++];
}
while(i<=m)
b[t++]=a[i++];
while(j<=r)
b[t++]=a[j++];
for(int i=;i<t;i++) //合并
a[l+i]=b[i];
} void merge_sort(int l,int r) //划分问题
{
if(l<r)
{
int m=(l+r)/;
merge_sort(l,m);
merge_sort(m+,r);
merge(l,m,r);
}
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==)
break;
ans=;
for(int i=;i<n;i++)
scanf("%d",&a[i]);
merge_sort(,n-);
printf("%lld\n",ans);
}
return ;
}
本来想着完全不看别人的代码都由自己做，可是看了一天了只是有了思路，还是写不出来。。。又看来了别人的代码。。。