归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。时间复杂度是O(nlogn)
核心思想
将一段序列分解知道不能再分解的时候，然后开始逐层合并，并在合并的时候保证他们有序，这样就能保证每次合并后的内容有序，直到合并完成保证了所有的部分全部有序。
分治三步法：
- 划分问题：把序列分成元素个数尽量相等的两半
- 递归求解：把两半元素分别排序
- 合并问题：把两个有序表合并成一个
代码实现
void mergeSort(int a[],int sta,int end,int tmp[])
{
if(sta<end)
{
int mind=(sta+end)/2;
mergeSort(a,first,mid,tmp);//使左边排列有序
mergeSort(a,mid+1,end,tmp);//使右边排列有序
mergeArray(a,sta,mid,end,tmp);//合并左右两个有序数列
}
}
合并的方法
合并时对象是两个已排序好的数列，初始状态下，两个指针分别指向两个待合并数列的第一个元素，然后比较这两个元素的大小，将较小的元素添加到一个新创建的数列中。接着，被复制的数列中的指针后移，指向该较小的后继元素。上述操作一直持续到两个数列中的一个被处理完位置。然后，在未处理完的数列中，剩下的元素被复制到新数组列的尾部。
合并实现
Merge(int left[],int right,int tmp[])
{
int i=0,j=0,k=0;
while(i<len1&&j<len2)
{
if(left[i]<right[j])
{
tmp[k++]=left[i++];
}else
{
tmp[k++]=right[j++];
}
}
while(i<len1) tmp[k++]=left[i++];
while(j<len2) tmp[k++]=right[j++];
}
优缺点
需要使用O(n)的辅助空间，而与之效率相同的快排和堆排需要O(logn)和O(1)的辅助空间，在同类算法中归并排序的空间复杂度略高。
优点是稳定性。
变形
- 可以自底向上合并数组的一个个元素对，然后再合并这些有序对，以此类推。这样能避免使用堆栈处理递归调用时的时间和空间开销。
比较适合用链表组织的数据。
- 把数组划分为待排序的多个部分，再对他们递归排序，最后将其合并在一起。适合对存放在二级存储空间的文件进行排序，也被称为多路合并排序。
原方法也被称之为二路合并排序。
解决逆序对问题
逆序对概念
设A为一个有n个数字的有序集(n>1)，其中所有数字各不相同。如果存在正整数i,j使得1<=i<j<=n而且A[i]>A[j],则<A[i],A[j]>这个有序对称为A的一个逆序对，也称作逆序数。
逆序对从定义上分析，逆序对就是数列中任意两个数满足大的在前，小的在后的组合。
所谓逆序对问题，即对给定的数组序列，求其逆序对的数量。
在算法实现中，略微修改原有的归并排序，当右边序列的元素为较小值是，就统计其产生的逆序对数量，即可完成逆序对的统计。
代码实现
void msort(int s,int t)
{
if(s==t) return;
int mid=(s+t)/2;
msort(s,mid);
msort(mid+1,t);
int i=s,j=mid+1,k=s;
while(i<=mid && j<=t)
{
if(a[i]<=a[j])
r[k++]=a[i++];
else
{
r[k++]=a[j++];
ans+=mid-i+1;//统计产生逆序对的数量
//mid-i+1为左边剩余元素个数
}
}
while(i<=mid) r[k++]=a[i++];
while(j<=t) r[k++]=a[j++];
for(int i=s;i<t;i++) a[i]=r[i];
}
