为什么这种快速排序会导致在几乎排序的列表和排序的列表上出现堆栈溢出？

对于随机数组，您可以划分出大量数据。
但是对于一个（几乎）排序的数组，您通常一次要划分一个元素。

因此，对于排序后的数组，您的堆栈大小最终将与该数组的大小相同，而对于一个随机数组，则更可能是该大小的对数。

因此，即使随机数组比几乎排序的数组大得多，较小的数组引发异常也就不足为奇了，而较大的数组则不会。

修改您的代码

在修复方面，如EJP所指出的那样，您应该首先进行较小的分区以限制堆栈的增长。但这本身不能解决问题，因为Java不支持尾部调用优化（嗯，据我所知，它对于实现是可选的）。

一个相当简单的解决方法是将您的函数放入while循环中，本质上是对尾调用优化进行硬编码。

为了更好地理解我的意思：

public static void quickSort(int[] arr, int highE, int lowE){    while (true)    {        if (lowE + 29 < highE)        { ... quickSort(arr, storeE - 1, lowE); // not doing this any more //quickSort(arr, highE, storeE + 1); // instead, simply set the parameters to their new values // highE = highE; lowE = storeE + 1;        }        else        { insertSort(arr, highE, lowE); return;        }    }}

好了，既然您已经有了基本的想法，这看起来会更好（在功能上等同于上面，更加简洁）：

public static void quickSort(int[] arr, int highE, int lowE){    while (lowE + 29 < highE)    {        ...        quickSort(arr, storeE - 1, lowE);        lowE = storeE + 1;    }    insertSort(arr, highE, lowE);}

当然，这实际上并不是先做较小的事情，但我将留给您去弄清楚（似乎您已经对如何做到这一点有了一个很清楚的想法）。

如何运作

对于一些虚构的价值…

您当前的代码执行此操作：（缩进指示该函数调用内发生了什么-因此增加缩进意味着递归）

quickSort(arr, 100, 0)   quickSort(arr, 49, 0)      quickSort(arr, 24, 0)         insertion sort      quickSort(arr, 49, 26)         insertion sort   quickSort(arr, 100, 51)      quickSort(arr, 76, 0)         insertion sort      quickSort(arr, 100, 74)         insertion sort

修改后的代码将执行以下操作：

quickSort(arr, 100, 0)   quickSort(arr, 49, 0)      quickSort(arr, 24, 0)         break out of the while loop         insertion sort   lowE = 26   break out of the while loop      insertion sortlowE = 51run another iteration of the while-loop    quickSort(arr, 76, 0)      break out of the while loop      insertion sortlowE = 74break out of the while loop   insertion sort

增加堆栈大小

不知道您是否考虑过这个问题，或者它是否可以与您的参数一起使用，但是您始终可以考虑使用

-Xss