好吧，又是另一个分治。是一种稳定的算法，时间复杂度是O(nlogn)。
*稳定：若一个数组中两个数的值原来相同，经过某种排序算法排序后这两个数的顺序不发生变化，则称这种排序算法是稳定的
基本步骤
- 确定分界点mid
- 递归排序左半段，又半段
- 归并——合二为一（双指针算法），时间复杂度O(n)
代码
#include<bits/stdc++.h>
using namespace std;
void merge_sort(vector<int> &q, int l, int r, vector<int> &tmp)
{
if (l >= r) return ;
int mid = l + (r - l >> 1);
merge_sort(q, l, mid, tmp), merge_sort(q, mid + 1, r, tmp);
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 ++];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n; cin >> n;
vector<int> q(n);
for (int i = 0; i < n; i ++ ) cin >> q[i];
vector<int> tmp(n);
merge_sort(q, 0, n - 1, tmp);
for (int i = 0; i < n; i ++) cout << q[i] << ' ';
cout << '\n';
return 0;
}应用：求逆序对数
ll merge_sort(int q[], int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
ll cnt = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
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++];
cnt += (mid - i + 1);
}
}
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
for (int i = l, j = 0; i <= r; i++, j++)
q[i] = tmp[j];
return cnt;
}代码如上，核心添加了计数模块。我们在执行每一段的核心代码时，其左右两半总是排序好的。因此，一旦出现左半段的数（下标为i）大于右半段的数（下标为j），则说明从第i个数到第mid个数都大于第j个数，故逆序对的数量为(mid – i + 1)。
后续只需要累加即可
2月3日补充
逆序对数一定要严格大于，今天复习的时候踩坑了。
评论（0）
暂无评论