学归并排序和逆序对，这篇文章就够了！！！归并排序和逆序对超详细整理！

小鱼儿 2021-07-24 20:44 380阅读 0赞

### 目录 ###

*   *   *  1.归并排序
         *  2.逆序对
         *  3.例题

### 1.归并排序 ###

**(1).介绍**  
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(DivideandConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序的时间复杂度是O(nlogn). 速度快,同时归并排序是稳定的排序,即相等的元素的顺序不会改变，如输人记录1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的1(1) 2(3) 2(4) 3(2) 5(5)中的2和2是按输人的顺序。这对要排序数据包含多个信息而要按其中的某一个信息排序，要求其它信息尽量按输人的顺序排列时很重要，这也是它比快速排序优势的地方。  
**(2).实现**  
2-路归并排序的原理是，将序列两两分组，将序列归并为n/2个组，组内单独排序;然后将这些组再两两归并，生成n/4个组，组内再单独排序;以此类推，直到只剩下一个组为止。  
下面来看一一个例子，要将序列\{66, 12, 33, 57, 64, 27, 18\}进行2-路归并排序。

①第一趟。两两分组，得到四组: \{66, 12\}、 \{33,57\}、 \{64,27\}、 \{18\}, 组内单独排序，得到新序列\{12, 66\}, \{33, 57\}, \{27, 64\}, \{18\}\}.

②第二趟。将四个组继续两两分组，得到两组: \{12, 66, 33,57\}、\{27, 64, 18\}，组内单独排序，得到新序列\{ \{12, 33, 57, 66\}, \{18, 27, 64\}\}.

③第三趟。将两个组继续两两分组，得到一组: \{12, 33, 57, 66, 18, 27, 64\},组内单独排序，得到新序列\{12, 18, 27, 33, 57, 64, 66\}。算法结束。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]  
**(3).代码**

//归并排序模板
    const int maxn = 1e5 + 10;
    int a[maxn],b[maxn];
    void msort(int l, int r)
    { 
    	if (l == r) return;   //如果只有一个数字则返回，无需排序
    	int mid = (l + r) / 2;
    	msort(l, mid);       //分解左序列
    	msort(mid + 1, r);   //分解右序列
    	int i = l, j = mid + 1, k = l;
    	while (i <= mid && j <= r)
    	{ 
    		if (a[i] <=a[j])
    		{ 
    			b[k] = a[i]; k++; i++;
    		}
    		else
    		{ 
    			b[k] = a[j]; k++; j++;
    		}
    	}
    	while (i <= mid)   //复制左边子序列剩余
    	{ 
    		b[k] = a[i]; k++; i++;
    	}
    	while (j <= r)     //复制右边子序列剩余
    	{ 
    		b[k] = a[j]; k++; j++;
    	}
    	for (int i = l; i <= r; i++)
    	{ 
    		a[i] = b[i];
    	}
    }

**简化版**

const int maxn = 1e5 + 10;
    int q[maxn], tmp[maxn];
    void merge_sort(int q[], int l, int r)
    { 
    	if (l >= r)  return; //如果只有一个数字或没有数字，则无需排序
    	int mid = (l + r ) /2;
    	merge_sort(q, l, mid);       //分解左序列
    	merge_sort(q, mid + 1, r); //分解右序列
    	int k = l, i = l, j = mid + 1;
    	while (i <= mid && j <= r)   //合并
    	{ 
    		if (q[i] <= q[j]) tmp[k++] = q[i++];
    		else tmp[k++] = q[j++];
    	}
    	while (i <= mid) tmp[k++] = q[i++];   //复制左边子序列剩余
    	while (j <= r) tmp[k++] = q[j++];    //复制右边子序列剩余
    	for (int i = l; i <= r; i++) q[i] = tmp[i];
    }

### 2.逆序对 ###

**(1).介绍**  
上述提到归并排序是稳定的排序，相等的元索的顺序不会改变，进而用其可以解决逆序对的问题。首先我们了解一下什么是逆序对。

逆序对:设 A为一个有n个数字的有序集(n>1),其中所有数字各不相同。如果存在正整数i,j使得1≤i<j≤n而且A\[i\]> A\[j\].则<A\[i\],A\[j\]>这个有序对称为A的一个逆序对，也称作逆序数。

例如，数组(3,1,4,5,2)的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。

所谓逆序对的问题，即对给定的数组序列,求其逆序对的数量。

从逆序对定义上分析，逆序对就是数列中任意两个数满足大的在前,小的在后的组合。如果将这些逆序对都调整成顺序(小的在前，大的在后),那么整个数列就变得有序，即排序。因面，容易想到冒泡排序的机制正好是利用消除逆序来实现排序的，也就是说，交换相邻两个逆序数，最终实现整个序列有序，那么交换的次数即为逆序对的数量。

冒泡排序可以解决逆序对问题，但是由于冒泡排序本身效率不高，时间复杂度为O(n^2),对于n比较大的情况就没用武之地了。我们可以这样认为，冒泡排序求逆序对效率之所以低，是因为其在统计逆序对数量的时候是一对一对统计的，而对于范围为n的序列，逆序对数量最大可以是(n+1)\*n/2,因此其效率太低.那怎样可以一下子统计多个，而不是一个一个累加呢?这个时候，归并排序就可以帮我们来解决这个问题。  
在合并操作中，我们假设左右两个区间元素为：

左边：\{3 4 7 9\} 右边：\{1 5 8 10\}

那么合并操作的第一步就是比较3和1,然后将1取出来放到辅助数组中,这个时候我们发现，右边的区间如果是当前比较的较小值，那么其会与左边剩余的数字产生逆序关系，也就是说1和3、4、7、9都产生了逆序关系，我们可以一下子统计出有4对逆序对。接下来3,4取下来放到辅助数组后，5与左边剩下的7、9产生了逆序关系，我们可以统计出2对。依此类推,8与9产生1对,那么总共有4+2+1对。这样统计的效率就会大大提高，便可较好地解决逆序对问题。

而在算法的实现中，我们只需略微修改原有归并排序,当右边序列的元素为较小值时，就统计其产生的逆序对数量，即可完成逆序对的统计。.

**(2).代码**

const int maxn = 1e5 + 10;
    int q[maxn], tmp[maxn];
    void merge_sort(int q[], int l, int r)
    { 
    	if (l >= r)  return; //如果只有一个数字或没有数字，则无需排序
    	int mid = (l + r )/2;
    	merge_sort(q, l, mid);       //分解左序列
    	merge_sort(q, mid + 1, r); //分解右序列
    	int k = l, i = l, j = mid + 1;
    	while (i <= mid && j <= r)   //合并
    	{ 
    		if (q[i] <= q[j]) tmp[k++] = q[i++];
    		else 
    		{ 
    		    tmp[k++] = q[j++];
    		    ans += mid - i + 1;   //统计产生逆序对的数量
    		}
    	}
    	while (i <= mid) tmp[k++] = q[i++];   //复制左边子序列剩余
    	while (j <= r) tmp[k++] = q[j++];    //复制右边子序列剩余
    	for (int i = l; i <= r; i++) q[i] = tmp[i];
    }

其中，ans+=mid-i+1 这句代码统计新增逆序对的数量，ans作为全局变量，用于统计逆序对的数量，此时ans要增加左边剩余元素的个数。当归并排序结束后，逆序对也得到解决，ans即为逆序对的数量。

### 3.例题 ###

**(1).题目**  
给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a\[i\] > a\[j\]，则其为一个逆序对；否则不是。

**输入格式**  
第一行包含整数n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

**输出格式**  
输出一个整数，表示逆序对的个数。

**数据范围**  
1≤n≤100000  
**输入样例：**  
6  
2 3 4 5 6 1  
**输出样例：**  
5

//归并排序模板
    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn = 1e6 + 10;
    int q[maxn], tmp[maxn];
    long long ans = 0;
    void merge_sort(int q[], int l, int r)
    { 
    	if (l >= r)  return;      //如果只有一个数字或没有数字，则无需排序
    	int mid = (l + r ) /2;
    	merge_sort(q, l, mid);       //分解左序列 
    	merge_sort(q, mid + 1, r);   //分解右序列 
    	int k = l, i = l, j = mid + 1;
    	while (i <= mid && j <= r)   //合并
    	{ 
    		if (q[i] <= q[j]) tmp[k++] = q[i++];
    		else
    		{ 
    			tmp[k++] = q[j++];
    			ans += mid - i + 1;
    		}
    	}
    	while (i <= mid) tmp[k++] = q[i++];   //复制左边子序列剩余
    	while (j <= r) tmp[k++] = q[j++];    //复制右边子序列剩余
    	for (int i = l; i <= r; i++) q[i] = tmp[i];
    }
    int main()
    { 
    
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; i++)
    	{ 
    		cin >> q[i];
    	}
    	merge_sort(q, 0, n - 1);
    	cout << ans << endl;
    	return 0;
    }

参考书籍：《信息学奥赛一本通》，《算法笔记.胡凡》，将其中讲解的很好的内容搬运过来并加以整理，方便各位对归并排序和逆序对的学习。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/11cde7f8e1a64c4aba3ccb1be69ed6c8.png