拿出讀書時寫的C代碼,現在看發現看不懂了,原因是當時學數據結構時沒寫清具體的思路,這次為避免同樣問題,把自己具體理解的過程寫下來,特別是一些細節,這樣以後用到時可以省下不少時間.
從上到下兩路歸並
歸並:
有兩個有序序列(即已經排序過的)A,B, 那麼可以通過以下方法將A,B序列合並成序列C.
取A,B的第一個元素進行比較,將較小的元素存入C,接著取下一個元素(存入C後那個元素序列的下一個),直到A,B其中一個序列為空,那麼將另外一個不為空的序列余下元素復制到C中,這樣就得到一個有序的C序列,其元素來自A,B兩序列.
以上描述可以用下面的C代碼表示:
-----------------------------------------
// r為待排序數組指針,buffer為輔助空間,其大小應該滿足:
// buffer.Length >=r.Length
void merge(int *r, int *buffer, int l, int m, int h)
{
int k;
int i,j;
// L (這裡大寫) 為第一個序列的開始下標,h為第二個序列的結束下標
// m 為 (L+h)/2 的值, 因此 L~M 為第一個序列的地址范圍,M+1 ~ h 為第二個序列的范圍
for(i=l,k=l,j=m+1; i<=m && j<=h;k++)
{
if(r[i] < r[j]) buffer[k]=r[i++];
else buffer[k]=r[j++];
}
//復制余下元素到輔助空間
while(i<=m)
buffer[k++]=r[i++];
while(j<=h)
buffer[k++]=r[j++];
}
歸並排序將待排序序列看作一個由r.Length( r為數組指針)個有序序列組成的集合(每個序列開始只有一個元素,因此這個只有一個元素序列必然是有序的), 我們將集合中的序列兩兩合並(歸並,使用上面的方法)形成較大的序列(2個元素),
而集合長度則變為原來的一半,如此往復下去,最後集合包含2個待排序的有序序列,歸並這兩個序列即得到排序的結果.
代碼( C描述)
-------------------------------
void msort(int *r, int *buffer,int l,int h)
{
//聲明函數原形
void merge(int *r, int *buffer, int l, int m, int h);
void copy(int * r, int *buffer, int l, int h);
int m;
if(l < h) //保證區間至少包括2個元素,只含一個元素的取間已經有序了
{ m=(l+h)/2;
msort(r,buffer,l,m); //排序左邊
msort(r,buffer,m+1,h); //排序右邊
merge(r,buffer,l,m,h); //合並左右兩個有序序列
copy(r,buffer,l,h); //將輔助空間中已經排序的元素復制回到r空間
}
}
說明:
上面的遞歸操作第一次輸入的L,h是數組r 的上下標(0,n-1),遞歸在L=H時開始反回,第一次反回後, H-L=1(2個元素的區間,實際上上H=1,L=0)因此有m=(h+l)/2=(L+L+1)/2=L (整數相除 3/2=1,5/2=2),這樣m+1=h ,msort(r,buffer,m+1,h) 調用直接返回(排序右邊的操作),
而merge(r,buffer,L,M,h)將歸並含2個元素的區間的兩個序列(每個序列有一個元素).完成後返回上一層.(這裡是0跟1元素排序完成後返回).
另外這裡先左還是先右效果是一樣的
記的當時學習時是將每次調用的各變量跟過程一一寫在紙上,逐步演推下來,這樣就比較清楚了.
關鍵點:
１． 兩個有序序列的合並
２．遞歸調用的返回條件設置,具體調用的推演
3. 兩個整數相除後的結果是取最接近這個實數,但不大於這個實數的整數,(比方 5/2=2.5 ,取2為結果)
下面是C#中使用泛型實現的歸並排序類:
------------------------------------------
public class MergeSort<T>
{
private static readonly MergeSort<T> _instance = new MergeSort<T>();
public static void Sort(T[] array, IComparer<T> comparer)
{
_instance.MSort(array, comparer);
}
private void Merge(T[] array, T[] buffer, int L, int m, int h,IComparer<T> comparer)
{
int k, i, j;
for (i = L, k = L, j = m + 1; i <= m && j <= h; k++)
{
if (comparer.Compare(array[i], array[j]) < 0) buffer[k] = array[i++];
else buffer[k] = array[j++];
}
while (i <= m)
buffer[k++] = array[i++];
while (j <= h)
buffer[k++] = array[j++];
for (i = L; i <= h; i++)
{
array[i] = buffer[i];
}
}
private void MSort(T[] array, IComparer<T> comparer)
{
T[] buffer = new T[array.Length];
int L = 0;
int h = array.Length - 1;
Sort(array, buffer, L, h,comparer);
}
private void Sort(T[] array, T[] buffer, int L, int h, IComparer<T> comparer)
{
int m = 0;
if (L < h)
{
m = (L + h) / 2;
Sort(array, buffer, L, m,comparer);
Sort(array, buffer, m + 1, h,comparer);
Merge(array, buffer, L, m, h,comparer);
}
}
}
客戶端調用代碼示例
------------------------------------
private void button1_Click(object sender, EventArgs e)
{
int[] t ={ 1, 8, 23, 234, 2, 6, 7, 77, 18, 21 };
MergeSort<int>.Sort(t, new IntComparer());
foreach (int i in t)
{
textBox1.Text += i + ",";
}
textBox1.Text= textBox1.Text.TrimEnd(",".ToCharArray());
textBox1.Text += Environment.NewLine;
string[] r ={ "A", "C", "B", "F", "K", "Z" };
MergeSort<string>.Sort(r, new StringComparer());
foreach (string item in r)
{
textBox1.Text += item + ",";
}
textBox1.Text= textBox1.Text.TrimEnd(",".ToCharArray());
textBox1.Text += Environment.NewLine;
string[] R ={ "X", "X", "P", "J", "K" };
MergeSort<string>.Sort(R, new StringComparer());
foreach (string item in R)
{
textBox1.Text += item + ",";
}
textBox1.Text = textBox1.Text.TrimEnd(",".ToCharArray());
textBox1.Text += Environment.NewLine;
}
public class StringComparer : IComparer<string>
{
public int Compare(string x, string y)
{
return string.Compare(x, y, true);
}
}
public class IntComparer : IComparer<int>
{
public int Compare(int x, int y)
{
return x - y;
}
}
--------------------------------------
從下到上兩路歸並
自下到上的兩路歸並排序消除了遞歸調用,首先按段長為1進行兩兩歸並,接著按段長為2進行兩兩歸並,這樣按照1,2,4,8,16....的長度歸並下去直到得到等長度的完整序列,在歸並時需要考慮最後元素個數在不足兩個段長時,或不足一個段長時的處理,MSort中采用在兩個數組裡互相拷的辦法虛擬地消除復制過程.
下面是C#的泛型實現代碼,客戶端調用參考上面的
--------------------------------------------------
public class MergeSortB<T>
{
private static readonly MergeSortB<T> _instance = new MergeSortB<T>();
public static void Sort(T[] array, IComparer<T> comparer)
{
_instance.MSort(array, comparer);
}
private void Merge(T[] a, T[] b, int L, int m, int h, IComparer<T> comparer)
{
int k, i, j;
for (i = L, k = L, j = m + 1; i <= m && j <= h; k++)
{
if (comparer.Compare(a[i], a[j]) < 0) b[k] = a[i++];
else b[k] = a[j++];
}
while (i <= m)
b[k++] = a[i++];
while (j <= h)
b[k++] = a[j++];
}
private void MSort(T[] a,IComparer<T> comparer)
{
int n = a.Length;
T[] b = new T[n];
int s = 1;//段長開始為1,段長將按1,2,4,8,16...這樣的方式增長
//s>=n時表示排序完成了,即段長達到數組長度
//for(s;s<n;s*=2)
//{
// MergePass(a,b,s,n,comparer);
//采用這個形式時需要在Merge中將元素從輔助空間中復制回數組中
//具體參考上面遞歸實現的Merge方法,另外MergePass也需要做相應修改
//}
while (s < n)
{
MergePass(a, b, s, n, comparer);
s += s;
//保證最終把b中的元素復制到A
MergePass(b, a, s, n, comparer);
s += s;
}
}
private void MergePass(T[] a, T[] b, int s, int n,IComparer<T> comparer)
{
int i = 0;
while (i + 2 * s < n)
{
// i 為當前位置,加上2倍的段長就是後一組(2段)的開始下標了
//當前位置下標加上段長是下一段第一個元素的下標(i+s),
//故第一段
Merge(a, b, i, i + s - 1, i + 2 * s - 1,comparer);
i += 2 * s;
}
//剩余的元素,不足兩個分段長度,但大於或等於一個段長度[s,2s-1]
if (i + s < n)
{
Merge(a, b, i, i + s - 1, n - 1, comparer);
}
else //剩余元素小於一個段長度,有可能為零個[0,s-1]
{
//這裡也有可能是用來把b中的全部元素復制回a,
//這時候i是0,參考MSort
while (i < n)
{
b[i] = a[i++];
}
}
}
}
參考
數據結構-排序: 兩路歸並排序算法
