2

我在合并排序中遇到堆栈溢出错误。还不知道为什么。

//BAD CODE BAD CODE
public static void main(String[] args) {
    int[] S = {3,4,6,2,5,3,7};
    mergesort(S, 1, 5);
    System.out.println(S);
}   

public static void mergesort(int[] S, int left, int right){
    if (right <= 1) { return; }
    int mid = (right + left) / 2;
    mergesort (S, left, mid);
    mergesort (S, mid+1, right);
    merge(S, left, mid, right); 
}

public static void merge(int[] S, int left, int mid, int right){
    int i, j;
    int[] aux = new int[S.length];

    for (i = mid+1; i > left; i--) {aux[i-1] = S[i-1];}
    for (j = mid; j < right; j++) {aux[right+mid-j] = S[j+1];}
    for (int k = left; k <= right; k++){
        if (aux[j] < aux[i]) {
            S[k] = aux[j--]; 
        } else{
            S[k] = aux[i++];
        }
    }
}
//END OF BAD CODE

更新

感谢您的所有快速回复，我得到了它的工作并提出了一些建议的更改。复制粘贴，试试看：

//GOOD CODE
package longest_sequence_proj;
import java.util.*;

public class MergeTest {

/**
 * @param args
 */
public static void main(String[] args) {
    int[] S = {3,4,6,2,5,3,7};

    mergesort(S, 0, 6);

    System.out.println(Arrays.toString(S));

}



public static void mergesort(int[] S, int left, int right){
    if (right <= left) { return; }
    int mid = (right + left) / 2;
    mergesort (S, left, mid);
    mergesort (S, mid+1, right);
    merge(S, left, mid, right);

    }

public static void merge(int[] S, int left, int mid, int right){
    int i, j;
    int[] aux = new int[S.length];

    for (i = mid+1; i > left; i--) {aux[i-1] = S[i-1];}
    for (j = mid; j < right; j++) {aux[right+mid-j] = S[j+1];}
    for (int k = left; k <= right; k++){
        if (aux[j] < aux[i]) {
            S[k] = aux[j--]; 
        } else{
            S[k] = aux[i++];
        }
    }
}
}
4

3 回答 3

3

您的停止条款是错误的：

 if (right <= 1) { return; }

当使用的部分数组的大小小于 1时，您实际上想要停止，因此您可能正在寻找：

if (right - left <= 1) { return; }

作为旁注：

System.out.println(S);

我想这不是你想要的（它不打印数组，而是对象的标识符......）
为了打印数组使用：

System.out.println(Arrays.toString(S));
于 2012-09-29T21:29:20.887 回答
2

好吧，考虑一下：

int mid = (right + left) / 2;
...
mergesort (S, mid+1, right);

从left=1和right=5开始，mid变成3，所以递归调用是left=4和right=5。这会产生 mid=9/2，我猜在 java 中是 4，​​所以我们得到了 left=5 和 right=5 的另一个递归，这导致 mid=5 和 left=6 和 right=5 的递归等等。“对”永远不会变小……

于 2012-09-29T21:31:42.980 回答
0

你的右支mergesort电话永远不会结束。

你的停止条件是right <= 1- 但在你的调用树的右分支上right永远不会1。

你应该为你的递归设置一个更好的结束条件——这实际上会在某个时候结束。

于 2012-09-29T21:28:50.253 回答