java - 合并排序java错误(从edX.org学习

Question

这是我要合并排序的数组，位于static void main:

int[] lst = {6, 5, 4, 7, 2, 1, 9}

这是mergeSort函数:

static int[] mergeSort(int[] lst) {
    int n = lst.length; 
    int[] left;
    int[] right;

    // create space for left and right subarrays
    if (n % 2 == 0) {
        left = new int[n/2];
        right = new int[n/2];
    } 
    else {
        left = new int[n/2];
        right = new int[n/2+1];
    }

    // fill up left and right subarrays
    for (int i = 0; i < n; i++) {
        if (i < n/2) {
            left[i] = lst[i];
        }
        else {
            right[i-n/2] = lst[i];
        }
    }

    // **ERROR B**

    // recursively split and merge
    left = mergeSort(left);
    right = mergeSort(right);

    // merge
    return merge(left, right);
}

这是合并函数:

// the function for merging two sorted arrays
static int[] merge(int[] left, int[] right) {
    // create space for the merged array
    int[] result = new int[left.length+right.length];

    // running indices
    int i = 0;
    int j = 0;
    int index = 0;

    // add until one subarray is deplete
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result[index++] = left[i++];
        { // **ERROR A** [ see description below ]
        else {
            result[index++] = right[j++];
        }
    }

    // add every leftover elelment from the subarray 
    while (i < left.length) {
        result[index++] = left[i++];
    }

    // only one of these two while loops will be executed
    while (j < right.length) {
        result[index++] = right[j++];
    }

    return result;
}

错误 A:我在这里收到一个错误，指出没有 if 的 else 语句。如果我删除 result[index++] = left[i++] 下的大括号，它将运行并给出错误: Exception in thread "main"java.lang.StackOverflowError 并将错误指向上面的代码，即错误 B。

Here's the source code

Answer 1

这非常接近。您所缺少的只是递归 base case在你的合并排序中，正如所写的，它将无休止地递归，直到堆栈崩溃。它说:“0 或 1 项的列表？继续拆分!”

归并排序的关键实现是单元素数组或零元素数组已经排序。这是基本情况。代码如下:

if (n <= 1) {
    return lst; // this list is already sorted
}

至于您的其他错误，这只是一个不匹配的括号，修复它应该会给您带来堆栈溢出错误，这是您的主要问题，与括号问题无关。这是完整的工作代码:

class Main {
    public static void main(String[] args) {
        int[] lst = {6, 5, 4, 7, 2, 1, 9};
        System.out.println(java.util.Arrays.toString(mergeSort(lst)));
    }

    static int[] mergeSort(int[] lst) {
        int n = lst.length; 

        if (n <= 1) {
            return lst;
        }

        int[] left;
        int[] right;

        if (n % 2 == 0) {
            left = new int[n/2];
            right = new int[n/2];
        } 
        else {
            left = new int[n/2];
            right = new int[n/2+1];
        }

        for (int i = 0; i < n; i++) {
            if (i < n / 2) {
                left[i] = lst[i];
            }
            else {
                right[i-n/2] = lst[i];
            }
        }
        
        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

    static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length+right.length];
        int index = 0;
        int i = 0;
        int j = 0;

        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                result[index++] = left[i++];
            }
            else {
                result[index++] = right[j++];
            }
        }

        while (i < left.length) {
            result[index++] = left[i++];
        }

        while (j < right.length) {
            result[index++] = right[j++];
        }

        return result;
    }
}