1 class Program
  2     {
  3         static void Main(string[] args)
  4         {
  5             int[] data = new int[] { 21, 37, 12, 56, 11, 78, 65, 96 };
  6             data = Sort(data);
  7             foreach (int a in data)
  8             {
  9                 Console.WriteLine(a.ToString());
 10             }
 11         }
 12         /// <summary>
 13         /// 归并排序之归：归并排序入口 
 14         /// Updated by Lihua at 05/06/2009
 15         /// </summary>
 16         /// <param name="data">无序数组</param>
 17         /// <returns>有序数组</returns>
 18         /// <author>lihua</author>
 19         /// <copyright>www.zivsoft.com</copyright>
 20         static int[] Sort(int[] data)
 21         {
 22             //若data为null，或只剩下1 or 0个元素，返回，不排序
 23             if (null == data || data.Length <= 1)
 24             {
 25                 return data;
 26             }
 27 
 28             //取数组中间下标
 29             //int middle = data.Length / 2; //方法一：除2取整数
 30             int middle = data.Length >> 1;  //方法二：位移 (感谢读者hyper给出的这个效率稍高的方法)
 31 
 32             //初始化临时数组let,right，并定义result作为最终有序数组，若数组元素奇数个，将把多余的那元素空间预留在right临时数组
 33             int[] left = new int[middle], right = new int[data.Length - middle], result = new int[data.Length];
 34 
 35             //下面这句对性能有些影响，所以在上面有了改进，直接用data.Length-middle初始化right数组
 36             //if (data.Length % 2 != 0) right = new int[middle + 1]; 
 37 
 38             //int i = 0, j = 0;
 39             //foreach (int x in data)//开始排序
 40             //{
 41             //    if (i < middle)//填充左数组
 42             //    {
 43             //        left[i] = x;
 44             //        i++;
 45             //    }
 46             //    else//填充右数组
 47             //    {
 48             //        right[j] = x;
 49             //        j++;
 50             //    }
 51             //}
 52 
 53             //上面的foreach被改成了for循环
 54             //for (int i = 0; i < data.Length; i++)
 55             //{
 56             //    if (i < middle)//用middle，不用left.Length
 57             //    {
 58             //        left[i] = data[i];
 59             //    }
 60             //    else
 61             //    {
 62             //        right[i - middle] = data[i]; //此处i-middle，让我省掉定义一个j，性能有所提高
 63             //    }
 64             //}
 65 
 66             //经调查,用Array.Copy的确比上面的for循环优化很多
 67             Array.Copy(data, 0, left, 0, middle);//拷贝左数组
 68             Array.Copy(data, left.Length, right, 0, right.Length); //拷贝右数组
 69             
 70             left = Sort(left);//递归左数组
 71             right = Sort(right);//递归右数组
 72             result = Merge(left, right);//开始排序
 73             //this.Write(result);//输出排序,测试用(lihua debug)
 74             return result;
 75         }
 76         /// <summary>
 77         /// 归并排序之并:排序在这一步
 78         /// </summary>
 79         /// <param name="a">左数组</param>
 80         /// <param name="b">右数组</param>
 81         /// <returns>合并左右数组排序后返回</returns>
 82         static int[] Merge(int[] a, int[] b)
 83         {
 84             //定义结果数组，用来存储最终结果
 85             int[] result = new int[a.Length + b.Length];
 86             int i = 0, j = 0, k = 0;
 87             while (i < a.Length && j < b.Length)
 88             {
 89                 if (a[i] < b[j])//左数组中元素小于右数组中元素
 90                 {
 91                     result[k++] = a[i++];//将小的那个放到结果数组
 92                 }
 93                 else//左数组中元素大于右数组中元素
 94                 {
 95                     result[k++] = b[j++];//将小的那个放到结果数组
 96                 }
 97             }
 98             while (i < a.Length)//这里其实是还有左元素，但没有右元素
 99             {
100                 result[k++] = a[i++];
101             }
102             while (j < b.Length)//右右元素，无左元素
103             {
104                 result[k++] = b[j++];
105             }
106             return result;//返回结果数组
107         }
108 
109     }

优质内容筛选与推荐>>
1、maven2工程报环境警告的解决办法
2、修改电脑OEM信息&IE标题栏修改
3、Python numpy.ZIP 安装问题
4、sql之left join、right join、inner join的区别（转）
5、redis 3.2 迁移到4.x注意事项 和 redis 4.0的主要特性