.排序总讲.

embedded/2024/10/19 9:38:32/

在这里赘叙一下我对y总前四节所讲排序的分治思想以及递归的深度理解。

就以788.逆序对这一题来讲（我认为这一题对于分治和递归的思想体现的淋淋尽致）。

题目：

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤1000001≤𝑛≤100000，
数列中的元素的取值范围 [1,109][1,109]。

输入样例：

6
2 3 4 5 6 1

输出样例：

代码：

#include<bits/stdc++.h>using namespace std;
//对long long 重新定义一下 
typedef long long LL;int n;
//数组res储存较小的数值，为推导公式做准备
int a[100010],res[100010];
//因为逆序对最多的形况为数组倒序，大概有5*1e9
//会爆int，所以要开辟long long 
LL sum=0;
LL merge_sort(int a[],int l,int r)
{if(l>=r) return 0;int mid= l+r >> 1;//对左、右半边求内部逆序对数量 merge_sort(a,l,mid)+merge_sort(a,mid+1,r);int i=l,j=mid+1,k=0;//对分别在左右两边的数求逆序对数量 while(i<=mid&&j<=r)if(a[i]<=a[j]) res[k++]=a[i++];else {res[k++]=a[j++];/*因为左右两边分别排好序后，对逆序对的数量是毫无影响的，所以才有此推导公式*/ sum=mid-i+1+sum;//推导公式 }//扫尾 while(i<=mid) res[k++]=a[i++];while(j<=r) res[k++]=a[j++];//物归原主 for(i=l,k=0;i<=r;i++,k++)a[i]=res[k];//返回sum return sum;}
int main()
{scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);cout << merge_sort(a,0,n-1) << endl;
//	for(int i=0;i<n;i++)
//	cout << a[i] << " ";return 0;
}

递归与分治的理解

在递归排序时是先递归，在运算。为什么要先递归呢？

首先我们先来理解一下递归函数的意义在哪：递归函数是用来处理需要多次使用同一个一个思想或方法，这时我们不妨来调用其本身，然后在达到某一条件时结束递归。

接下来我们回到逆序对这一题，我们分治完第一步就是递归其本身，先求出仅仅处在左边（y总所讲红色小球）或者右边（绿色小球）的逆序对数量，然后计算出处在分界点两边的数组逆序对的数量（黄色小球）（最后这一步这才是使用分治以及递归函数的本质）。如果没有最后一步来实现逆序对的求解，那么每一次对只处在两边（红色、绿色）或分别处在两边的数组（黄色）的递归岂不是成了空谈？？

附上我丑陋的图解qwq：