7.1 算法的目标

对数组按照升序/降序进行排序
时间复杂度：O(nlogn)
空间复杂度：O(n)

7.2 算法的思想目标

归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行
从下往上，依次进行。将分组逐层进行合并成一个大的分组，最终完成排序

7.3 算法的具体步骤

以数组[4、5、8、1、7、2、6、3]为例
shep1：首先对其进行逐层拆分：
7、归并排序 - 图1
shep2：从下往上进行逐层进行合并，例如：
7、归并排序 - 图2
对两边的小序列进行比较，定义p1和p2分别指向小序列的第一个元素，p指向大序列的第一个元素
将两边小序列的比较小的数放入到大序列中，直到某个序列放完
然后将剩余没放完的数填充到大序列中，最后将大序列复制给数组。

  1.    public  static  void  sort(int [] nums,int left,int right){
  2.         if (left<right){
  3.             //首先进行逐层拆分
  4.             int middle=(left+right)/2;
  5.             sort(nums,left,middle);
  6.             sort(nums,middle+1,right);
  7.             //然后自下往上进行合并
  8.             merge(nums,left,right,middle);
  9.         }
  11.     }
  12.         //自下往上进行逐层合并的方法
  13.     private static void merge(int[] nums, int left, int right, int middle) {
  14.          //首先定义一个新的数组，作为大序列
  15.         int [] p =new int[right-left+1];
  16.         int index=0;
  17.         //创建两个小序列，其位置索引分别为left-middle, middle+1-right;
  18.         int p1=left,p2=middle+1;
  19.         while (p1<=middle&&p2<=right){
  20.             //从两个小序列中选取较小的数依次加入到大序列
  21.             if (nums[p1]<=nums[p2]){
  22.                 p[index++]=nums[p1++];
  23.             }else {
  24.                 p[index++]=nums[p2++];
  25.             }
  26.         }
  27.         //某个序列放完，然后将小序列放入剩余的大序列中
  28.         while (p1<=middle){
  29.             p[index++]=nums[p1++];
  30.         }
  31.         while (p2<=right){
  32.             p[index++]=nums[p2++];
  33.         }
  34.         //最后将p数组赋值给nums
  35.         for (int i = 0; i <p.length ; i++) {
  36.             nums[i+left]=p[i];
  37.         }
  38.     }