Java ForkJoin快速排序遇全相等元素时StackOverflow问题求助

问题原因 #

当数组所有元素相等时，你的并行快排实现会触发StackOverflowError，核心原因有两点：

1. 分区策略缺陷：当前partition函数在所有元素等于pivot时，返回的分界点是当前区间的起始位置，导致每次递归处理的右区间仅比原区间少1个元素。当区间长度大于阈值（50000）时，compute方法会持续递归调用自身，递归深度达到O(n)，远超JVM栈的默认容量。
2. 递归未做尾优化：串行实现通过while循环对较大分区做了尾递归优化，将栈深度控制在O(logn)；但并行实现的compute方法直接递归处理右分区，没有类似优化，极端场景下栈会被撑爆。

修复方案 #

核心改进思路 #

采用三路分区策略（将数组划分为小于、等于、大于pivot的三部分），彻底解决全相等元素场景下的分区低效问题；同时优化并行递归逻辑，控制栈深度，另外修正static数组带来的线程安全隐患。

修复后的并行实现代码 #

import java.util.Comparator;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class QuickSortMultiThreading extends RecursiveAction {
    private final int threshold = 50000;
    private final Apartment[] arr; // 改为成员变量，移除static修饰
    private int start, end;
    private static final Comparator<Apartment> comparator = new Apartment.ApartmentComparator();

    public QuickSortMultiThreading(Apartment[] arr, int start, int end) {
        this.arr = arr;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        if (start >= end) {
            return;
        }
        if (end - start <= threshold) {
            quickSort(start, end);
        } else {
            // 三路分区，返回[小于pivot的最后索引, 大于pivot的起始索引]
            int[] bounds = threeWayPartition(start, end);
            int leftEnd = bounds[0];
            int rightStart = bounds[1];
            
            QuickSortMultiThreading leftTask = new QuickSortMultiThreading(arr, start, leftEnd);
            QuickSortMultiThreading rightTask = new QuickSortMultiThreading(arr, rightStart, end);
            
            // 优先处理较小分区，减少递归栈深度
            if (leftEnd - start < end - rightStart) {
                leftTask.fork();
                rightTask.compute();
                leftTask.join();
            } else {
                rightTask.fork();
                leftTask.compute();
                rightTask.join();
            }
        }
    }

    // 三路分区实现
    private int[] threeWayPartition(int low, int high) {
        Apartment pivot = arr[high];
        int i = low;
        int lt = low; // 小于pivot区域的右边界
        int gt = high; // 大于pivot区域的左边界

        while (i <= gt) {
            int cmp = comparator.compare(arr[i], pivot);
            if (cmp < 0) {
                swap(lt++, i++);
            } else if (cmp > 0) {
                swap(i, gt--);
            } else {
                i++;
            }
        }
        return new int[]{lt - 1, gt + 1};
    }

    private void swap(int i, int j) {
        Apartment temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 复用串行实现的尾递归优化快排
    private void quickSort(int low, int high) {
        while (low < high) {
            int[] bounds = threeWayPartition(low, high);
            int leftEnd = bounds[0];
            int rightStart = bounds[1];
            
            if (leftEnd - low < high - rightStart) {
                quickSort(low, leftEnd);
                low = rightStart;
            } else {
                quickSort(rightStart, high);
                high = leftEnd;
            }
        }
    }

    public static void main(String[] args) {
        int size = 100000;
        Apartment[] arr = new Apartment[size];

        for (int j = 0; j < size; j++) {
            arr[j] = new Apartment(1, 2, 3);
        }

        ForkJoinPool pool = new ForkJoinPool(12);
        pool.invoke(new QuickSortMultiThreading(arr, 0, size - 1));
    }
}

关键优化点 #

1. 三路分区：全相等元素场景下，一次分区即可覆盖整个区间，递归深度直接降到O(logn)，从根源避免栈溢出。
2. 递归栈控制：并行处理时优先fork较小分区，直接compute较大分区，避免递归栈过度积累。
3. 线程安全：将static数组改为成员变量，每个任务持有独立的数组引用，避免多线程环境下的冲突。

内容的提问来源于stack exchange，提问作者Kirill Tesla