时间戳

首页 > 解决方案 > 为什么在 java 中递归实现合并排序时会发生这个 Stackoverflow 异常？

java - 为什么在 java 中递归实现合并排序时会发生这个 Stackoverflow 异常？

问题描述

我基本上是在尝试在 Java 中实现合并排序。为此，我创建了一个名为 Array 的类，它有一个整数数组 a[]。该类还有一个名为 slice(int left, int right) 的方法，它产生数组的切片并返回对象。此后，有一个 sort() 方法递归调用自身并分解数组并在最后返回一个 Array 对象。

import java.util.*;
class Array
{
    int a[];

    public Array()
    {
        a = null;
    }

    public Array(int x)
    {
        a = new int[x];
    }  

    public void input()
    {
        Scanner sc = new Scanner(System.in);
        for(int i = 0; i < a.length; i++)
        {
            System.out.print("Enter a No. = ");
            a[i] = sc.nextInt(); 
        }
    }

    public void display()
    {
        for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + "\t");
        System.out.println();
    }

    public Array slice(int left, int right)
    {
        Array ob = new Array(left + right + 1);
        for(int i = left; i <= right; i++)
            ob.a[i] = this.a[i];
        return ob;
    }

    public static Array merge(Array A, Array B)
    {
        Array C = new Array(A.a.length + B.a.length);
        int i, j, k;
        i = j = k = 0;

        while(i < A.a.length && j < B.a.length)
        {
            if(A.a[i] < B.a[j])
                C.a[k++] = A.a[i++];
            else if(A.a[i] > B.a[j])
                C.a[k++] = B.a[j++];
            else
            {
                C.a[k++] = A.a[i++]; j++;
            }
        }

        while(i < A.a.length)
            C.a[k++] = A.a[i++];

        while(j < B.a.length)
            C.a[k++] = B.a[j++];

        return C;
    }

    public Array sort()
    {
        if(this.a.length == 1)
            return this;
        else
        {
            return merge(this.slice(0, (this.a.length - 1) / 2).sort(), this.slice(1 + (this.a.length - 1) / 2, this.a.length - 1).sort());
        }
    }

    public static void main()
    {        
        Array x;
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the No. of Elements = ");
        Array ob = new Array(sc.nextInt());
        ob.input();
        System.out.println("\n ORIGINAL ARRAY");
        ob.display();
        System.out.println("\n SORTED ARRAY");
        x = ob.sort();
        x.display();
    }
}

假设如果我有一个对象 A，它有一个整数数组 a[]，那么在调用 A.sort() 时必须返回一个对象，其中所有数组元素都将按升序排序。

我得到的错误：java.lang.StackOverflowError: null

标签： javarecursionstack-overflowmergesort

解决方案

堆栈是有限大小的内存区域。它通常不是那么大。当你调用一个递归函数时，每个递归调用都放在堆栈上。当递归完成时，堆栈上的调用被弹出并执行。

问题是如果你的数组很大，并且递归深入（许多调用），你可能会用完堆栈上的空间来放置下一个递归调用。这是堆栈溢出。

我曾经在大学犯过完全相同的错误。:)

要修复您的程序，您可以：

  • 增加堆栈大小（这是一个 hack，你可以进行多少递归调用仍然有限制，现在只是更高了）
  • 减少每次调用的内存使用（仍然是一种 hack，可能也不是很有效，除非您将大量数据存储在局部变量中）
  • 迭代地实现您的合并排序，以便您一次只处理小块数据，而不是先将它们全部放在堆栈上，然后在最后处理它。

每个递归算法都可以通过迭代（循环）来实现。

推荐阅读