Question

如何解决java中混合快速排序法栈溢出（stack overflow）

混合快速排序法中breakpoint如果小于或等于数组长度时，就用插入排序法

public static void hybridQuickSort(int[] a, int start, int end, int breakpoint )
{
intPair pivotPosn;
pivotPosn = new intPair(0,0);

if((end-start)<=breakpoint)
{
insertionSort(a,start,end);
}
else
{
choosePivot(a,start,end);
pivotPosn = partitionWithDuplicates(a, start, end);
hybridQuickSort(a,start,pivotPosn.getEqualsStart(),breakpoint);
hybridQuickSort(a,pivotPosn.getBigsStart(),end,breakpoint);
}
}
这只是部分代码，要解释的是partitionWithDuplicates是分成三部分，分别是小与，等于与大于三部分，而不是普通的小于与大于。inpair是新建的一个类用来储存相等部分开始下标与大于部分开始下标。重复调用小于与大于部分就能完成数组排序。
问题是：长度是1000的数组也能完成排序，但是是当数组长度过大时，比如是20000，出现了stack overflow（栈溢出）。这个问题应该如何解决？

Answer 1

1. 应该是您的递归算法调用的层级太多导致的。优化下算法，让调用层级减低才行。
2. 这种情况自己维护个栈序列，用循环的方式来处理应该就可以了。
例如可以是：
1. （start,end）入栈
2. 栈是否为空，若为空则退出
3. 弹出栈定元素，如果start-end<breakpoint使用插入排序，完成后回到2。
否则对[start，end]序列进行划分，将小于和大于choosePivot(a,start,end);的区间入栈
（minstart,minend), (maxstart, maxend)
4. 重复2，3，直到栈为空