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になります。これにより、Javaでは4であると推測されるmid = 9/2が生成されるため、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 に答える