归并排序以及逆序对

归并排序以及逆序对 定义

什么是归并排序呢，相信很多学过算法的人都知道，这个名词的含义了，对于我来说的话，其实就是解释文言文，“归”就是递归，“并”就是合并。排序就不用说了。也就是这个名字也可以叫做递归合并排序。但是之所以能够做到最后的顺序是一定的，是因为在递归的过程就已经在不断的排序了，所以其实最终合并的是一个已经部分有序的数列了。

①“归”

 我们看一下这一个递归的过程，似乎好像就是把一串数字，最后分开，成为一个独立的数字，但是正如我们所学过的递归，其实就是这样的一个过程，一直深入直到一个不可以再往下的过程了，所以，我们合并的时候呢？

归的求解

void gbsort(int l,int r)
{
	if(l==r) return;
	int m=l+((r-l)>>1);
	gbsort(l,m);
	gbsort(m+1,r);
	merge(l,m,r);
}

从上面的代码，我们可以看到，其实就是把一串需要处理的数列从中间割裂开，然后分别处理左边和右边，这里的gbsort我们给他的定义是实现归并排序的函数，这里的定义决定了这个函数的功能，到下面我们，要求出逆序对的数量的时候，读者会发现，定义上的不同，就会导致一个函数做事上的不同，但是其实写法是差不多的，至于此处的merge，我们留到下一个块进行讲解。 

②“并”

当我们已经递归到了最后的一层，我们要一层一层的回溯，然后将数列合并在一起，然而我们知道如果仅仅是按照分开的方式进行合并，那不就相当于原数组的数丝毫没有改变嘛？也就是开始我们提到的思想，在合并的过程中，我们便要进行排序了。其实看到上面的图，我们可以知道分开的过程，应当运用到了一个二分的思想，这也是为什么归并排序最终的时间复杂度小于o（）的关键了。而这个“并”中所蕴含的思想应当是很深的，本蒟蒻在写这篇博客的时候，其实还是不能把这样的代码得心应手的写下来，这也就说明，很多的模板真的是需要熟能生巧的。

双指针＋辅助数组

完成排序的关键其实就是用双指针，从开头和中间两个位置分别进行移动，然后在两个指针下标的数组内的值不断的进行比较，然后将数字放到我们的辅助数组下，这样就能完成，辅助数组里面的数字一定是有序的，毕竟最后两个指针是可以遍历完整个数组的。

int a[1000],vi[1000];  //a数组记录待排序和计算逆序对的数组，vi表示辅助数组 
int n;  //n代表需要输入的数组长度
 
void merge(int start,int mid,int end)
{
	int p1=start; //p1指针
	int p2=mid+1; //p2指针
	int d=1; //利于辅助数组从1开始进行存数
	while(p1<=mid&&p2<=end)
	{
	if(a[p1]

这是完成merge的一个 *** 作函数，下面会利用图进行讲解

利用4658进行举例子

两个指针分别从开头的start开始和（mid+1）的位置进行遍历，然后对比p1，p2的位置，我们显然可以找到大小关系，图里面忘记写等号了，读者注意结合代码看图。因此，在p1和p2遍历的过程，将4，5，6，8依次的放入数组之中，请注意，在此过程之前，左右两边一定是有序的，为什么呢，因为这已经是“并”的中间步骤了，也就是在前面的时候，已经让两边变成了从小到大的顺序，这不就是递归完成的过程吗？子问题的依次解决最后让整个问题得到了解决。因此完整的代码如下。

归并排序完整代码

#include
using namespace std;

int a[1000],vi[1000];  //a数组记录待排序和计算逆序对的数组，vi表示辅助数组 
int n;  //n代表需要输入的数组长度
 
void merge(int start,int mid,int end)
{
	int p1=start; //p1指针
	int p2=mid+1; //p2指针
	int d=1; //利于辅助数组从1开始进行存数
	while(p1<=mid&&p2<=end)
	{
	if(a[p1]>1);
	gbsort(l,m);
	gbsort(m+1,r);
	merge(l,m,r);
}

int main()
{
 	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	gbsort(1,n);
	for(int i=1;i<=n;i++)
	cout<

逆序对数量求解

 

①背景

为什么会想到逆序对呢？因为在归并排序的时候，不断的让指针进行移动，然而这个移动的过程，我们发现，每次的移动都进行了相关的比较，所以依据这个特点，是否可以拿来做一些文章呢？我想这个是肯定蕴藏了一些奥妙的。

②相关题目

这是来自洛谷上一个通过率挺低的题目，当初通过学习，居然AC了，但是现在让我独立地再写一遍，还是很有难度，这就是不够熟练的后果把。相信大家看到这个图之后会对逆序对有更加深刻的理解了，大家不妨想想，如果给你一串数字，你会怎么去计算它的逆序对的数量呢？在我们日常生活中，当然就是一个数一个数来嘛，依次与后面的数字进行对比，然后发现一对让答案加一个，这样的方法显然没有问题，可以毕竟是算法，还是那句话，TLE永远会限制得分的脚步啊，因此我们要想一个时间复杂度的方法。

③图解

 我们看到这幅图，当然与之前讲解的归并排序不同的是，最后排序的顺序是从大到小的，因此，待会也可以像大家展示一下两者的细微差别。我们可以看到当p1指向3的时候，我们会先让p2往后移，但是在此之前，我们便需要计算逆序对数量了，我写的答案是2，很多人肯定看到这里是会有所懵逼的，为什么不是3呢，明显2，1，1都是答案啊，这就是递归的奥妙了，回顾之前的递归函数，3，3，2已经是一个有序的数组了，那是否已经说明，其实再之前我们其实已经算了一遍2为答案的逆序对数量，所以在此我们已经不需要多计算一遍了，这也就是为什么最终我们算出来的答案不会重复，也不会遗漏的根本。这个2是怎么来的呢？其实就是利用p2和end进行计算，我们看到end为6，此时的p2为5，刚好p2到end区间有多少数便是我们需要求的值，也就是end-p2+1。

题目最终代码

#include
using namespace std;

int a[500005],vi[500005];  //a数组记录待排序和计算逆序对的数组，vi表示辅助数组 
int n;  //n代表需要输入的数组长度
 
long long merge(int start,int mid,int end)  //定义为逆序对的数量和 
{
	int p1=start; //p1指针
	int p2=mid+1; //p2指针
	int d=1; //利于辅助数组从1开始进行存数
	long long ans=0; //计算某个区间的逆序对数量 
	while(p1<=mid&&p2<=end)
	{
	if(a[p2]>=a[p1]) 
	vi[d++]=a[p2++];
	else 
	{
	ans+=end-p2+1;	
	vi[d++]=a[p1++];
    }
    }
	while(p1<=mid) vi[d++]=a[p1++];
	while(p2<=end) vi[d++]=a[p2++];
	for(int i=start,d=1;i<=end;i++,d++)
	a[i]=vi[d];
	return ans; 
}

long long gbsort(int l,int r)
{
	if(l==r) return 0;
	int m=l+((r-l)>>1);
	return gbsort(l,m)+gbsort(m+1,r)+merge(l,m,r);  //左边的数量加右边的最后加所有的 
}

int main()
{
 	long long sum=0;
    cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	sum=gbsort(1,n);
	cout< 
相关讲解 
其实相关的地方，有注释在旁边，这里其实就是想提到，我们看到我们定义的函数全部最后返回了一个数值，这也就是为什么开头的时候说到函数定义的不同完成的事情也不同，内部需要注意的就是我们必须要计算左边部分的逆序对数量＋右边的+全部排的，正如所说的，如果我们没有计算全三部分，虽然不影响排序，但是会影响到最终的答案。
 
AC的成就感 
 
 反正相信大家看到自己每次能够AC掉一个题目，一定会有所成就感，然后发现绿色是多么美好的颜色，反正就是说这样的模板题目，还是常做常新啊，一定得多动手进行练习把。 
 
相关链接 
最后还是得放上，做出此题其实看了很多很多的资料吧，然后肯定会有很多人对归并排序的原理啊顺序啥的还是很纠结，大家可以看看下面的一些视频，相信会有更好的理解吧！为了增加神秘感，我就不说，点进去是什么了哈哈哈哈哈。
 
①链接一
 
②链接二
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5680787.html