题目描述

针对y总的模板，参考《算法 第4版》修改了一下
将归并部分的3个while循环改成一个for循环

int i = l, j = mid + 1;
for (int k = 0; k <  r - l + 1; k++){ //归并回到[l , r]
            if (i > mid)                 temp[k] = arr[j++]; //左边遍历完，取右边
            else if (j > r)             temp[k] = arr[i++]; //右边遍历完，取左边
            else if (arr[i] <= arr[j])  temp[k] = arr[i++]; //左边不大于右边，取左边
            else                        temp[k] = arr[j++]; //左边大于右边，取右边

        }

完整程序代码

import java.io.*;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int[] arr = new int[num];

        String[] str = br.readLine().split(" ");
        for(int i = 0; i < num; i++){
            arr[i] = Integer.parseInt(str[i]);
        }
        merge_sort(arr, 0, num - 1);
        for(int i : arr){
            System.out.print(i + " ");
        }

    }
    public static void merge_sort(int[] arr, int l, int r){
        if (l >= r) return;

        int mid = l + r >> 1;

        merge_sort(arr, l , mid);
        merge_sort(arr, mid + 1, r);

        int i = l, j = mid + 1;
        int[] temp = new int[r + 1 - l];
        for (int k = 0; k <  r - l + 1; k++){
            if (i > mid)                 temp[k] = arr[j++];
            else if (j > r)             temp[k] = arr[i++];
            else if (arr[i] <= arr[j])  temp[k] = arr[i++];
            else                        temp[k] = arr[j++];

        }
        for (i = l, j = 0; i <= r; i++, j++){
            arr[i] = temp[j];
        }

    }
}