归并排序POJ2299

归并排序POJ2299

传送门：=2299
归并排序的思想：先把每个数看成一段，然后两两合并成一个较大的有序数组，再把较大的两两合并，直到最后成为一个有序数组。

例如：

初始数组为：4 2 1 3

先把每个数看成一段，即：4 ｜ 2 ｜ 1 ｜ 3

接着两两合并成有序数组，即：2 4 ｜ 1 3

最后合并成总的有序数组，即：1 2 3 4

不难发现，在排序过程中，若某个数向前移动了N位，则必定存在N个逆序数。比如上面第二轮排序中，数字1一开始是在第2位，后面移到了第0位，前进了两位，因此必定存在两个逆序，即（2, 1）， （4, 1）。所以只需要在归并排序过程中把这个数记录下来即可得到结果。

归并步骤：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=5e5+10;
ll arr[maxn];
ll temp[maxn];
int n;
ll ans;
//合并两个有序的数组，用指针比较，分别用i表示左边数组的开始，j表示右边数组的开始；
//重新开一个temp数组，记录
void merge(int st,int mid,int en){int i,j,k;i=st,j=mid+1,k=st;while(i<=mid&&j<=en){if(arr[i]<=arr[j])temp[k++]=arr[i++];else{ans+=j-k;//计算逆序数temp[k++]=arr[j++];}}while(i<=mid){temp[k++]=arr[i++];}while(j<=en){temp[k++]=arr[j++];}for(int i=st;i<=en;i++)arr[i]=temp[i];
}
//将无序的数组排成有序数组，不停分割
void mergesort(int st,int en){if(st<en){int mid=(st+en)/2;mergesort(st,mid);mergesort(mid+1,en);merge(st,mid,en);}
}
int main(){while(~scanf("%d",&n)&&n){ans=0;for(int i=1;i<=n;i++)scanf("%lld",&arr[i]);mergesort(1,n);printf("%lld\n",ans);}
}