A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 马毅 中级黑马   /  2012-12-12 23:05  /  1156 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 Mayi 于 2012-12-12 23:09 编辑

合并排序是对分治法的一个完美展现,若对一个数组进行合并排序,其思路是将该数组一分为二,然后递归排序,再把两个排好序的数组合二为一,达到排序的目的;
例如对一个数组{8,3,4,6}进行排序,其过程如下:
  1. {    5    3    4    6    }            //将数组一拆为二
  2. {    5    3    }    {    4    6    }            //再次拆
  3. {    5    }    {    3    }    {    4    }    {    6    }            //数组1和2比较,8 > 3 所以3先落位,然后是8,合并数组1和2为一个数组,数组3、4做同样的操作
  4. {    3    5    }    {    4    6    }            //数组1和2比较,1中的第一个元素小于2中的第一,第二,所以3先落位,5大于数组2中第一个,所以接下来是数组2中的4落位,然后比较
  5.                                                      //数组1中的5和数组2中的6,5 < 6 所以5先落位,然后剩下的6落位,得到排序好的数组
  6. {3    4    6    8    }
复制代码
以下是实现代码,欢迎指正:

  1.         static void MergeSort(ref int[] A)
  2.         {
  3.             if (A.Length > 1)
  4.             {
  5.                 //分
  6.                 int[] left = new int[A.Length / 2 + A.Length % 2];
  7.                 int[] right = new int[A.Length / 2];
  8.                 for (int n = 0; n < (A.Length / 2 + A.Length % 2); n++)
  9.                 {
  10.                     left[n] = A[n];
  11.                 }
  12.                 for (int n = 0; n < (A.Length / 2); n++)
  13.                 {
  14.                     right[n] = A[(A.Length / 2) + (A.Length % 2) + n];
  15.                 }
  16.                 //递归
  17.                 MergeSort(ref left);
  18.                 MergeSort(ref right);
  19.                 //合并,排序
  20.                 Merge(left, right, ref A);
  21.             }
  22.         }

  23.         static void Merge(int[] left, int[] right, ref int[] A)
  24.         {
  25.            
  26.             int i = 0, j = 0, k = 0;
  27.             while (i < left.Length && j < right.Length)
  28.             {

  29.                 if (left[i] <= right[j])
  30.                 {
  31.                     A[k] = left[i];
  32.                     i++;
  33.                 }
  34.                 else
  35.                 {
  36.                     A[k] = right[j];
  37.                     j++;
  38.                 }
  39.                 k++;
  40.                 if (i == left.Length)
  41.                 {
  42.                     for (; j < right.Length; j++)
  43.                     {
  44.                         A[k] = right[j];
  45.                         k++;
  46.                     }
  47.                 }
  48.                 if(j == right.Length)
  49.                 {
  50.                     for (; i < left.Length; i++)
  51.                     {
  52.                         A[k] = left[i];
  53.                         k++;
  54.                     }
  55.                 }

  56.             }


  57.         }
复制代码
多的不说了,有不对之处还请指出,
PS:觉得有些冗余,找机会在优化一下,如果有不同的看法希望不吝赐教,其他算法请看这里

评分

参与人数 1技术分 +1 收起 理由
宋天琪 + 1

查看全部评分

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马