算法学习之分治---并归

/**
 * @ClassName 并归排序
 * @Author ACER
 * @Description ToDo
 * @Date 2021/7/10 20:11
 * @Version 1.0
 **/
public class 并归排序 {
    public static void main(String[] args) {
        int [] a={1,5,1,3};
        int [] temp=new int[10];
        mergeSort(a,0,a.length-1,temp);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    public static void mergeSort(int [] nums,int start,int end,int []temp){
        if (start<end){
            int mid=start+(end-start)/2;
            mergeSort(nums,start,mid,temp);
            mergeSort(nums,mid+1,end,temp);
            merge(nums,start,mid,end,temp);
        }
    }
    public static void merge(int[]nums,int start,int mid,int end,int[] temp){
       int p1=start;
       int p2=mid+1;
       int pb=0;
       while (p1<=mid&&p2<=end){
            if (nums[p1]>nums[p2]){
                temp[pb++]=nums[p2++];
            }else {
                temp[pb++]=nums[p1++];
            }
       }
       //剩下的有些还没拷贝到
        while (p1<=mid){
            temp[pb++]=nums[p1++];
        }
        while (p2<=end){
            temp[pb++]=nums[p2++];
        }
        for (int i = 0; i < end - start+1; i++) {
            nums[start+i]=temp[i];
        }
    }
}