java - 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 列表中添加数据透视表。此外，您还可以了解如何选择变体here on the blog