递归插入排序处理5000对象时仅遇StackOverflow异常，如何解决？

为什么会出现这个问题？ #

兄弟，这事儿本质就是递归深度把调用栈给撑爆了！递归版插入排序在最坏场景（比如你的5000个对象完全逆序）下，递归深度会达到n-1也就是4999层。但JVM或者.NET CLR的默认调用栈空间是有限的——一般默认栈大小对应的最大递归深度就在几千层，你看到position到4719就报错，刚好卡在这个阈值上。每一次递归调用都会在栈上创建一个栈帧（存局部变量、返回地址这些信息），栈空间被占满后，自然就抛出StackOverflowException了。

最靠谱的解决方案：换成迭代版插入排序 #

递归虽然写起来优雅，但插入排序这种算法天生更适合用迭代实现，完全没有栈深度的限制。给你写个针对对象整数属性排序的迭代版示例（假设你的对象类叫DataObject，整数属性是intValue）：

public void iterativeInsertionSort(ArrayList<DataObject> list) {
    for (int i = 1; i < list.size(); i++) {
        DataObject key = list.get(i);
        int j = i - 1;
        
        // 把比key大的元素往后挪位置
        while (j >= 0 && list.get(j).getIntValue() > key.getIntValue()) {
            list.set(j + 1, list.get(j));
            j--;
        }
        // 把key插入到正确位置
        list.set(j + 1, key);
    }
}

这个版本不管你排1万还是10万个对象，都不会出现栈溢出的问题，而且因为少了递归调用的开销，实际运行效率甚至比递归版还快一点。

如果你非要保留递归（不推荐） #

如果因为某些特殊原因必须用递归，那只能通过调整虚拟机的栈大小参数临时解决：

• Java环境：启动程序时加上-Xss4m（把栈大小设置为4MB，默认一般是1-2MB），这样能支持更深的递归深度。但注意，这个参数是虚拟机级别的，换个环境可能要重新设置，而且如果数据量再变大（比如10万），还是会爆栈。
• .NET环境：可以在项目属性里调整“堆栈大小”，或者用editbin工具修改可执行文件的堆栈大小，但同样是治标不治本的办法。

另外提一句：有些语言支持尾递归优化，但Java和C#目前都没有完善的尾递归优化支持，就算把递归改成尾递归形式也解决不了问题。

内容的提问来源于stack exchange，提问作者pops