分治法把大问题化成小问题逐个解决，可以优化算法复杂度（局部的优化有利于全局，一个问题的解决，其影响力扩大了k倍，即扩大到了全局）。
（1）分解（2）求解子问题，对子序列排序（3）合并
和交换排序相似，但合并两个有序的子序列效率更高。
图解释得很清楚，就是比较两个子序列，得到的数存到另一个数组里。（とても簡単です）
排序是竞赛中的常用功能，一般直接使用STL的sort()函数，并不需要自己再写一个排序的程序。不过也有一些特殊的问题，需要写出程序，并在程序内部做一些处理，例如逆序对问题。
放题：http://acm.hdu.edu.cn/showproblem.php?pid=4911
k=0直接暴力求有多少个逆序对，然后你就快快乐乐地TLE了。
在子序列里元素都是有序的，不存在逆序对，逆序对只存在于不同的子序列之间。
如果前一个子序列元素比后面元素大，就会产生逆序对。（注意产生的逆序对个数不止一个：cnt+=mid-i+1）
当k不等于0时，又分两种情况：
（1）cnt<=k，总逆序对交换次数<k，那么最少的逆序对数量为0.
（2）cnt>k，k次交换都发生在逆序的相邻数上，那么剩余的逆序对是cnt-k。
放代码：
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std;int a[100005],b[100005],cnt;
void Merge(int l,int mid,int r){//归并
int i=l,j=mid+1,t=0;
while(i<=mid&&j<=r){
if(a[i]>a[j]){
b[t++]=a[j++];
cnt+=mid-i+1;//上面提到过的记录逆序对数量
}
else
b[t++]=a[i++];
} //一个子序列中的数都处理完了，另一个还没有，把剩下的直接复制过来
while(i<=mid){
b[t++]=a[i++];
}
while(j<=r){
b[t++]=a[j++];
}
for(i=0;i<t;i++){
a[l+i]=b[i];//排好序的b[]复制回a[]
}
}void Mergesort(int l,int r){//归并
if(l<r){
int mid=(l+r)/2;//平分成两个子序列
Mergesort(l,mid);
Mergesort(mid+1,r);
Merge(l,mid,r);//合并
}
}
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k)){
cnt=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
Mergesort(0,n-1);
if(cnt<=k)
printf("0\n");
else
printf("%I64d\n",cnt-k);
}
return 0;
}
逆序对除了可以用归并，还可以用树状数组求解......这个东西就放在以后再说吧！
应用：求第k大数问题，递归包含第k个数的那部分就行了。
（唉，反正一般还是sort嘛，了解思想就行啦，sort用法之前的博客已经写过咯）
EOF
原文：https://www.cnblogs.com/Untergehen/p/14315892.html