题解 | #排序#

import java.util.*;

//归并排序
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] nums) {

        int length = nums.length;
        //length 为 1出口
        if(length == 1)
        return nums;
        int i = 0;
        int[] numsleft = new int[length/2];
        int j = 0;
        while(i<length/2)
        {
            numsleft[j++] = nums[i++];
        }
        int k=0;
        int[] numsright = new int[length-length/2];
        while(i<length){
            numsright[k++] = nums[i++];
        } 
        numsleft = MySort(numsleft);
        numsright = MySort(numsright);
        int[] numsnew =
        merge(numsleft,numsright);//这里合并传入的是数组，不是下标
        return numsnew;
        // write code here
    }

    public int[] merge(int[] numsleft,int[] numsright){
    int left = numsleft.length;
    int right = numsright.length;
    int[]  numsnew = new int[left+right];
    int i=0;
    int j=0;
    int k=0;
    while(i<left&&j<right)//while语句长度比for语句短，while中的i,j可以进行切换、跳跃递增，for中的不可以
    { if(numsleft[i]<numsright[j])//不管是左边还是右边，小的放到新数组
        { numsnew[k++] = numsleft[i++];
        }else{
        numsnew[k++] = numsright[j++];  
        }
    }
    //把还未比较的一边的数一个个放到新的合并数组
    while(i==left&&j<right){
        numsnew[k++] = numsright[j++];    
        }
    while(i<left&&j==right){
    numsnew[k++] = numsleft[i++];    
    }
        return numsnew;
    }
  public int[] merge2(int[] numsleft,int[] numsright){
    int left = numsleft.length;
    int right = numsright.length;
    int[]  numsnew = new int[left+right];
    int i=0;
    int j=0;
    int k=0;
        while(i<left&&j<right){//
            if(numsleft[i] <= numsright[j] ){
            numsnew[k++] = numsleft[i++];
           
            } else {
            numsnew[k++] = numsright[j++];//不要写成right，会报指针异常错误
            }
        }
    //   if(j == right) {
    //     break;
    //   } 
    //   //内循环left先出来，循环不到头,内循环不判断left，会报指针异常错误，所以这里外循环无意义，还麻烦，虽然可能可以减少后续一个循环，但不好操作
    // }
        while(i<left&&j==right)
        {
            numsnew[k++] = numsleft[i++];
        }
        while(i==left && j< right)
        {
            numsnew[k++] = numsright[j++];
        }
        return numsnew;
}
}