归并排序

一、算法思想

归并排序的核心思想是 分治，具体流程如下。

1. 确定分界点 $X$：中间位置；
2. 递归排序左右区间；
3. 归并两个有序数组（重点）：合二为一。

二、算法模板

C++

const int N = 1e6 + 10;
int tmp[N];

void mergeSort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    mergeSort(q, l, mid);
    mergeSort(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++];
    }
    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];
    }
}

Go

func mergeSort(q []int, l int, r int) {
    if l >= r {
        return
    }
    mid := l + (r-l)/2
    mergeSort(q, l, mid)
    mergeSort(q, mid+1, r)

    tmp := make([]int, r-l+1)
    k, i, j := 0, l, mid+1
    for i <= mid && j <= r {
        if q[i] < q[j] {
            tmp[k] = q[i]
            k++
            i++
        } else {
            tmp[k] = q[j]
            k++
            j++
        }
    }
    for i <= mid {
        tmp[k] = q[i]
        k++
        i++
    }
    for j <= r {
        tmp[k] = q[j]
        k++
        j++
    }
    for i, idx := 0, l; idx <= r; i, idx = i+1, idx+1 {
        q[idx] = tmp[i]
    }
}

三、代码实战

AcWing 0787

---

题目：归并排序

给定你一个长度为 $n$ 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 $n$。

第二行包含 $n$ 个整数（所有整数均在 $1∼{10}^9$ 范围内），表示整个数列。

输出格式

输出共一行，包含 $n$ 个整数，表示排好序的数列。

数据范围

$1\le{n}\le{100000}$

输入样例：

5

3 1 2 4 5

输出样例：

1 2 3 4 5

解答代码：

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N], tmp[N];

void mergeSort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    mergeSort(q, l, mid);
    mergeSort(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++];
    }
    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()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }
    
    mergeSort(q, 0, n - 1);
    
    for (int i = 0; i < n; i++) {
        printf("%d ", q[i]);
    }
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

func mergeSort(q []int, l int, r int) {
    if l >= r {
        return
    }
    mid := l + (r-l)/2
    mergeSort(q, l, mid)
    mergeSort(q, mid+1, r)

    tmp := make([]int, r-l+1)
    k, i, j := 0, l, mid+1
    for i <= mid && j <= r {
        if q[i] < q[j] {
            tmp[k] = q[i]
            k++
            i++
        } else {
            tmp[k] = q[j]
            k++
            j++
        }
    }
    for i <= mid {
        tmp[k] = q[i]
        k++
        i++
    }
    for j <= r {
        tmp[k] = q[j]
        k++
        j++
    }
    for i, idx := 0, l; idx <= r; i, idx = i+1, idx+1 {
        q[idx] = tmp[i]
    }
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var n int
    Fscan(in, &n)

    q := make([]int, n)
    for i := 0; i < n; i++ {
        Fscan(in, &q[i])
    }

    mergeSort(q, 0, n-1)

    for i := 0; i < n; i++ {
        Fprintf(out, "%d ", q[i])
    }
}

func main() {
    run(os.Stdin, os.Stdout)
}

AcWing 0788

---

题目：逆序对的数量

给定一个长度为 $n$ 的整数数列，请你计算数列中的逆序对的数量。

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

输入格式

第一行包含整数 $n$，表示数列的长度。

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

输出格式

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

数据范围

$1\le{n}\le{100000}$

$1 \le \text{数列中元素的值} \le 10^9$

输入样例：

6

2 3 4 5 6 1

输出样例：

5

解答代码：

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n;
int q[N], tmp[N];

LL mergeSort(int q[], int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1;
    LL ans = mergeSort(q, l, mid) + mergeSort(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++];
            ans += mid - i + 1;
        }
    }
    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 ans;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }
    
    LL ans = mergeSort(q, 0, n - 1);
    
    printf("%ld ", ans);
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

func mergeSort(q []int, l int, r int) (ans int) {
    if l >= r {
        return
    }
    mid := l + (r-l)/2
    ans += mergeSort(q, l, mid)
    ans += mergeSort(q, mid+1, r)

    tmp := make([]int, r-l+1)
    k, i, j := 0, l, mid+1
    for i <= mid && j <= r {
        if q[i] <= q[j] {
            tmp[k] = q[i]
            k++
            i++
        } else {
            ans += mid - i + 1
            tmp[k] = q[j]
            k++
            j++
        }
    }
    for i <= mid {
        tmp[k] = q[i]
        k++
        i++
    }
    for j <= r {
        tmp[k] = q[j]
        k++
        j++
    }
    for i, idx := 0, l; idx <= r; i, idx = i+1, idx+1 {
        q[idx] = tmp[i]
    }
    return
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var n int
    Fscan(in, &n)

    q := make([]int, n)
    for i := 0; i < n; i++ {
        Fscan(in, &q[i])
    }

    Fprintf(out, "%d", mergeSort(q, 0, n-1))
}

func main() {
    run(os.Stdin, os.Stdout)
}