JAVA快排退化后出现StackOverflowError问题
来源：3-7 双路快速排序法
许昭宇
2021-03-21
使用单路快排产生近乎有序的数组，快排退化，大数据量情况下出现了StackOverflow问题；
使用双路快排，比如：
while (i <= r && arr[i] <= v) {
i++;
}
while (j >= l + 1 && arr[j] >= v) {
j–;
}
（多了=，使用了<=v 和 >=v，此时也出现了退化），大数据量情况下出现了StackOverflow，理论上就算不加=，在极端条件下，也可能出现StackOverflow；
可是我们使用JAVA 内置的排序方法（也是基于快排）貌似没有此类异常。
请问JAVA内置排序会出现此异常吗？
如果不会的话，它做了什么优化？
1回答
-
就是因为对于有序的数组，pivot 每次都分布在数组的一端。这样做不但导致我们整个算法是 O(n^2) 的，同时递归深度变成了 n，如果 n 很大，就会 stackoverflow。
课程之前使用随机标定点，应该已经解决了有序数组的问题。但是对于大量重复元素，仍然会退化。双路快排在此基础上解决了大量重复元素的问题。如果你的代码现在还会退化，说明你的代码有问题，请使用课程这一小节的代码在你的环境下测试一下试试看？https://git.imooc.com/coding-71/coding-71/src/master/03-Sorting-Advance/Course%20Code%20%28Java%29/07-Quick-Sort-Deal-With-Identical-Keys/src/bobo/algo/QuickSort2Ways.java
对于这一小节的双路快排，不能加 = 是核心。不加等号不会退化。你可以在不加等号的情况下，构造一下你说的“极端条件”试试看？
这里的问答，在说明为什么不能加 = 号。你也可以具体实验一下，思考一下为什么 = 会在有大量重复元素的情况下造成退化。http://coding.imooc.com/learn/questiondetail/4920.html
Java 内部的快排类似三路快排的思想（是类似，不是完全）。三路快排在课程后续就会介绍。但是，一个正确实现的双路快排，应该已经不会退化了。
继续加油！：）
022021-03-22
相似问题