时间戳

首页 > 解决方案 > 合并排序java错误（从edX.org学习

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

问题描述

这是我要合并排序的数组，位于静态 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);
}

这是merge功能：

// 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并将错误指向上面的代码，即 ERROR B。

这是源代码

标签： javasortingrecursionmergesortedx

解决方案

这非常接近。您所缺少的只是合并排序中的递归基本情况，正如所写的那样，它将无休止地递归，直到堆栈崩溃。它说：“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;
    }
}

推荐阅读