黑马程序员技术交流社区

标题: 合并排序 [打印本页]
作者: 马毅    时间: 2012-12-12 23:05
标题: 合并排序
本帖最后由 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    }
复制代码
以下是实现代码，欢迎指正：

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

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

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

  60.             }


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





欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2