java - 调用合并排序方法时出现堆栈溢出错误

Question

我一直在做这个问题:

我创建了一个采用随机数的文件，并将这些数字存储在 SinglyLinkedList 数据结构中，我想执行 mergeSort 对这些随机数进行排序。

对于较小的输入，一切正常。但是当我插入 10000 个数字时，它开始在 9800 左右出现“stack_overflow”错误(仅在显示数字时)，当我插入 10 万个数字时 - 它在 99700 个数字之前运行良好，但随后开始显示其余数字的错误.

那么这个错误背后的具体原因是什么(我知道这是因为它在递归函数中丢失了)请在这里帮助我，我无法跟踪导致此错误的问题。

这是我的主要方法代码:

FileReader fr = new FileReader("C://my_folder//file_List.txt");
    BufferedReader br = new BufferedReader(fr);

    LinkedListNode lln = new LinkedListNode();

    String str;

    while((str=br.readLine())!=null){

        /* This insertAtEnd appends the number to the SinglyLinkedList*/
        lln.insertAtEnd(Integer.parseInt(str));
        System.out.println(" "+str);
    }
     /*This method displays the elements of a LinkedList*/
    Node res = lln.traverse();
    System.out.println("\n");
    mergeSortLinkedList ms = new mergeSortLinkedList();
    ms.sort(res);

这是我的排序方法代码:

public void sort(Node n){
    Node tmp = n;

    MergeSort(tmp);
}

Node a;
Node b;

public void MergeSort(Node headRef){


    Node head1 = headRef;

    if(head1 == null || head1.next == null){
        return;
    } 
    System.out.print("hi..");
    Node Euler = splitList(head1);
    printList(Euler);

}

/* perform merge sort on the linked list */

public Node splitList(Node head1){

    Node slow;
    Node fast;
    Node left, right;


    if(head1 == null || head1.next == null){
        left  = head1;
        right = null;

        return head1;
    }
    else{

        slow = head1;
        fast = head1.next;


        while(fast!=null){

            fast = fast.next;

            if(fast!=null){

                slow = slow.next;
                fast = fast.next;
            }
        }

        left = head1;
        right = slow.next;

        slow.next = null;


    }



    return SortedMerge(splitList(left),splitList(right));
}

/* merge the lists.. */
public Node SortedMerge(Node a, Node b){

    Node result = null;

    if(a == null){
        return b;
    }
    else if( b == null){
        return a;
    }

    if(a.data < b.data){
        result = a;
        result.next = SortedMerge(a.next, b);//getting error at this line
    }
    else{
        result = b;
        result.next = SortedMerge(a,b.next);//getting error at this line
    }

    return result;
}


public void printList(Node Euler){
    System.out.println("\nPrinting sorted elements");
    Node Ref = Euler;
    int count = 0;

     while(Ref!=null){
        count++;
        System.out.println(count+"-"+Ref.data);
        Ref = Ref.next;
    }
}

Answer 1

您是否考虑过使用 JDK 中的 Collections.sort() 来进行合并排序？ Java 8 还有一个并行排序，它执行并行合并排序。