归并排序、求逆序对归并排序(mergesort)

归并排序(mergesort)

归并排序采用分治的思想：
先将数组分成一半，然后将左边的数组和右边的数组进行排序，在递归的过程中，又将左边的数组分半然后合并。递归的出口就是当数组只剩下一个元素。
1.把数组从中间划分成两个子数组;
2.一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素
3.依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。

#include<iostream>
using namespace std;
int a[10001];
int b[10001];  //辅助数组
int ans; // 统计逆序对的数量
void mergesort(int l,int r)
{
	if(l == r) return ;
	int mid=(l+r)/2;
	mergesort(l,mid);
	mergesort(mid+1,r);
	int i=l,j=mid+1,p=l;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j]) b[p++]=a[i++];
		else{
			b[p++]=a[j++];
			//ans+=mid-i+1; 计算逆序对的固定算式
		}
	}
	while(i<=mid) {
		b[p++]=a[i++];
	}
	while(j<=r){
		b[p++]=a[j++];
	}
	for(i=l;i<=r;i++) a[i]=b[i];
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	mergesort(0,n-1);
	cout<<ans;
	return 0;
} 

复杂度分析：

• 时间复杂度：O(nlogn),对于规模为n的问题，一共要进行log(n)层的大小切分;每一层的合并复杂度都是O(n);
• 空间复杂度： O(n),需要分配一个大小为n的额外数组.

最后

以上就是英勇冬瓜为你收集整理的归并排序、求逆序对归并排序(mergesort)的全部内容，希望文章能够帮你解决归并排序、求逆序对归并排序(mergesort)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。