Java归并排序算法输出多余中间数组，如何修复？

你的归并排序代码能正确完成排序，但执行时会输出多个中间合并的数组结果，原因很明确：merge方法里的System.out.println(Arrays.toString(arr));会在每一次合并左右子数组时执行，而归并排序的过程需要多次合并操作，因此会打印所有中间状态的数组。

解决方法 #

要只输出最终排序后的数组，只需调整打印语句的位置：

• 删除merge方法中的打印语句
• 在main方法中，调用完divide完成排序后，再打印最终数组

修改后的代码 #

import java.util.Arrays;

class FirstClass {
    public static void divide(int[] arr) {
        if(arr.length == 1) {
            return;
        }

        int mid = arr.length/2;

        int[] leftHalf = new int[mid];
        int[] rightHalf = new int[arr.length - mid];

        for(int i = 0; i < mid; i++) {
            leftHalf[i] = arr[i];
        }
        for(int i = mid; i < arr.length; i++) {
            rightHalf[i - mid] = arr[i];
        }

        divide(leftHalf);
        divide(rightHalf);

        merge(arr, leftHalf, rightHalf);
    }

    public static void merge(int[] arr, int[] leftHalf, int[] rightHalf) {
        int i = 0, j = 0, k = 0;

        while(i < leftHalf.length && j < rightHalf.length) {
            if(leftHalf[i] < rightHalf[j]) {
                arr[k] = leftHalf[i];
                i++;
            } else {
                arr[k] = rightHalf[j];
                j++;
            }
            k++;
        }

        while(i < leftHalf.length) {
            arr[k] = leftHalf[i];
            k++; i++;
        }

        while(j < rightHalf.length) {
            arr[k] = rightHalf[j];
            k++; j++;
        }
        // 移除原有的打印语句
    }
    public static void main(String[] args) {
        int[] arr = {1,3,6,8,3,0,6};

        divide(arr);
        // 仅在排序完成后打印最终结果
        System.out.println(Arrays.toString(arr));
    }
}

可选：保留调试用的中间打印 #

如果需要保留中间数组打印用于调试，可以添加一个开关参数控制，这样既能在调试时查看过程，又能在正式运行时只输出最终结果：

import java.util.Arrays;

class FirstClass {
    // 调试开关：true打印中间结果，false仅打印最终结果
    private static final boolean DEBUG = false;

    public static void divide(int[] arr) {
        if(arr.length == 1) {
            return;
        }

        int mid = arr.length/2;

        int[] leftHalf = new int[mid];
        int[] rightHalf = new int[arr.length - mid];

        for(int i = 0; i < mid; i++) {
            leftHalf[i] = arr[i];
        }
        for(int i = mid; i < arr.length; i++) {
            rightHalf[i - mid] = arr[i];
        }

        divide(leftHalf);
        divide(rightHalf);

        merge(arr, leftHalf, rightHalf);
    }

    public static void merge(int[] arr, int[] leftHalf, int[] rightHalf) {
        int i = 0, j = 0, k = 0;

        while(i < leftHalf.length && j < rightHalf.length) {
            if(leftHalf[i] < rightHalf[j]) {
                arr[k] = leftHalf[i];
                i++;
            } else {
                arr[k] = rightHalf[j];
                j++;
            }
            k++;
        }

        while(i < leftHalf.length) {
            arr[k] = leftHalf[i];
            k++; i++;
        }

        while(j < rightHalf.length) {
            arr[k] = rightHalf[j];
            k++; j++;
        }

        // 仅当调试开关开启时打印中间结果
        if(DEBUG) {
            System.out.println(Arrays.toString(arr));
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,3,6,8,3,0,6};

        divide(arr);
        // 始终打印最终结果
        System.out.println(Arrays.toString(arr));
    }
}

内容的提问来源于stack exchange，提问作者Mohd. Saad Haider