我所理解的歸并排序算法
作者：goal00001111（高粱）
始發(fā)于goal00001111的專欄；允許自由轉(zhuǎn)載，但必須注明作者和出處
引子：這篇文章以前寫過，最近復(fù)習(xí)排序算法，覺得以前的代碼還可以改進(jìn)，因此有了此文。
歸并排序算法以O（NlogN）最壞情形運(yùn)行時(shí)間運(yùn)行，而所使用的比較次數(shù)幾乎是最優(yōu)的。
該算法中最基本的操作是合并兩個(gè)已排序的表，這只需要線性的時(shí)間，但同時(shí)需要分配一個(gè)臨時(shí)數(shù)組來暫存數(shù)據(jù)。
歸并排序算法可以用遞歸的形式實(shí)現(xiàn)，形式簡潔易懂。如果N=1，則只有一個(gè)元素需要排序，我們可以什么都不做；否則，遞歸地將前半部分?jǐn)?shù)據(jù)和后半部分?jǐn)?shù)據(jù)各自歸并排序，然后合并這兩個(gè)部分。
歸并排序算法也可以用非遞歸的形式實(shí)現(xiàn)，稍微難理解一點(diǎn)。它剛好是遞歸分治算法的逆向思維形式，在使用遞歸分治算法時(shí)，程序員只需考慮將一個(gè)大問題分成若干個(gè)形式相同的小問題，和解的邊界條件，具體如何解決這些小問題是由計(jì)算機(jī)自動(dòng)完成的；而非遞歸形式要求程序員從最基本的情況出發(fā)，即從解決小問題出發(fā)，一步步擴(kuò)展到大問題。
我這里兩種形式都給出。
另外，很多人在寫遞歸形式的歸并排序算法時(shí)，臨時(shí)數(shù)組是在MergeSort函數(shù)中分配的，這使得在任一時(shí)刻都可能有logN個(gè)臨時(shí)數(shù)組處在活動(dòng)期，如果數(shù)據(jù)較多，則開銷很大，實(shí)用性很差。
我把臨時(shí)數(shù)組設(shè)置在Merge函數(shù)中，避免了這個(gè)問題。
///////////////////////////////////////////////////////////////////////
遞歸形式：
template <class
T>
void MSort(T a[], int
left, int right)
{
if (left < right)
{
int center = (left + right) / 2;
MSort(a, left, center);
MSort(a, center+1, right);
Merge(a, left, center+1, right+1);
}
}
template <class
T>
void MergeSort(T a[],
int n)
{
MSort(a, 0, n-1);
}
///////////////////////////////////////////////////////////////////////
非遞歸形式：
算法介紹：先介紹三個(gè)變量beforeLen，afterLen和i的作用：
int beforeLen; //合并前序列的長度
int afterLen;//合并后序列的長度，合并后序列的長度是合并前的兩倍
int i = 0;//開始合并時(shí)第一個(gè)序列的起始位置下標(biāo)，每次都是從0開始
i，i+beforeLen，i+afterLen定義被合并的兩個(gè)序列的邊界。
算法的工作過程如下：
開始時(shí)，beforeLen被置為1，i被置為0。外部for循環(huán)的循環(huán)體每執(zhí)行一次，都使beforeLen和afterLen加倍。內(nèi)部的while循環(huán)執(zhí)行序列的合并工作，它的循環(huán)體每執(zhí)行一次，i都向前移動(dòng)afterLen個(gè)位置。當(dāng)n不是afterLen的倍數(shù)時(shí)，如果被合并序列的起始位置i，加上合并后序列的長度afterLen，超過輸入數(shù)組的邊界n，就結(jié)束內(nèi)部循環(huán)；此時(shí)如果被合并序列的起始位置i，加上合并前序列的長度beforeLen，小于輸入數(shù)組的邊界n，還需要執(zhí)行一次合并工作，把最后長度不足afterLen，但超過beforeLen的序列合并起來。這個(gè)工作由語句Merge(a, i, i+beforeLen, n);完成。
template <class
T>
void MergeSort(T a[],
int n)
{
int beforeLen; //合并前序列的長度
int afterLen = 1;//合并后序列的長度
for (beforeLen=1; afterLen<n; beforeLen=afterLen)
{
afterLen = beforeLen << 1; //合并后序列的長度是合并前的兩倍
int i = 0;//開始合并時(shí)第一個(gè)序列的起始位置下標(biāo)，每次都是從0開始
for ( ; i+afterLen<n; i+=afterLen)
Merge(a, i, i+beforeLen, i+afterLen);
if (i+beforeLen < n)
Merge(a, i, i+beforeLen, n);
}
}
///////////////////////////////////////////////////////////
上面兩種算法都要用到下面的合并函數(shù)。
/*函數(shù)介紹：合并兩個(gè)有序的子數(shù)組
輸入：數(shù)組a[]，下標(biāo)left，center，元素個(gè)數(shù)len，a[left]~a[center-1]及a[center]~a[len-1]已經(jīng)按非遞減順序排序。
輸出：按非遞減順序排序的子數(shù)組a[left]~a[len-1]。
*/
template <class
T>
void Merge(T a[], int
left, int center, int len)
{
T *t = new T[len-left];//存放被合并后的元素
int i = left;
int j = center;
int k = 0;
while (i<center && j<len)
{
if (a[i] <= a[j])
t[k++] = a[i++];
else
t[k++] = a[j++];
}
while (i < center)
t[k++] = a[i++];
while (j < len)
t[k++] = a[j++];
//把t[]的元素復(fù)制回a[]
for (i=left,k=0; i<len; i++,k++)
a[i] = t[k];
delete []t;
}