4.25归并排序

思路：

1.首先分割成一个个独立的部分
2.然后组合，借助临时数组
3.把其中那个没有遍历完全的数组元素填到临时数组中
4.物归原主

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], temp[N]; // temp作为临时数组
void merge_sort(int a[], int l, int r) {
    if (l >= r) return; // 这里不管在应用的时候还是单纯归并排序，这里可以都可以写成==替代
    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    int k = 0, i = l, j = mid + 1; // 实际两个有序序列的合并过程
    while (i <= mid && j <= r) { 
        if(a[i] < a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] =a[j++];
    for (int i = l, j = 0; i <= r; i++, j++) a[i] = temp[j]; // 物归原主过程
}
int main() {
    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]);
}

逆序对（归并的应用）

牛客网对应编程题的链接，思路搞得y总的视频，明白原理最重要

1 2 3 5 4 逆序个数是1
基本思想，整个区间分成俩区间以后，总的逆序的个数 = 左边区间逆序个数和右边区间逆序个数的和 + 两个区间之间的一个逆序。和走楼梯思路一直，基本思想就是基于分治的思想。两个区间的如何计算？

answer:在合并两个区间的时候计算， 第二个区间的第一个元素当 a[i] > a[j],此时从i到mid整个区间部分都是大于j指针所指的元素，因此res 需要在加上前面的 merge_sort(l, mid) 和 merge_sort(mid + 1, r)的基础上，加上第一区间比第二区间每个元素大的总个数。就是上面一段红色部分个数。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], temp[N];
typedef long long LL;
LL merge_sort(int l, int r) {
    if (l >= r) return 0;
    int mid  = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r); // 第一个区间内部和第二个区间内部的逆序个数。
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j<= r) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else {
            temp[k++] = a[j++];
            res += mid - i + 1; // 两个区间之间的逆序个数。
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (int i = l, j = 0; i <= r; i++, j++) a[i] = temp[j];
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++ ){
        scanf("%d", &a[i]);
    }
    cout << merge_sort(0, n - 1) << endl;
    return 0;
}