java - 使用我的快速排序算法对 7 个数字的列表进行排序时出现 StackOverflowError

Question

对于以下快速排序算法:

import java.util.Scanner;
import java.util.ArrayList;
public class quick_sort_demo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> my_arr = new ArrayList<Integer>();
        while (true) {
            System.out.println("Enter input value. '-1' to exit the adding process. ");
            int val = sc.nextInt();
            sc.nextLine();
            if (val == -1) {
                break;
            } else {
                my_arr.add(val);
            }
        }
        quick_sort(my_arr);
    }
    public static ArrayList<Integer> quick_sort(ArrayList<Integer> arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        int pivot_index = (int) (Math.random() * arr.size());
        int pivot = arr.get(pivot_index);
        ArrayList<Integer> left_arr = new ArrayList<Integer>();
        ArrayList<Integer> right_arr = new ArrayList<Integer>();
        for (int i = 0; i < arr.size(); i++) {
            int element = arr.get(i);
            if (element > pivot) {
                right_arr.add(element);
            } else {
                left_arr.add(element);
            }
        }
        left_arr = quick_sort(left_arr);
        right_arr = quick_sort(right_arr);
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.addAll(left_arr);
        result.add(pivot);
        result.addAll(right_arr);
        return result;
    }
}

我反复收到此错误:

Exception in thread "main" java.lang.StackOverflowError
        at java.base/java.util.Random.next(Random.java:209)
        at java.base/java.util.Random.nextDouble(Random.java:463)
        at java.base/java.lang.Math.random(Math.java:865)
        at quick_sort_demo.quick_sort(quick_sort_demo.java:23)
        at quick_sort_demo.quick_sort(quick_sort_demo.java:35)

我对该程序的具体输入如下:{6,15,32,643,6543,534232,232,-1}

我尝试询问 CHATGPT，但对于我遇到的具体错误，我无法获得有用的答案。我不明白为什么我会收到 stackoverflow 错误，因为递归方法应该毫无问题地调用自身，直到 'arr.size()' 返回 <= 1 的内容。有人可以解释我做错了什么吗？我的算法是否错误？为什么会出现递归错误？

Answer 1

代码运行良好

好吧几乎很好，您的代码中有一个错误

left_arr = quick_sort(left_arr);
right_arr = quick_sort(right_arr);
ArrayList<Integer> result = new ArrayList<Integer>();
result.addAll(left_arr);
result.add(pivot); //BUG HERE
result.addAll(right_arr);

当您拆分左/右时，您已经将 pivot 添加到 left_arr 中 - 因此无需添加两次，因为

if (element > pivot) {
    right_arr.add(element);
} else {
    left_arr.add(element); //pivot itself is NOT bigger than pivot and will be added here
}

或者，您可以从列表中删除枢轴:int hub = arr.remove(pivot_index);

关于java.lang.StackOverflowError

嗯 - 你的代码在我的机器上运行良好，所以我想你必须正确设置你的计算机 - 请参阅 this answer了解更多详细信息(抱歉仅提供链接答案)