各种算法的C#实现系列

xabc2011 贡献于2011-11-10

作者 thinkpad  创建于2010-07-23 11:52:00   修改者thinkpad  修改于2010-07-23 11:52:00字数4303

文档摘要:合并排序算法是用分治策略实现对n个元素进行排序的算法。 其基本思想是:将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的子集合合并成所要求的排好序的集合。
关键词:

各种算法的C#实现系列2 - 合并排序的原理及代码分析     合并排序算法是用分治策略实现对n个元素进行排序的算法。 其基本思想是:将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的子集合合并成所要求的排好序的集合。 合并排序算法递归实现的程序: class MergeRecursion where T: new()  {  public void MergeSort(List li, int left, int right)  {  //临时存储数据区  List li_b = new List(100);  for (int i = 1; i <= 100; i++)  {  T item = new T();  li_b.Add(item);  }  //判断,保证至少有个元素  if (left < right)  {  //取中点  int m = (left + right) / 2;  MergeSort(li, left, m);  MergeSort(li, m + 1, right);  //合并到数组b  MergeCommon.Merge(li, li_b, left, m, right);  //复制回数组a  Copy(li, li_b, left, right);  }  else  {  return;  }  } private static void Copy(List li, List li_b, int left, int right)  {  for (int i = left; i <= right; i++)  {  li[i] = li_b[i];  }  }  }   Merge方法将两个排好序的数组段合并到一个新的数组b中,然后由Copy将合并后的数组段再复制回a中。合并算法Merge的实现如下: class MergeCommon  {  public static void Merge(List li, List li_b, int left, int m, int right)  {  //比较用 BComparer bc = BComparer.Instance;  //合并li[left:m]和li[m+1:right]到d[left:right]  int i = left;  int j = m + 1;  int k = left;  while ((i <= m) && (j <= right))  {  if(bc.Compare(li[i],li[j]) <= 0)  {  li_b[k++] = li[i++];  }  else  {  li_b[k++] = li[j++];  }  }  if (i > m)  {  for (int q = j; q <= right; q++)  {  li_b[k++] = li[q];  }  }  else  {  for (int q = i; q <= m; q++)  {  li_b[k++] = li[q];  }  }  }  }  合并排序的非递归实现     由于递归操作是一种较消耗资源的操作,可以考虑实现无递归的合并排序     思想:首先将数组a中相邻的元素两两配对。用合并算法将他们排序,构成n/2组长度为2排好序的子数组段,然后再将它们排序成长度为4的排好序的子数组段,如此继续下去,直至整个数组排序好。 此思想的算法实现: class MergeNRecursion where T: new()  {  public void MergeSort(List li, int n)  {  //临时存储数据区  List li_b = new List(100);  for (int i = 1; i <= 100; i++)  {  T item = new T();  li_b.Add(item);  }  int s = 1;  while (s < n)  {  MergePass(li,li_b,s,n);  s += s;  MergePass(li_b,li,s,n);  s += s;  }  }  private static void MergePass(List li, List li_b, int s, int n)  {  … …  }  }  其中MergePass用于合并排好序的相邻数组段。而具体的合并算法同样由Merge来实现。   MergePass算法实现:  private static void MergePass(List li, List li_b, int s, int n)  {  //合并大小为s的相邻子数组  int i = 0;  while (i <= n - 2 * s)  {  //合并大小为s的相邻2段子数组  MergeCommon.Merge(li,li_b,i,i+s-1,i+2*s-1);  i = i + 2 * s;  }  //剩下的元素个数少于2s  if (i + s < n)  {  MergeCommon.Merge(li, li_b, i, i + s - 1, n - 1);  }  else  {  for (int j = i; j <= n - 1; j++)  {  li_b[j] = li[j];  }  }  }    解释:剩余元素个数少于2s后的处理程序中,i + s < n 这句判断可以得出个数不足2s的那段数组是否已排过序,如果if条件成立,说明剩余元素还未排过序,需要调用Merge方法排序,否则说明在前一次MergePass执行过程中就已经对相同的数组段进行过排序,不用重复进行,只需要直接复制到另一个数组即可(else实现)。 这种非递归的合并排序拥有自然合并排序的基本思想 算法中一个很重要的代码是对泛型对象的大小比较,代码来自光辉的晨星的Blog原文见此。 把代码粘贴于此: public class BComparer  { //比较委托  Comparison _comparison;  static readonly Dictionary _map = new Dictionary();  //实现单例(代替构造函数的功能)  static readonly BComparer _instance = new BComparer();  //构造函数 private BComparer() { }  public static BComparer Instance  {  get  {  System.Diagnostics.Debug.Assert(_map.ContainsKey(typeof(T)));  //强转为具体的比较委托  _instance._comparison = (Comparison)_map[typeof(T)];  return _instance;  }  }  //情态构造,初始化  static BComparer()  {  //基础类型比较器  Type t = typeof(T);  if (t == typeof(bool))  {  Comparison cmp_bool = delegate(bool t1, bool t2)  { return t1 == t2 ? 0 : (t1 ? 1 : -1); };  _map.Add(typeof(bool), (Delegate)cmp_bool);  }  if (t == typeof(int))  {  Comparison cmp_int = delegate(int t1, int t2)  { return t1 > t2 ? 1 : (t1 == t2 ? 0 : -1); };  _map.Add(typeof(int), (Delegate)cmp_int);  }  //.其他 }  //注册自定义比较  public static void Register(Comparison comparison)  {  System.Diagnostics.Debug.Assert(_map.ContainsKey(typeof(NT)) == false);  _map.Add(typeof(NT), (Delegate)comparison);  }  //比较函数,以后用来实现IComparer用  public int Compare(T t1, T t2)  {  System.Diagnostics.Debug.Assert(_comparison != null);  return _comparison(t1, t2);  }  }        原书文章中提到了自然合并排序,自然合并排序是上述非递归合并排序算法的一个变形。其基本思想是初始序列中有自然排好序的子数组,用1次对数组线性扫描就足以找出所有这些排好序的子数组段。将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组。这样继续下去直至真个数组排好序。这样就比从1开始排相邻的元素效率要高很多。 下面是个人实现的一种自然排序,请指点: class MergeNature where T : new()  {  //扫描遍子数组 public static List GetChildArray(List li)  {  //保存子数组长度(最后一个元素位置) List arr = new List(100);    int i = 0;  arr.Add(-1);    BComparer bc = BComparer.Instance;    while (i < li.Count - 1)  {  if (bc.Compare(li[i], li[i + 1]) <= 0)  {  i++;  continue;  }  else  {  arr.Add(i);  i++;  }  }  if (arr[arr.Count - 1] != 29)  {  arr.Add(29);  }  return arr;  }    ///   /// 合并子数组(即列表)  ///   ///   public static void MergeSort(List li)  {  //调用GetChildArray获取arr  List arr = GetChildArray(li);    //临时存储数据区  List li_b = new List(100);  for (int i = 1; i <= 100; i++)  {  T item = new T();  li_b.Add(item);  }  int s = 1;  while (s < arr.Count - 1)  {  MergePass(li, li_b, s, arr);  s += s;  MergePass(li_b, li, s, arr);  s += s;  }  }    private static void MergePass(List li, List li_b, int s, List arr)  {  int i = 0;  int length = arr.Count - 1;    while (i <= length - 2 * s )  {  MergeCommon.Merge(li, li_b, arr[i] +  1, arr[i + s], arr[i + 2 * s]);  i = i + 2 * s;  }    //arr数组中剩余元素个数少于s  if (i + s < length)  {  MergeCommon.Merge(li, li_b, arr[i] + 1, arr[i + s], arr[length]);  }  else  {  for (int j = arr[i] + 1; j <= arr[length]; j++)  {  li_b[j] = li[j];  }  }  }  } 

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档