快速排序Java的StackOverFlowError

Question

我正在测试我编写的快速排序代码，但我不确定为什么我会得到

错误：

Exception in thread "main" java.lang.StackOverflowError
    at java.util.ArrayList$Itr.<init>(ArrayList.java:820)
    at java.util.ArrayList.iterator(ArrayList.java:814)
    at practice.Quicksort.quicksort(Quicksort.java:15)
    at practice.Quicksort.quicksort(Quicksort.java:25)
    at practice.Quicksort.quicksort(Quicksort.java:25)
    at practice.Quicksort.quicksort(Quicksort.java:25)

其中第15行为：

for (int n : arr) {

第25行为：

more = quicksort(more);

代码：

public class Quicksort {
    public static List<Integer> quicksort(List<Integer> arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        List<Integer> less = new ArrayList<Integer>();
        List<Integer> more = new ArrayList<Integer>();
        int pivotIndex = arr.size() / 2;
        int pivot = arr.get(pivotIndex);
        for (int n : arr) {
            if (n < pivot) {
                less.add(n);
            }
            else {
                more.add(n);
            }
        }
        // recursively sort
        less = quicksort(less);
        more = quicksort(more);
        // concatenate all
        less.add(pivot);
        less.addAll(more);
        return less;
    }
    public static void main(String[] args) {
        List<Integer> test = new ArrayList<Integer>();
        int[] arr = {2,4,1,4,5,2,-10,3,0,33,23};
        for (int c : arr) {
            test.add(c);
        }
        System.out.println(quicksort(test));
    }
}

Answer 1

您的代码有一个基本缺陷，这增加了名为more的列表在随后的两次迭代中相同的可能性。可能的问题在于代码的以下部分：

 int pivotIndex = arr.size() / 2;
    int pivot = arr.get(pivotIndex);
    for (int n : arr) {
        if (n < pivot) {
            less.add(n);
        }
        else {
            more.add(n);
        }
    }

不要在more或less列表中添加枢轴。此外，您可以在博客

Answer 2

列表more不应包含枢轴。如果你运行了more，那么就有可能与传入的列表完全相同，并且你会得到一个无限递归循环，直到程序耗尽堆栈空间。

一种常见的技术是用列表中的第一个项目交换枢轴，然后从第二个项目开始创建less和more的列表。