0 
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.
4

2 回答 2

1

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

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

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

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

于 2013-02-05T09:04:09.957 回答
0

默认情况下，Java 无法处理那么深（10000）的递归深度。考虑以下过于简化的示例仍然会引发 StackOverflowError。

static void test(int i)
{
   if (i == 0) return;
   test(i-1);
}

public static void main(String[] args)
{
   test(10000);
}

您必须指定命令行参数来实现这一点（-Xss并且可能-Xmx分配更多内存）。

-Xmx1000m -Xss10000000我使用（虽然花了一段时间）成功地运行了你的算法，用于一个大小为 100000 的数组。

我认为您使用递归而不是简单的双 for 循环是有原因的。

于 2013-02-05T08:44:32.443 回答