为什么在 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);
}
我基本上是在尝试在 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);
}