归并排序 & 逆序对

归并排序

动画演示：

我们发现，首先将 「 8个元素 」 分成 「 4个元素 」，再将 「 4个元素 」分成 「 2个元素 」，然后 「比较」这「 2个元素 」的值，使其在自己的原地数组内有序，然后两个 「 2个元素 」 的数组归并变成 「 4个元素 」 的 「升序」数组，再将两个「 4个元素 」 的数组归并变成 「 8个元素 」 的 「升序」数组。

归并排序代码如下：

const int N = 100009;
int n, s[N], t[N];
void msort(int l, int r)
{
    if (l >= r)
        return ;
    int mid = l + r >> 1;
    msort(l, mid), msort(mid + 1, r);
    int h1 = l, h2 = mid + 1, idx = l;
    while (h1 <= mid && h2 <= r)
        t[idx++] = (s[h1] <= s[h2] ? s[h1++] : s[h2++]);
    while (h1 <= mid)
        t[idx++] = s[h1++];
    while (h2 <= r)
        t[idx++] = s[h2++];
    for (int i = l; i <= mid; i++)
        s[i] = t[i];
    for (int i = mid + 1; i <= r; i++)
        s[i] = t[i];
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> s[i];
    msort(1, n);
    for (int i = 1; i <= n; i++)
        cout << s[i] << " \n"[i == n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

归并排序求逆序对

我们在归并排序的过程中就可以计算逆序对的个数
左边头元素 $>$ 右边头元素
$逆序对个数+=mid-左边头位置+1$

归并排序求逆序对代码：

const int N = 1000009;
int n, s[N], t[N];
long long ans = 0;
void msort(int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 1;
    msort(l, mid), msort(mid + 1, r);
    int h1 = l, h2 = mid + 1, idx = l;
    while (h1 <= mid && h2 <= r)
    {
        if (s[h1] <= s[h2])
            t[idx++] = s[h1++];
        else    
            t[idx++] = s[h2++], ans += mid - h1 + 1;
    }
    while (h1 <= mid)
        t[idx++] = s[h1++];
    while (h2 <= r)
        t[idx++] = s[h2++];
    for (int i = l; i <= mid; i++)
        s[i] = t[i];
    for (int i = mid + 1; i <= r; i++)
        s[i] = t[i];
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    msort(1, n);

    cout << ans << '\n';
}
int main()
{
    buff;
    solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40