我在quicksort中得到一个java.lang.StackOverflowError。

Question

这是一个基本的使用数组列表的简单quicksort，但我找不到为什么我会陷入无休止的递归。最后，我得到的唯一结果是堆栈溢出错误。

 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

考虑到你有2个元素在你的 toSort List (当它第一次被调用)。[2, 1].

首先，你创建两个 Lists, left 和 right.

然后你根据 "pivot "来填充这些。 您可以使用 toSort.get(toSort.size() / 2); 作为中枢。 toSort.size() ＝2，所以 toSort.get(1) ＝1(自 List 以上）在这种情况下。

然后将这些元素添加到不同的 List根据它们是否是 少于 这个值。 所以，这意味着你最终会得到（在完成了 for 循环已完成）。)

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

然后你再打电话 quickSort 在这两方面 List的再次。 第二次，当调用 toSort.addAll(quicksort(right)); 你回来了 确切 状态作为你的第一次调用，于是上面的事情又发生了。 最终导致堆栈溢出。

---

你的问题在于你错误地实现了quicksort算法。 我建议你回顾一下你的实现所基于的quicksort算法的伪代码，然后每次通过较小的步骤来解决这个问题（当你确定你所误解的最小步骤时，再寻求帮助）。