java - 我用 Java 编写的合并排序程序无法运行？

Question

我正在尝试创建我的简单合并排序程序，该程序完全用 Java 编写，试图进行排序。请告诉我，这里出了什么问题？

mergeSort.java:

import java.util.Arrays;

public class MyProgram {
    public static void main(String[] args){

        int[] list = {2, 5, 6, 7, 52, 64, 22, 10, 11, 14, 17, 18, 19};

        System.out.println("\t**BEFORE MERGE SORT**");
        System.out.println(Arrays.toString(list));

        mergeSort(list);

        System.out.println("\t**AFTER MERGE SORT**");
        System.out.println(Arrays.toString(list));
    }

    private static void mergeSort(int[] array){
        if(array.length > 1){
            int[] left = leftList(array);
            int[] right = rightList(array);

            mergeSort(left);
            mergeSort(right);

            //Merging the sorted half into equal parts.
            merge(array, left, right);
        }
    }

    private static int[] leftList(int[] array){
        int size = array.length/2;
        int left[] = new int[size];

        for(int i=0; i<size; i++){
            left[i] = array[i];
        }
        return left;
    }

    private static int[] rightList(int[] array){
        int size1 = array.length/2;
        int size2 = array.length - size1;
        int right[] = new int[size2];

        for(int i=0; i<size2; i++){
            right[i] = array[i+size1];
        }
        return right;
    }

    private static void merge(int[] result, int[] left, int[] right){
        int i1 = 0;
        int i2 = 0;

        for(int i=0; i<result.length; i++){
            if(i2>=right.length || (i1 < left.length && left[i1] <= right[i2])){
                result[i1] = left[i1];
                i1++;
            }
            else{
                result[i2] = left[i2];
                i2++;
            }
        }
    }
}

获得以下输出:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
    at com.programming16.MyProgram.merge(MyProgram.java:63)
    at com.programming16.MyProgram.mergeSort(MyProgram.java:28)
    at com.programming16.MyProgram.mergeSort(MyProgram.java:24)
    at com.programming16.MyProgram.mergeSort(MyProgram.java:24)
    at com.programming16.MyProgram.main(MyProgram.java:13)
    **BEFORE MERGE SORT**
[2, 5, 6, 7, 52, 64, 22, 10, 11, 14, 17, 18, 19]

非常感谢您的帮助!!

Answer 1

尝试合并时，您没有对索引进行足够的检查。进行比较时，需要确保左右索引都在数组的合适范围内(小于数组的大小)。如果其中一个索引不在合适的范围内，那么我们就知道我们已经完成了该数组，并且不必再进行任何比较，因为我们只需添加另一个数组中的剩余数字即可。尝试这样的事情:

private static void merge(int[] result, int[] left, int[] right){
    int i1 = 0; //left index
    int i2 = 0; //right index
    for (int i=0; i<result.length; i++){
        if (i1<left.length && i2<right.length){ //We have something in both lists
            if (left[i1]<=right[i2]){  //Add from left
                result[i] = left[i1];
                i1++;
            }else{ //Add from right
                result[i] = right[i2];
                i2++;
            }
        }
        //If we get to here we know one list is empty
        //We need to figure out which one is empty
        else if (i1<left.length){//Right is empty
            result[i] = left[i1]; //Add from left
            i1++;
        }else{ //Left is empty
            result[i] = right[i2]; //Add from right
            i2++;
        }
    }
}