归并排序（包含逆序数对的个数51Nod1019）

归并排序是效率很好的排序方式，和快排效率一样高，但在稳定性上优于快排，下面我们来介绍归并排序。

归并排序运用递归将序列不断二分（其原理就是分治），就像一棵树不断向下分支，最后分到只剩一个元素，这样这个元素就可当做有序的，因为只有一个元素嘛。然后是合并，怎么分出来就怎么合并回去，不过既然是排序，那么合并的时候就需要比较一下大小了。

下面为了更好的理解，我们来看一张图片。（这张图是借用的，很感谢制图人）

这就是一个简单序列的归并排序过程。

下面让我们来看代码。

#include<cstdio>

const int Max=50001;

int temp[Max],num=0;

void mergearray(int a[],int first,int mid,int last){//将数组按顺序合并

	int i=first,j=mid+1,m=mid,n=last,k=0;

	while(i<=m&&j<=n){//这里的等号很重要，没有的话前半段的数据不能全部遍历

		if(a[i]<=a[j]) temp[k++]=a[i++];

		else{

			temp[k++]=a[j++];

			num+=mid-i+1; //统计逆序数对

		}

	}

	while(i<=m) temp[k++]=a[i++];    //这里等号很重要，不然会漏数据

	while(j<=n) temp[k++]=a[j++];//这里等号很重要，不然会漏数据

	for(int q=0;q<=last-first;q++)

		a[first+q]=temp[q];

}

void mergesort(int a[],int first,int last){//将数组二分处理

	if(first<last){

		int mid=(first+last)/2;

		mergesort(a,first,mid);  //左边有序

		mergesort(a,mid+1,last);//右边有序

		mergearray(a,first,mid,last);

	}

}

int main()

{

	int a[Max],n;

	scanf("%d",&n);

	for(int i=0;i<n;i++){

		scanf("%d",&a[i]);

	}

	mergesort(a,0,n-1);

	for(int i=0;i<n;i++)

		printf("%d\n",a[i]);//统计逆序数的话输出num即可。

}

这里可能有的人不太明白逆序数为什么num+=mid-i+1这样算，这里做一下说明，在数组合并时计算前面的数是否比后面的大，这里要注意合并时前后两部分已经是有序，如果此时啊a[i]>a[j],说明a[first]到a[i-1]全部小于a[j]，而a[mid+1]到a[j-1]全部小于a[j],那么意思就是大于a[j]的数全部在a[i]到a[mid]之间，a[i]到a[mid]共有mid-i+1个数，所以逆序数对num此时要加上mid-i+1。

本人实力有限，如有错误，欢迎指出，谢谢。

巴特西

归并排序（包含逆序数对的个数51Nod1019）

最新文章

热门文章