为什么在 java 中递归实现合并排序时会出现此 Stackoverflow 异常?

Why this Stackoverflow exception is occuring while implementing merge sort in java recursively?

我基本上是在尝试在 Java 中实现合并排序。为此,我创建了一个名为 Array 的 class,它有一个整数数组 a[]。 class 还有一个名为 slice(int left, int right) 的方法,它生成数组切片和 returns 对象。此后,有一个 sort() 方法递归调用自身并分解数组,最后 returns 一个 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() 时必须 return 一个对象,其中所有数组元素将在其中排序升序。

我遇到的错误:java.lang.WhosebugError:null

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

问题是,如果您的数组很大,并且递归深入(多次调用),您可能 运行 超出堆栈中的 space 以放置下一个递归调用。这是堆栈溢出。

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

要修复您的程序,您可以:

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

每个递归算法都可以用迭代(一个循环)来实现。

首先,你的切片应该这样实现。我怀疑这是主要问题。按照您的方式,切片不会变小,因此递归永远不会触底。

public Array slice(int left, int right)
{
    int length = right - left; // this is the proper length
    Array ob = new Array(length);
    for(int i = 0; i < length; i++)
        ob.a[i] = this.a[i + left];
    return ob;
}

其次,合并应该是这样的。

public static Array merge(Array A, Array B)
{
    Array C = new Array(A.a.length + B.a.length);
    int i = 0, j = 0, 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++];
            C.a[k++] = B.a[j++]; // this preserves duplicates
        }
    }

    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(a.length < 2)
        return this;

    int half = a.length / 2;
    Array left = slice(0, half).sort();
    Array right = slice(half, a.length).sort();
    return merge(left, right);
}