Stack_Overflow_error 在调用 mergeSort 方法时

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 还有一个并行排序的 parallelSort。

Answer 2

我想给你更新。

通过更改堆栈大小，我确实能够运行我的程序正常运行。它造成的原因 Exception in thread "main" java.lang.WhosebugError 是因为它超出了堆栈大小。

所以我四处搜索并得到了这个解决方案。

转到项目属性 - 在运行中，转到 VM 选项并将其放入参数 -Xss100m 中以使其成为运行！现在它能够对超过 100 万个数字进行排序 :D

欢迎提出其他建议/解决方案。

Stack_Overflow_error 在调用 mergeSort 方法时

Stack_Overflow_error while calling mergeSort method

java

stack-overflow

mergesort