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

在你的功能合并： if (Left.get(0) < Right.get(0)) 你写Result.get(Left.get(0))而不是Result.add(Left.get(0))

另一件事：在打印排序堆栈时的主函数中：您真的要使用.peek()（它只查看堆栈顶部）吗？

于 2013-10-22T11:58:44.850 回答