归并排序

归并排序是一种分治算法，怎么分，怎么治？

• 分：通过递归不断把数组分成两半，直到每个子数组只剩 1 个元素（天然有序）
• 治：把两个已经排好序的子数组合并成一个有序数组。

把问题分解为简单子问题，就体现在每个数组只剩一个元素时，那就天然有序了。

模板题

P1177 【模板】排序

归并排序代码实现

#include<iostream>using namespace std;const int N = 1e5 + 10;int n, a[N], tmp[N]; //a存数据，tmp辅助归并排序时合并两个数组 void merge_sort(int left, int right)
{if(left >= right) return; //left == right只有一个元素，有序，返回 //1.数组一分为二 int mid = (left + right) / 2;//2.将左右数组都排好序 merge_sort(left, mid);merge_sort(mid + 1, right);//3.合并左右有序数组到tmp中 int cur1 = left, cur2 = mid + 1, i = left; //i帮助写入临时数组 while(cur1 <= mid && cur2 <= right){if(a[cur1] <= a[cur2]) tmp[i++] = a[cur1++];else tmp[i++] = a[cur2++];}while(cur1 <= mid) tmp[i++] = a[cur1++];while(cur2 <= right) tmp[i++] = a[cur2++];//4.将tmp中的[left,right]区间转移到a的[left,right]区间 for(int j=left;j<=right;j++) a[j] = tmp[j]; //最容易错的一步，要知道在merge_sort函数中，我们是对[left, right]区间进行排序而不是[0, n] 
}int main()
{cin >> n;for(int i=1;i<=n;i++) cin >> a[i];merge_sort(1,n);for(int i=1;i<=n;i++) cout << a[i] << " ";return 0;
}

时间复杂度

不断地将数组一分为二，直到只剩下一个元素为止，时间复杂度为 logn；
将 tmp 数组复制到 a 数组，时间复杂度为 n。
总的时间复杂度为$O(nlogn)$。

逆序对

什么是逆序对？

逆序对（Inversion）是指在一个序列中，如果前面的数比后面的数大，那么这两个数就构成一个逆序对。

逆序对和排序的关系

• 逆序对的数量衡量了序列的无序程度：逆序对越多，序列越乱；逆序对越少，序列越接近有序。
• 排序的本质就是消除逆序对

例题

P1908 逆序对

分析

首先我们可以想到两层for循环暴力统计逆序对个数，但是会超时。

我们可以尝试一下分治的思想，在原数组中找逆序对，相当于先将数组一分为二，在左半边数组找逆序对，在右半边数组找逆序对，再一左一右找逆序对，所有的逆序对数量加起来就是原数组的逆序对数量。

于是我们得到了这样两个数组，分别对左右求逆序对，这咋求？？？这还不是要两层for循环挨个遍历统计逆序对吗，这算上二分数组的时间复杂度，现在总时间复杂度干到了$O(n^{2}logn)$，这能对吗？

但是当左边这个数组和右边这个数组分别有序的时候，再统计逆序对个数就非常方便了。我们选择一个元素在左边数组，另一个元素在右边数组的逆序对，统计逻辑如下：

我们可以发现，这与归并排序中合并有序数组的流程是一致的。

但是这里就有一个问题：对左边数组和右边数组分别排序的话，是否会影响逆序对的统计呢？
不会，因为在统计一左一右的时候，左右数组的逆序对已经统计过了，才形成的左右这样有序的数组，统计逆序对的统计和归并排序是同时进行的。
我们仍可以从极限情况分析，当数组的长度为2时，分成左右数组，它们的长度分别为1，于是左右数组中的逆序对个数肯定为0，我们接下来统计一左一右的逆序对个数，统计完之后，这个长度为2的数组也就通过归并排序变得有序了。另一边肯定也通过这样相同的流程得到了一个长度为2的有序数组，然后对它们进行一左一右的逆序对统计，这时候再思考为什么不分别统计左右数组中的逆序对个数呢？因为已经统计过了，它们就是在一左一右合并的过程中统计的。

代码

#include<iostream>using namespace std; typedef long long LL;const int N = 5e5 + 10;int n, a[N], tmp[N];LL merge(int left, int right)
{if(left >= right) return 0;//1.一分为二int mid = (left + right) >> 1; //2.计算左右数组LL ret = 0; ret += merge(left, mid);ret += merge(mid + 1, right);//3.合并左右数组int cur1 = left, cur2 = mid + 1, i = left;while(cur1 <= mid && cur2 <= right){if(a[cur1] <= a[cur2]) tmp[i++] = a[cur1++];else{tmp[i++] = a[cur2++];ret += mid - cur1 + 1; }	} while(cur1 <= mid) tmp[i++] = a[cur1++];while(cur2 <= right) tmp[i++] = a[cur2++];for(int j=left;j<=right;j++) a[j] = tmp[j];return ret;
}int main()
{cin >> n;for(int i=1;i<=n;i++) cin >> a[i];cout << merge(1,n) << endl;	return 0;
}