32

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

public class ParallelQuickSort extends RecursiveAction {
    private final int[] array;
    private final int low;
    private final int high;
    private static final int THRESHOLD = 1000;  // 阈值，决定何时顺序排序

    public ParallelQuickSort(int[] array, int low, int high) {
        this.array = array;
        this.low = low;
        this.high = high;
    }

    @Override
    protected void compute() {
        if (high - low < THRESHOLD) {
            Arrays.sort(array, low, high + 1);  // 小任务直接排序
        } else {
            int pivotIndex = partition(array, low, high);  // 分区操作
            ParallelQuickSort left = new ParallelQuickSort(array, low, pivotIndex - 1);
            ParallelQuickSort right = new ParallelQuickSort(array, pivotIndex + 1, high);
            invokeAll(left, right);  // 并行处理左右子任务
        }
    }

    // 分区函数（Hoare分区法）
    private int partition(int[] array, int low, int high) {
        int pivot = array[high];  // 选择最后一个元素为基准
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, high);
        return i + 1;
    }

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

    // 测试代码
    public static void main(String[] args) {
        int[] array = new int[100000];
        // 初始化数组（示例）
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(1_000_000);
        }
        ForkJoinPool pool = new ForkJoinPool();
        ParallelQuickSort task = new ParallelQuickSort(array, 0, array.length - 1);
        pool.invoke(task);
        // 验证排序结果
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                System.out.println("Error: Not sorted!");
                break;
            }
        }
    }
}