歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用。時間復雜度是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);//合并左右兩個有序數列
    }
}

合并的方法

合并時對象是兩個已排序好的數列，初始狀態(tài)下，兩個指針分別指向兩個待合并數列的第一個元素，然后比較這兩個元素的大小，將較小的元素添加到一個新創(chuàng)建的數列中。接著，被復制的數列中的指針后移，指向該較小的后繼元素。上述操作一直持續(xù)到兩個數列中的一個被處理完位置。然后，在未處理完的數列中，剩下的元素被復制到新數組列的尾部。

合并實現

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

優(yōu)缺點

需要使用O(n)的輔助空間，而與之效率相同的快排和堆排需要O(logn)和O(1)的輔助空間，在同類算法中歸并排序的空間復雜度略高。

優(yōu)點是穩(wěn)定性。

變形

• 可以自底向上合并數組的一個個元素對，然后再合并這些有序對，以此類推。這樣能避免使用堆棧處理遞歸調用時的時間和空間開銷。

比較適合用鏈表組織的數據。

• 把數組劃分為待排序的多個部分，再對他們遞歸排序，最后將其合并在一起。適合對存放在二級存儲空間的文件進行排序，也被稱為多路合并排序。

原方法也被稱之為二路合并排序。

解決逆序對問題

逆序對概念

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