我的快速排序得到了 java.lang.StackOverflowError

Question

这基本上是一个使用数组列表的简单快速排序，但我找不到陷入无休止递归的原因。最后我得到的唯一结果是堆栈溢出错误。

 List<Integer> quicksort(List<Integer> toSort){

        if(toSort.size() > 1){
            List<Integer> left = new ArrayList<>();
            List<Integer> right = new ArrayList<>();
            for(int i=0;i<toSort.size();i++){
                if(toSort.get(i) < toSort.get(toSort.size()/2))
                    left.add(toSort.get(i));
                else
                    right.add(toSort.get(i));
            }

            toSort = quicksort(left);
            toSort.addAll(quicksort(right));
            return toSort;

        }else
            return toSort;
    }

Answer 1

假设您的 toSort List 中有 2 个元素（首次调用时），[2, 1].

首先，您创建两个 List，left 和 right。

然后根据 'pivot' 填充这些。您使用 toSort.get(toSort.size() / 2); 作为基准。 toSort.size() = 2，所以在这种情况下 toSort.get(1) = 1（来自上面的 List）。

然后根据元素是否小于将元素添加到不同的 List。所以这意味着你最终得到（在 for 循环完成后）：

left = [], right = [2, 1].

然后您再次对这两个 List 调用 quickSort。第二次，当调用 toSort.addAll(quicksort(right)); 时，您回到了第一次调用时的 exact 状态，因此上述情况再次发生。最终这会导致堆栈溢出。

你的问题是你错误地实现了快速排序算法。我建议您查看基于您的实现的快速排序算法的伪代码，并一次完成它的较小步骤（然后在您确定您误解的最小步骤时寻求帮助）。

我的快速排序得到了 java.lang.StackOverflowError

I'm getting a java.lang.StackOverflowError in my quicksort

java

stack-overflow

recursion

quicksort