java - 使用递归实现插入排序时出现 Stackoverflow 错误

Question

public static void insertionSortRecursion(String a[], int first, int last) {
        if (first < last) {
            //sort all but last
            insertionSortRecursion(a, first, last - 1);
            insertInOrder(a[last], a, first, last -1);
        }
    }

    private static void insertInOrder(String element, String[] a, int first, int last) {
//        System.out.println(last - 1);
//        System.out.println(element);
//        System.out.println(a[last]);
        if (element.compareTo(a[last]) >= 0) {
            a[last + 1] = element;
        } else if(first < last) {
            a[last + 1] = a[last];
            insertInOrder(element, a, first, last - 1);
        } else {
            a[last + 1] = a[last];
            a[last] = element;
        }
    }

嘿伙计们， 我正在尝试使用递归实现插入排序，它在少量单词上运行良好，但在实现它后我遇到了 stackoverflow，因为我正在排序的文件大小有很多大约 10,000 个单词。请建议我应该做什么来消除错误。

These are the methods I am using for insertion sort using recursion and I am calling them in my constructor.

Answer 1

假设您的算法是正确的，请保持此函数不变。不要尝试修复它。一般来说，要摆脱堆栈溢出(同时保持递归)，有两种解决方案:

• 使用tail call optimization
• 增加堆栈大小

但是让我们坐下来假设这段代码不仅仅是编程练习。任何其他必须阅读的人都会认为:

1. 为什么他使用插入排序？
2. 为什么他重新实现插入排序？
3. 必须是递归吗？我的主!!
4. 他为什么要浪费时间去寻找尾部调用插入算法？或者
5. 他只是为了运行他的方法而增加了堆栈大小吗？
6. 很好。现在我们有 1000,000 个项目需要排序，但程序一直崩溃。

结论，他们会立即删除你的代码并使用Collections.sort() 。正如我所说，如果您正在做编程练习，那么很好，您的递归插入对工作进行排序直到某个时刻。继续前进。