Java implementation of Quicksort with Arraylist Troubleshoot

Question

我正在尝试使用 ArrayList 实现快速排序算法，但似乎无法使其正常工作。它在 sort（） 函数中的递归返回调用中给了我一个错误。请帮忙！

这是我得到的错误：线程"main"java.lang.StackOverflowError 中的异常

    public static void main(String[] args) {
    List<Integer> l = new ArrayList<Integer>();
    l.add(10); l.add(7); l.add(13); l.add(22); l.add(9);
    //l.get(2);

    System.out.println(sort(l));

}

public static List<Integer> sort(List<Integer> l) {
    if (l.size() <= 1) {
        return l;
    }
    int pivot = l.get(0);
    List<Integer> left = new ArrayList<Integer>();
    List<Integer> right = new ArrayList<Integer>();
    for (int i = 0; i < l.size(); i++) {
        if (l.get(i) < pivot) {
            left.add(l.get(i));
            //System.out.println(left);
        } else {
            right.add(l.get(i));
        }
    }
    return join(sort(left), sort(right), pivot);
}
public static List<Integer> join(List<Integer> left, List<Integer> right, int pivot) {
    List<Integer> l =  new ArrayList<Integer>();
    for (int i = 0; i < left.size(); i++) {
        l.add(left.get(i));
    }
    l.add(pivot);
    for (int i = l.size(); i < right.size(); i++) {
        l.add(right.get(i));
    }
    return l;
}

}

Answer 1

问题可能出在这里：

选择透视表为：

l.get(0);

然后再次添加透视：

int i = 0; i < l.size(); i++

当你从零开始！

因此，将其更改为从 1 开始：

int i = 1; i < l.size(); i++

编辑：另一个错误是你的join()方法——你必须从 0 开始，对于两个数组列表：

for (int i = 0; i < right.size(); i++) {
        l.add(right.get(i));
}

Answer 2

考虑一下如果选择最小的元素作为枢轴会发生什么。两个子列表中的一个将为空，另一个将包含整个原始列表，从而导致无限递归。