关于归并排序及快速求序列逆序对数的学习

1.关于排序

这算是最简单的算法了吧，简单朴素的算法如冒泡排序和选择排序复杂度均为O(N^2)，显然无法满足这个物欲横流 飞速发展的时代的要求，于是我们需要O(nlogn)的排序

那么我们想：如果有两个有序序列，把他们合并成一个有序序列的复杂度是多少？

void merge(int l,int mid,int r,int arr[])
{
	int i=l,j=mid+1;
	int k=0;
	while(i<=mid&&j<=r)
	{
		if(arr[i]<arr[j]) t[++k]=arr[i++];
		else t[++k]=arr[j++];
	}
	while(i<=mid) t[++k]=arr[i++];
	while(j<=r) t[++k]=arr[j++];
	for(int p=1;p<=k;p++) arr[p+l-1]=t[p];
}

显然是O(N)的，如果原序列左右分别是有序的，那么我们可以在线性复杂度内合并他们。

于是就形成了分治关系，不断把左右两边有序化，然后与合并，因为是分成两半，所以最多分O(logN)次，每次进行O(N)的合并，总复杂度O(NlogN)

核心代码：

void merge(int l,int mid,int r,int arr[])
{
	int i=l,j=mid+1;
	int k=0;
	while(i<=mid&&j<=r)
	{
		if(arr[i]<arr[j]) t[++k]=arr[i++];
		else t[++k]=arr[j++];
	}
	while(i<=mid) t[++k]=arr[i++];
	while(j<=r) t[++k]=arr[j++];
	for(int p=1;p<=k;p++) arr[p+l-1]=t[p];
}
void mergesort(int l,int r,int arr[])
{
	if(l<r)
	{
		int mid=(l+r)>>1;
		mergesort(l,mid,arr);
		mergesort(mid+1,r,arr);
		merge(l,mid,r,arr);
	}
}

速度上说，归并排序是稳定的排序算法，在本地手测还是挺快的，与快排对比n=1000000（单位是什么？？？我不知道）：

2.关于求逆序对数的O(NlogN)算法

朴素的算法：直接暴力扫---O(N^2)

高端的：假如知道了左右两个有序序列，如果左边的一个数比右边的大(Left[i]>Right[j])那么左边这个后面的所有都比右边的大，对答案贡献为左边总个数-i+1

类比归并排序，知道两半有序序列后，分别从头扫，答案累加就可以了。

例题:POJ2299

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define cls(x) memset(x,0,sizeof x)
typedef long long ll;
const int maxn = 500010;
using namespace std;
int n;
int a[maxn];
int t[maxn];
ll merge(int l,int mid,int r,int arr[])
{
	ll ans=0;
	int i=l,j=mid+1;
	int k=0;
	while(i<=mid&&j<=r)
	{
		if(arr[i]>arr[j])
		{
			ans=ans+(mid-i+1);
			t[++k]=arr[j++];
		}
		else t[++k]=arr[i++];
	}
	while(i<=mid) t[++k]=arr[i++];
	while(j<=r) t[++k]=arr[j++];
	for(int p=0;p<k;p++) arr[l+p]=t[p+1];
	return ans;
}
ll solve(int l,int r,int arr[])
{
	ll x=0;
	if(l<r)
	{
		int mid=(l+r)>>1;
		x+=solve(l,mid,arr);
		x+=solve(mid+1,r,arr);
		x+=merge(l,mid,r,arr);
	}
	return x;
}
int main()
{
	while(1)
	{
		cls(a);cls(t);
		scanf("%d",&n);
		if(n==0) break;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		printf("%lld\n",solve(1,n,a));
	}

	return 0;
}