简单递归归并排序 Stack java.lang.StackOverflowError

Question

我有一个简单的递归合并排序，我只是尝试对实现 Comparable 的整数数组列表进行排序。我不明白为什么会出现错误，当它运行时会打印出我创建的随机整数的 ArrayList，然后打印

还没有错误

线程异常 "main" java.lang.WhosebugError

然后重复

在 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());
    }
}

Answer 1

您的 merge 方法有一个错误，它没有遍历所有列表来验证订单结果。

Answer 2

我认为您应该将 (last < first) 添加到您的条件中：

if (first-last==0 && last < first){
   System.out.println("no error yet");
}

Answer 3

您的错误发生在

rMerge(rList, first, last/2);

当first等于2 last小于2时，实际上last等于0，一直在调用自己。您需要检查是否有 1 个元素。

Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted)

Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

来自维基百科。

Answer 4

您还需要一个键来表示分割点，以便适当地分割元素。 merge()方法也需要重新实现，遍历所有目标元素。包含 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 java.lang.StackOverflowError

simple recursive merge sort Stack java.lang.StackOverflowError

java

sorting

recursion

mergesort