简单递归合并排序堆栈java.lang.StackOverflowError
简单递归合并排序堆栈java.lang.StackOverflowError
提问于 2017-04-03 01:17:22
我有一个简单的递归合并排序，我只是尝试对实现可比较的整数数组列表进行排序。我不明白为什么我会得到一个错误，当它运行时，它会打印出我创建的随机整数的ArrayList，然后它打印出来。
还没有错误
还没有错误
线程"main“java.lang.StackOverflowError中的异常
然后它会重复
在MergeTemplate.rMerge(MergeTemplate.java:38)
很多次直到它终于说
过程完成
import java.util.*;
public class MergeTemplate{
private ArrayList <Comparable> temp1=new <Comparable> ArrayList();
int num;
Random ar=new Random();
public MergeTemplate(){
num=25;
}
public MergeTemplate(int n){
num=n;
}
public ArrayList <Comparable> fillArray(){
ArrayList <Comparable> ar1=new <Comparable> ArrayList();
for(int i=0;i<num; i++)
ar1.add(ar.nextInt(11));
screenOutput(ar1);
return ar1;
}
public void screenOutput(){
for(Comparable x: temp1)
System.out.print(x+ " ");
System.out.println();
}
public void screenOutput(ArrayList <Comparable> temp){
for(Comparable x: temp)
System.out.print(x+ " ");
System.out.println();
}
public void rMerge(ArrayList <Comparable> rList){
rMerge(rList, 0, rList.size()-1);
}
public void rMerge(ArrayList <Comparable> rList, int first, int last){
if (first-last==0){
System.out.println("no error yet");
}
else{
rMerge(rList, first, last/2);
rMerge(rList, last/2 + 1, last);
merge(rList, first, last);
}
}
public void merge(ArrayList <Comparable> a, int first, int last){
Comparable placeHolder;
if(a.get(first).compareTo(a.get(last))>1){
placeHolder=a.get(first);
a.set(first, a.get(last));
a.set(last, placeHolder);
}
}
}
public class Tester {
public static void main(String[] args) {
MergeTemplate one=new MergeTemplate(8);
one.rMerge(one.fillArray());
}
}Stack Overflow用户
回答已采纳
发布于 2017-04-03 06:12:57
您还需要一个键来表示拆分点，以适当地划分元素。合并()方法还需要重新实现，以迭代所有目标元素。包含rMerge()方法实现的完整代码，添加一个名为mid的键和merge()方法的实现，如下所示。
import java.util.ArrayList;
import java.util.Random;
public class MergeTemplate {
private Random random = new Random();
private ArrayList<Comparable> temp1 = new ArrayList<>();
private int num;
public MergeTemplate() {
this.num = 25;
}
public MergeTemplate(int num) {
this.num = num;
}
public ArrayList<Comparable> fillArray() {
ArrayList<Comparable> ar1 = new ArrayList<>();
for (int i = 0; i < num; i++) {
ar1.add(random.nextInt(11));
}
screenOutput(ar1);
return ar1;
}
public void screeOutput() {
for (Comparable x : temp1) {
System.out.println(x + " ");
}
System.out.println();
}
public void screenOutput(ArrayList<Comparable> temp) {
for (Comparable x : temp) {
System.out.println(x + " ");
}
System.out.println();
}
public void rMerge(ArrayList<Comparable> rList) {
rMerge(rList, 0, rList.size() - 1);
}
public void rMerge(ArrayList<Comparable> rList, int first, int last) {
int mid = 0;
if (first >= last) {
System.out.println("no error yet");
} else {
mid = (first + last) / 2;
rMerge(rList, first, mid);
rMerge(rList, mid + 1, last);
merge(rList, first, mid, last);
}
}
public void merge(ArrayList<Comparable> a, int first, int mid, int last) {
int i, j, k, m;
i = first;
j = mid + 1;
k = first;
ArrayList<Comparable> tempList = new ArrayList<>();
// compare two divided parts
while (i <= mid && j <= last) {
if (a.get(i).compareTo(a.get(j)) < 1) {
tempList.add(a.get(i));
i++;
} else {
tempList.add(a.get(j));
j++;
}
k++;
}
if (i > mid) {
for (m = j; m <= last; m++) {
tempList.add(a.get(m));
k++;
}
} else {
for (m = i; m <= mid; m++) {
tempList.add(a.get(m));
k++;
}
}
for (i = 0, j = first; i < tempList.size(); i++, j++) {
a.set(j, tempList.get(i));
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43175257
复制相关文章
相似问题
腾讯云开发者
