合并排序 Java 错误(从 edX.org 中学习

Question

这是我想要合并排序的数组，位于静态 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：我在这里收到一个错误，说 else 语句没有如果。如果我删除result[index++] = left[i++]下的大括号，它将运行并给我一个错误：Exception in thread "main" java.lang.StackOverflowError并将错误指向上面的代码，即错误 B。

这是源代码

Answer 1

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

Answer 2

您的 mergeSort(( 方法缺少条件。如果你的列表只有 1 的长度，你必须停止尝试进一步拆分它，只返回它进行合并。