参考了文章：https://blog.****.net/qq_41550842/article/details/81215935

归并排序的理解

浅谈归并排序

（图源见水印）

归并排序，可以看这个网站的动图理解：https://visualgo.net/zh/sorting?slide=10-2

归并排序是分治算法的一种体现，分治解题的一般步骤是：

划分步骤：将大的原始问题划分成较小的子问题并递归地解决较小的子问题，
解决步骤：结合较小的子问题的结果来产生较大的原始问题的结果。

而归并排序的步骤可以细化为：

划分问题：把序列分成元素个数尽量相等的两半
递归求解：把两半元素分别排序
合并问题：把两个有序表合并为一个

在合并两边已排好的元素时，因为两个序列都具有不下降性，所以只需要比较两个序列里最小的元素就可以。

对于实现，一般需要一个辅助数组；

#include<bits/stdc++.h>
using namespace std;
const int N =  1000005;
int a[N] ,b[N];//b为辅助数组
void merge_sort(int l , int r)
{
    if(l < r){ //如果整个区间中元素个数大于1，则继续分割
        int mid = (l + r) >> 2 ;  //位运算提高速度
        int i = l; //辅助数组的下标
        int p = l , q = mid+1;
        merge_sort(l,mid);
        merge_sort(mid+1 ,r);
        while(p<=mid || q<=r){//左右两部分只要有一部分不为空
            if(q>r || (p<=mid && a[p]<=a[q]))//右边空了或者右边的数更大一点，就把左边的这个数放到前面一点点，（从左半数组复制到辅助数组）
                b[i++] = a[p++];
            else b[i++] = a[q++];//从右半数组复制到辅助数组
        }
        for(i = l ; i <= r; i++)//将b中排好序的元素复制到a中
            a[i] = b[i];
    }
}
int main()
{
     int n;
     scanf("%d",&n);
     for(int i = 1 ; i <= n; i ++)  cin >> a[i];
     merge_sort(1 , n);
     for(int i = 1; i <= n; i++) cout << a[i] << " ";
     return 0;
}

归并排序的应用

1.求逆序对

（听说可以用树状数组，然鹅小蒟蒻还没有学，学了以后再补一个叭qwq）

在比较的时候考虑：如果左边最小的数都比右边这个数大，那么左边剩余的所有数都会比右边这个数大

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int a[N] ,b[N]; 
long long cnt;
void merge_sort(int l , int r)
{
    if(l < r){
        int mid = (l + r) / 2 ;
        int i = l; 
        int p = l , q = mid+1;
        merge_sort(l , mid);
        merge_sort(mid+1 , r);
        while(p<=mid || q<=r){
            if(q > r || (p <= mid && a[p] <= a[q])) b[i++] = a[p++];
            else{
                b[i++] = a[q++];
                cnt += mid -p +1;  //将逆序对的个数累加起来
            }
        }
        for(i = l ; i <= r; i++) a[i] = b[i];
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1 ; i <= n; i ++) cin >> a[i];
    cnt = 0;
    merge_sort(1 , n);
    printf("%lld",cnt);
    return 0;
}

浅谈归并排序

归并排序的理解

归并排序的应用

相关推荐