排序算法（2）归并排序

• 算法思想
  将原问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
• 归并排序操作
  分解：将待排序的包含n个元素的序列分解为各含n/2个元素的子序列
  解决：使用归并排序递归的排序两个子序列
  合并：合并两个子序列以产生已排序的答案
• 归并排序算法时间复杂度 θ（nlgn）
• 归并排序伪代码实现
  排序子数组A[p..r]中的元素
  

• 归并排序之C#实现
  

  using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  using System.Threading.Tasks;
  
  namespace MergeSort
  {
      class Program
      {
          static void Main(string[] args)
          {
              Random rd = new Random();
              int[] data = new int[49];
              for (int i = 0; i < data.Length; i++)
              {
                  data[i] = rd.Next(100);
              }
              MergeSort(data, 0, data.Length-1);
          }
          static void MergeSort(int[] arr,int p,int r)
          {
              //排序子数组arr[p..r]中的元素
              if (p >= r) return;
              int q =(int)Math.Floor((p + r) / 2.0); //Math.Floor向下取整
              MergeSort(arr, p, q);
              MergeSort(arr, q + 1, r);
              Merge(arr, p, q, r);
          }
          static void Merge(int[] arr,int p,int q,int r)
          {
              //假设arr[p..q]和arr[q+1,r]都已排好序
              //从两个数组中取较小的元素至输出数组中，知道其中一个输入数组为空，
              //然后将剩余输入数组中元素全部移到输出数组，为了避免在每一步都判断输入数组是否为空，
              //在两个输入数组尾部放置一个哨兵 inf
              int n1 = q - p + 1;
              int n2 = r - q;
              //创建左右两个新的数组
              int[] LeftArr = new int[n1 + 1];
              int[] RightArr = new int[n2 + 1];
              for(int i=0;i<n1;++i)
              {
                  LeftArr[i] = arr[p + i];
              }
              for(int i=0;i<n2;++i)
              {
                  RightArr[i] = arr[q + 1 + i];
              }
              LeftArr[n1] = int.MaxValue;
              RightArr[n2] = int.MaxValue;
              int m = 0;
              int n = 0;
              for(int k=p;k<=r;++k)
              {
                  if (LeftArr[m] < RightArr[n])
                  {
                      arr[k] = LeftArr[m];
                      m++;
                  }
                  else
                  {
                      arr[k] = RightArr[n];
                      n++;
                  }
              }
          }
      }
  }