归并排序与逆序对

归并排序

归并排序是一种基于分治和递归思想的典型算法，正如其字面所述可以分为归类-合并两个步骤，归类指将两个子数组各自变为有序数组，合并指将两个有序数组拼成一个大的有序数组的过程

基本思想

考虑无序数组A[0...n]，要对A进行排序。
首先将A[n]划分为两个子数组A[0...n/2]和A[n/2 + 1 ... n]
然后对两个子数组分别进行归并排序
最后将两个子数组合并再重新写入A[0...n]

具体的归并过程见下方的代码实现部分注释

代码实现

const int N = xxxxx; // xxxxx为自定义大小
int a[N], b[N]; // 数组a中存放的是待排序元素，数组b是辅助数组，此方法下空间复杂度为O(n)

void merge(int l, int r, int mid){
	int i = l, j = mid + 1, k = l; // i用于遍历第一个子数组，j用于遍历第二个自数组，k用于记录当前排序轮次下一个元素的下标
    while (i <= mid && j <= r){
    	if (a[i] <= a[j]) b[k++] = a[i++]; //哪个元素小就把哪个元素排在前面
        else b[k++] = a[j++];
    }
    while (i <= mid) b[k++] = a[i++]; //如果存在未排完的元素就一次性全部排到有序数组之后，这句和下一句只有一句是会真正执行的
    while (j <= r) b[k++] = a[j++];
    for (int i = l; i <= r; i++){
    	a[i] = b[i];
    }
}

void mergeSort(int l, int r){
	if (l >= r) return; //当待排序区间只包含一个或更少的元素时停止递归进程
    int mid = (l + r) / 2;
    mergeSort(l, mid); // 左侧排序
    mergeSort(mid + 1, r); // 右侧排序，注意下标为mid的元素不要排两次
    merge(l, r, mid); // 合并左右两个有序数组
}

逆序对

逆序对在线性代数中多有提到，如求对角阵行列式的时候会用到，现简要讲解什么是逆序对
现存在一个序列

1 2 3 4 5

显然这是一个升序序列，所有的元素都比其后方的元素小，此时序列的逆序数为0
把 4 和 5 换一下位置

1 2 3 5 4

此时 5 的后面出现了比5小的元素，只有4一个，则(5, 4)成为一个逆序对，此时序列的逆序数为1

1 2 5 3 4

同理此时存在(5, 3),(5, 4)两个逆序对，此时逆序数为2\

逆序对的求法

方法一：暴力双指针

这是一种非常暴力的方法，时间复杂度在O(n^2)，若数据量小可以采用这个方法求

int nixu_count(int n, int a[]){ // n是元素个数
	int cnt = 0;
	for(int i = 0; i < n; i++){
    	for (int j = i + 1; j < n; j++){
        	if (a[i] > a[j]) cnt++;
        }
    }
    return cnt;
}

方法二：归并过程中求逆序

以二路归并为例，归并过程中总是从两个有序数组的头部取更小的那个元素，当前元素若来自第二个数组，则至少会产生mid - i + 1个逆序对，即逆序数至少增加mid - i + 1，这种方法的时间复杂度为O(nlogn)

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 10110;
int a[N], b[N];
int n, ans = 0;
 
void merge(int l, int r){
    if (l >= r) return;
    int mid = (l + r) / 2;
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r){
        if (a[i] <= a[j]) b[k++] = a[i++];
        else{
            b[k++] = a[j++];
            ans += mid - i + 1;
        }
    }
    while (i <= mid)b[k++] = a[i++];
    while (j <= r) b[k++] = a[j++];
    for (int i = l; i <= r; i++){
        a[i] = b[i];
    }
     
}
 
void mergeSort(int l, int r){
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    merge(l, r);
}
 
signed main(){
    ios :: sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
     
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    mergeSort(0, n - 1);
     
    cout << ans;
    return 0;
}