使用快速排序算法排序7个数字时出现StackOverflowError问题排查

错误原因分析 #

你的代码出现StackOverflowError的核心问题是分区逻辑错误导致无限递归：

• 在遍历数组分配元素到left_arr和right_arr时，你没有排除选中的pivot元素，而是将pivot也加入了left_arr（因为element <= pivot的条件包含了pivot本身）。
• 当随机选中的pivot是当前数组的最大值时，所有元素（包括pivot）都会被放入left_arr，此时left_arr的大小和原数组完全一致。递归调用quick_sort(left_arr)时，永远无法触发arr.size() <= 1的终止条件，递归会无限进行，最终耗尽栈空间引发溢出。

以你的输入{6,15,32,643,6543,534232,232}为例，当随机选中最大值534232作为pivot时，left_arr会包含全部7个元素，递归陷入死循环。

修复方案 #

修改分区逻辑，遍历数组时跳过pivot元素，确保left_arr和right_arr的大小严格小于原数组：

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);
            }
        }
        // 添加输出语句查看排序结果
        System.out.println("排序后数组：" + 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++) {
            // 跳过pivot元素，不加入左右数组
            if (i == pivot_index) {
                continue;
            }
            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;
    }
}

额外说明 #

• 修复后的代码中，我们在遍历数组时通过i == pivot_index跳过了pivot元素，保证每次递归处理的子数组规模都会缩小，最终触发终止条件。
• 同时在main方法中添加了输出语句，方便查看排序后的结果。

内容的提问来源于stack exchange，提问作者ege.exe