归并法排序求逆序数

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并操作

归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

算法描述

归并操作的过程如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

 

归并排序

归并排序具体工作原理如下（假设序列共有n个元素）：

1. 将序列每相邻两个数字进行归并操作，形成个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕

 

算法复杂度

比较操作的次数介于和。 赋值操作的次数是。 归并算法的空间复杂度为：Θ (n)

 

下面贴代码：

 

 

 

#include<stdio.h>
int a1[1000],a2[1000];
int n;
int g(int a,int b,int c)
{
	int i=a,j=b+1,k=a,sum=0;
	while(i<=b&&j<=c)
	{
		if(a1[i]<=a1[j])a2[k++]=a1[i++];
		else{a2[k++]=a1[j++];sum+=j-k;}
	}
	while(i<=b)a2[k++]=a1[i++];
	while(j<=c)a2[k++]=a1[j++];
	for(i=a;i<=c;i++)
		a1[i]=a2[i];
	return(sum);
}
int f(int a=0,int b=n-1)
{
	if(a>=b)return(0);
	int sum=0,mid=(a+b)>>1;
	sum+=f(a,mid);
	sum+=f(mid+1,b);
	sum+=g(a,mid,b);
	return(sum);
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		int i;
		for(i=0;i<n;i++)
			scanf("%d",&a1[i]);
		printf("%d\n",f());
		for(i=0;i<n;i++)
			printf("%d  ",a1[i]);
		putchar(10);
	}
	return(0);
}