归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。时间复杂度是O(nlogn)

核心思想

将一段序列分解知道不能再分解的时候，然后开始逐层合并，并在合并的时候保证他们有序，这样就能保证每次合并后的内容有序，直到合并完成保证了所有的部分全部有序。

分治三步法：

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

代码实现

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];
}