最近学习逆序对，发现竟然要学习归并排序，于是只好学了一下（之前一直用C++ STL的sort函数），发现思想和线段树竟然惊人的相似，先放一张图你们就懂了：
怎么样，是不是发现这就是一棵线段树！其实归并排序利用了二分的思想，即分而治之。
归并排序是一种稳定的方法， 时间复杂度：O(nlogn)，空间复杂度：O(n)
是不是很优秀啊，现在我们就来讲解一下算法的流程：
void gb_sort(int l,int r){ if(l == r)return; int mid = (l+r) >> 1; gb_sort(l,mid); gb_sort(mid+1,r); hb_sort(l,mid,r); }1.不断二分区间，直到将他们分到只有两个数后在返回时不断归并
2.从底向上归并，由此我们才可以将一个个排序好的小区间归并成大区间
void hb_sort(int l,int mid,int r){ int left = l,right = mid+1; while(left <= mid && right <= r){ if(a[left] > a[right]){ que.push(a[right]); right++; } else{ que.push(a[left]); left++; } } while(left <= mid){ que.push(a[left]); left++; } while(right <= r){ que.push(a[right]); right++; } while(!que.empty()){ a[l++] = que.front(); que.pop(); } }假如我们要合并的两个序列为1，5，15，16和4，8，9，10。
然后将数值小的下标加一，往后移。就便成了
这里4比5小，所以4入队，一直重复操作
直到完成，而这时还剩下两个，再将他们入队
然后再将队列里的数拷贝回原数组
由于我们每次要合并的区间由小到大，即从底向上合并，而且合并的区间长度大于2，也就是下图的红色区间：
3.这样我们就得到了一个有序的区间，之后的每次合并都这样操作，每一层合并为O(n),共有logn层，所以总的时间复杂度为
O(nlogn)
先看一道题：逆序对
在本题中我们要求的是当i<j时，a[i] > a[j]的个数，不难想到归并排序,而且只需在原来的代码上做一点小小的改动，
我们只需要记录每次后半段的数入队时，前半段有多少个数比他大，用一个ans统计就好了。
是不是很妙蛙！
下面我们直接来看代码：
#include <iostream> #include <cstdio> #include <queue> using namespace std; int n,ans; int a[40005]; queue<int>que; void hb_sort(int l,int mid,int r){ int left = l,right = mid+1; while(left <= mid && right <= r){ if(a[left] > a[right]){ que.push(a[right]); ans += mid-left+1;//求逆序对个数 right++; } else{ que.push(a[left]); left++; } } while(left <= mid){ que.push(a[left]); left++; } while(right <= r){ que.push(a[right]); right++; } while(!que.empty()){ a[l++] = que.front(); que.pop(); } } void gb_sort(int l,int r){ if(l == r)return; int mid = (l+r) >> 1; gb_sort(l,mid); gb_sort(mid+1,r); hb_sort(l,mid,r); } int main(){ scanf("%d",&n); for(int i = 1;i <= n; i++)scanf("%d",&a[i]); gb_sort(1,n); //for(int i = 1;i <= n; i++)printf("%d ",a[i]); printf("%d",ans); }
