1

私はこれに慣れていませんが、できるだけ早く学ぼうとしています。スタックを使用してマージソートを実装しようとしています。私のコードにはエラーはありませんが、コードを実行すると範囲外の配列エラーが発生します。どんな助けでも大歓迎です。

私が想像しているように、マージソート関数はスタックを2つ(左と右)に分割し、それらをソートしてマージするマージ関数を呼び出します。

public static void main(String[] args) {
    Stack<Integer> myStack = new Stack<>();
    Random r = new Random();
    int size= 30;
    for (int i = 0; i < size;i++)
    {
        myStack.add(r.nextInt(200));
        System.out.println(myStack.peek());
    }
    MergeSort(myStack);
    System.out.println("-------");
    for (int i = 0; i < size; i++)
    {
        System.out.println(myStack.pop());
    }

}
private static Stack<Integer> MergeSort(Stack<Integer> input)
{
    Stack<Integer> Result;
    Stack<Integer> Left = new Stack<>();
    Stack<Integer> Right = new Stack<>();
    if (input.size() <= 1)
    {
        return input;
    }
    int midpoint = input.size() / 2;
    for (int i = 0; i < midpoint; i++)
    {
        Left.add(input.get(i));
    }
    for (int i = midpoint; i < input.size(); i++)
    {
        Right.add(input.get(i));
    }
    Left = MergeSort(Left);
    Right = MergeSort(Right);
    Result = Merge(Left, Right);

    return Result;
}

private static Stack<Integer> Merge(Stack<Integer> Left, Stack<Integer> Right)
{
    Stack<Integer> Result = new Stack<>();
    while (Left.size() > 0 && Right.size()>0)
    {
        if (Left.get(0) < Right.get(0))
        {
            Result.add(Left.get(0));
            Left.removeElementAt(0);
        }
        else
        {
            Result.add(Right.get(0));
            Right.removeElementAt(0);
        }
    }
    while (Left.size()> 0)
    {
     Result.add(Left.get(0));   
     Left.removeElementAt(0);
    }
    while (Right.size() > 0)
    {
      Result.add(Right.get(0));
      Right.removeElementAt(0);                    
    }
    return Result;
}

これはコンソール出力です。

実行: 10 73 82 74 4 40 86 119 102 83 122 5 164 50 25 117 57 153 95 155 70 115 61 162 55 190 35 171 150

44

44 150 171 35 190 55 162 61 115 70 155 95 153 57 117 25 50 164 5 122 83 102 119 86 40 4 74 82 73 10 ビルド成功 (合計時間: 0 秒)

4

1 に答える 1

2

関数 Merge: の代わりにif (Left.get(0) < Right.get(0)) 書いたResult.get(Left.get(0))Result.add(Left.get(0))

別のこと：ソートされたスタックを印刷するときのメイン関数で：本当に使いたいですか.peek()（スタックの一番上だけを見ます）？

于 2013-10-22T11:58:44.850 に答える