稳定，思想：分治
时间复杂度：nlogn
以数组的中间部分来分，分为左边和右边。
-
确定分界点。mid = (1+r)/2;
-
递归排序left和right。
-
合二为一（重点）。合成一个有序的数组。
合并的方法：双指针法。
由于归并排序是稳定的，因此在两数相同的时候可以把第一个数字移动到尾部。
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数
第二行包含
输出格式
输出共一行，包含
数据范围
1≤ n ≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
// 取中间的位置
// 分别归并排序左右两侧，进行排序
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
// =========归并的过程===========
// k表示已经归并的数，i为指向左半边序列的起点，j为指向右半边序列的起点。
int k = 0, 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 ++ ];
// 存回q数组中
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000，
数列中的元素的取值范围
输入样例：
6
2 3 4 5 6 1
输出样例：
5
code：
思路还是标准的归并，但是需要注意的是res的范围。首先不妨考虑最复杂的情况，即这组数是从大到小排序好的，也就是一共可以组成$(n - 1) + (n - 2) + ... + 1 = \frac{n (n - 1)}{2}$，这里n最大是100000，因此逆序对最大为$5*10^9$，超过了int范围，可以选择开long long存储。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
// 收集每次排序中的逆序对
LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
// i指向的是左半段，j指向的是右半段
// 正常情况是左半段小于右半段
if (q[i] <= q[j]) tmp[k ++] = q[i ++];
// 否则说明是逆序，j和（i到mid）之间的所有数都组成逆序对，因为i之后的部分都大于i，同样也就大于j。
else
{
res += mid - i + 1;
tmp[k ++ ] = q[j ++ ];
}
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
return res;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
cout << merge_sort(a, 0, n - 1) << endl;
return 0;
}在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
code
class Solution {
public:
int reversePairs(vector<int>& nums) {
vector<int> tmp(nums.size());
return merge_sort(nums, tmp, 0, nums.size() - 1);
}
long long merge_sort(vector<int>& nums, vector<int>& tmp, int l, int r)
{
if( l >= r) return 0;
int mid = l + r >> 1;
long long res = merge_sort(nums, tmp, l, mid) + merge_sort(nums, tmp, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while( i <= mid && j <= r){
if(nums[i] <= nums[j]) tmp[k ++ ] = nums[i ++ ];
else{
res += mid - i + 1;
tmp[k ++ ] = nums[j ++ ];
}
}
while(i <= mid) tmp[k ++ ] = nums[i ++ ];
while(j <= r) tmp[k ++ ] = nums[j ++ ];
for(i = l, j = 0; i <= r; i ++, j ++ ) nums[i] = tmp[j];
return res;
}
};