合并排序java错误(从edX.org学习
合并排序java错误(从edX.org学习
提问于 2018-08-17 05:03:22
这是我想要合并排序的数组，位于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);
}下面是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;
}ERROR A：我在这里得到一个错误，说else语句没有if。如果我删除result[index++] = left[i++]下的大括号，它将运行并给出一个错误：Exception in thread "main" java.lang.StackOverflowError，并将错误指向上面的代码，即错误B。
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-08-17 05:49:22
这是非常接近的。您所缺少的就是合并排序中的递归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;
}
}Stack Overflow用户
发布于 2018-08-17 05:14:33
您的mergeSort()方法缺少一个条件。如果您的列表长度只有1，那么您必须停止进一步拆分它的尝试，只需返回它以进行合并。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51885313
复制相关文章
相似问题
腾讯云开发者
