拿出读书时写的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 { private static readonly MergeSort _instance = new MergeSort ();
public static void Sort(T[] array, IComparer comparer) { _instance.MSort(array, comparer); } private void Merge(T[] array, T[] buffer, int L, int m, int h,IComparer 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 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 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 .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 .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 .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 { public int Compare(string x, string y) { return string.Compare(x, y, true); } } public class IntComparer : IComparer { public int Compare(int x, int y) { return x - y; }
}
-------------------------------------- 从下到上两路归并 自下到上的两路归并排序消除了递归调用,首先按段长为1进行两两归并,接着按段长为2进行两两归并,这样按照1,2,4,8,16....的长度归并下去直到得到等长度的完整序列,在归并时需要考虑最后元素个数在不足两个段长时,或不足一个段长时的处理,MSort中采用在两个数组里互相拷的办法虚拟地消除复制过程. 下面是C#的泛型实现代码,客户端调用参考上面的
--------------------------------------------------
public class MergeSortB { private static readonly MergeSortB _instance = new MergeSortB ();
public static void Sort(T[] array, IComparer comparer) { _instance.MSort(array, comparer); } private void Merge(T[] a, T[] b, int L, int m, int h, IComparer 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 comparer) { int n = a.Length; T[] b = new T[n]; int s = 1;//段长开始为1,段长将按1,2,4,8,16...这样的方式增长 //s>=n时表示排序完成了,即段长达到数组长度 //for(s;s //{ // 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 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++]; } } } }
参考 数据结构-排序: 两路归并排序算法
http://haoxiai.net/bianchengyuyan/cyuyan/11929.html
