歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個(gè)非常典型的應(yīng)用翔脱。時(shí)間復(fù)雜度是O(nlogn)
核心思想
將一段序列分解知道不能再分解的時(shí)候磁滚，然后開(kāi)始逐層合并育韩，并在合并的時(shí)候保證他們有序，這樣就能保證每次合并后的內(nèi)容有序蛇更，直到合并完成保證了所有的部分全部有序瞻赶。
分治三步法：
- 劃分問(wèn)題：把序列分成元素個(gè)數(shù)盡量相等的兩半
- 遞歸求解：把兩半元素分別排序
- 合并問(wèn)題：把兩個(gè)有序表合并成一個(gè)
代碼實(shí)現(xiàn)
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);//合并左右兩個(gè)有序數(shù)列
}
}
合并的方法
合并時(shí)對(duì)象是兩個(gè)已排序好的數(shù)列，初始狀態(tài)下械荷，兩個(gè)指針?lè)謩e指向兩個(gè)待合并數(shù)列的第一個(gè)元素共耍，然后比較這兩個(gè)元素的大小，將較小的元素添加到一個(gè)新創(chuàng)建的數(shù)列中吨瞎。接著痹兜，被復(fù)制的數(shù)列中的指針后移，指向該較小的后繼元素颤诀。上述操作一直持續(xù)到兩個(gè)數(shù)列中的一個(gè)被處理完位置字旭。然后，在未處理完的數(shù)列中崖叫，剩下的元素被復(fù)制到新數(shù)組列的尾部遗淳。
合并實(shí)現(xiàn)
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)缺點(diǎn)
需要使用O(n)的輔助空間，而與之效率相同的快排和堆排需要O(logn)和O(1)的輔助空間心傀，在同類算法中歸并排序的空間復(fù)雜度略高屈暗。
優(yōu)點(diǎn)是穩(wěn)定性。
變形
- 可以自底向上合并數(shù)組的一個(gè)個(gè)元素對(duì)，然后再合并這些有序?qū)ρ眩源祟愅浦帜拧＿@樣能避免使用堆棧處理遞歸調(diào)用時(shí)的時(shí)間和空間開(kāi)銷。
比較適合用鏈表組織的數(shù)據(jù)弃甥。
- 把數(shù)組劃分為待排序的多個(gè)部分爽室，再對(duì)他們遞歸排序，最后將其合并在一起淆攻。適合對(duì)存放在二級(jí)存儲(chǔ)空間的文件進(jìn)行排序阔墩，也被稱為多路合并排序。
原方法也被稱之為二路合并排序瓶珊。
解決逆序?qū)?wèn)題
逆序?qū)Ω拍?/h3>
設(shè)A為一個(gè)有n個(gè)數(shù)字的有序集(n>1)啸箫，其中所有數(shù)字各不相同。如果存在正整數(shù)i,j使得1<=i<j<=n而且A[i]>A[j],則<A[i],A[j]>這個(gè)有序?qū)ΨQ為A的一個(gè)逆序?qū)瓒荆卜Q作逆序數(shù)筐高。
逆序?qū)亩x上分析，逆序?qū)褪菙?shù)列中任意兩個(gè)數(shù)滿足大的在前丑瞧，小的在后的組合。
所謂逆序?qū)?wèn)題蜀肘，即對(duì)給定的數(shù)組序列绊汹，求其逆序?qū)Φ臄?shù)量。
在算法實(shí)現(xiàn)中扮宠，略微修改原有的歸并排序西乖，當(dāng)右邊序列的元素為較小值是，就統(tǒng)計(jì)其產(chǎn)生的逆序?qū)?shù)量坛增，即可完成逆序?qū)Φ慕y(tǒng)計(jì)获雕。
代碼實(shí)現(xiàn)
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;//統(tǒng)計(jì)產(chǎn)生逆序?qū)Φ臄?shù)量
//mid-i+1為左邊剩余元素個(gè)數(shù)
}
}
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];
}
