归并排序 | 半卷书

归并排序

public class MergeSort {

    public static void main(String[] args) {
        int[] arr=new int[] {1,3,5,7,2,4,6,8,9};
        System.err.println(Arrays.toString(arr));
        //merge(arr, 0, 4, 8); 
        mergeSort(arr, 0, 8);
        System.err.println(Arrays.toString(arr));
    }

    //归并排序
    public static void mergeSort(int[] arr,int low,int high) {
        //递归结束条件
        if(low<high) {
            int mid=(high+low)/2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid+1, high);
            merge(arr, low, mid, high);
        }
    }

    //一轮归并
    public static  void merge(int[]arr,int low,int mid,int high) {

        int temp[]=new int[high-low+1];
        int index=0;
        int i=low;
        int j=mid+1;
        //循环条件是 左边索引小于mid ;右边索引小于high
        while(i<=mid&&j<=high) {

            if(arr[i]<=arr[j]) {
                temp[index]=arr[i];
                i++;
            }else {
                temp[index]=arr[j];
                j++;
            }
            index++;
        }
        //如果 左边剩余        1 3 5    2 4 
        while(i<=mid) {
            temp[index]=arr[i];
            i++;
            index++;
        }
        //如果 右边剩余        1 3 5    2 4 6 8
        while(j<=high) {
            temp[index]=arr[j];
            j++;
            index++;
        }
        for(int m=0;m<temp.length;m++) {
            arr[m+low]=temp[m];
        }
    }
}