前几天我看到一个演讲，演讲者使用了 McIlroy 的论文A Killer Adversary for Quicksort中概述的技术，为将触发 O(n 2 ) 行为Arrays.sort的原始类型生成输入。该序列导致枢轴选择始终仅将数组大小减少一个常量，这导致 Java函数导致堆栈溢出。Arrays.sort
根据JDK的源文件，Arrays.sort1快速排序实现函数没有防止堆栈溢出的保护。通过让排序例程不触发两个递归调用，而是使用 while 循环将当前堆栈帧重用于较大的子数组并且只递归一次（在较小的子数组上），总是可以使快速排序永远不会堆栈溢出。这导致最小的性能下降，并且不可能导致任何合理大小的输入的堆栈溢出，因为堆栈深度永远不会超过大小为 n 的输入上的 O(log n) 堆栈帧。作者也可以使用introsort算法，当快速排序递归深度超过某个限制时，它会修改快速排序以切换到最坏情况的 O(n log n) 排序算法，以防止这种情况发生。
作者有什么理由Arrays.sort不选择这样做吗？内置排序算法可能导致堆栈溢出似乎是一个严重的问题，因为它可以通过触发重复的堆栈溢出来对这样的系统发起 DoS 攻击。