归并排序

https://www.cnblogs.com/chengxiao/p/6194356.html

package test;

import java.util.Arrays;

/**
 * Created by Huwenxian on 2019/7/14.
 */



public class 归并排序 {

    public static void main(String[] args) {
        int arr[] = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


      public static void sort(int []arr){
    //在排序前，先建立一个长度相同的数组，避免在递归的过程中频繁的开辟空间
      int []temp = new int[arr.length];
      sort(arr,0,arr.length-1,temp);
      }

    public static void sort(int []arr, int left, int right, int []temp){
        if (left<right){
            //不断地递归分到不可再分,开始合并排序
            int mid = (left+right)/2;
            //分成左右两边拆开

            sort(arr,left,mid,temp);
            sort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }


    //合并数组
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int  i = left;//左序列指针
        int  j = mid +1;//右序列指针
        int  t = 0;//临时数组指针
        while(i<=mid && j<=right){
            if (arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        //右边那一半的数组全都被对比排序迁移进temp完成，（左边的数组已经排序过所以剩下的可以直接迁移）将左边的剩余数组元素全都迁入temp
        //j>righy
        while (i<=mid){
            //左边剩余元素填入temp
            temp[t++] = arr[i++];
        }
        //左边那一半的数组全都被对比排序迁移完成,（右边的数组已经排序过所以剩下的可以直接迁移）将右边剩余数组元素迁入temp
        //i>mid
        while (j<=right){
            temp[t++] = arr[j++];
        }

        //temp数组排序完毕，将temp中的数组元素复制到原数组arr内
        t = 0;
        while (left <=right){
            arr[left++] = temp[t++];
        }
    }


}