Java 并行快速排序：Fork/Join 框架的高效应用与性能对比

原创

你被录用了

修改于 2025-04-01 00:33:56

380

文章被收录于专栏：JavaJava

1.引言

排序算法是计算机科学中的基础问题，在大规模数据处理场景下，如何提高排序速度成为一个关键挑战。快速排序（QuickSort）因其平均时间复杂度为 O(nlogn) 而备受青睐。然而，在单线程环境下，传统快速排序无法充分利用多核 CPU 的并行计算能力。

本篇文章将介绍如何使用 Fork/Join 框架实现 并行快速排序，并与单线程版本进行性能对比，探索其在大规模数据处理中的优势。

2.快速排序算法回顾

快速排序基于分治思想，其具体实现主要有三个步骤：

1.基准选取：选择数组中一个元素作为基准并将它与数组中第0个元素交换，记录下该基准值，视数组第0个元素为空。

2.划分：找到基准应该放的数组中的位置，基准值的左边全部小于该值，基准值的右边全部大于该值。将基准值填入该位置。

3.分治：对基准值的左半部分数组和右半部分数组分别重复这三个步骤。直到数组长度为1。

代码实现：

public static void quickSort(int[] array, int left, int right) {
    if (right <= left) return;
    int mid = partition(array, left, right);
    quickSort(array, left, mid - 1);
    quickSort(array, mid + 1, right);
}

public static int partition(int[] array, int left, int right) {
    int pivot = array[left];
    while (left < right) {
        while (left < right && array[right] >= pivot) right--;
        array[left] = array[right];
        while (left < right && array[left] <= pivot) left++;
        array[right] = array[left];
    }
    array[left] = pivot;
    return left;
}

该算法在最坏情况下（例如已经排序的数组）会退化为 O(n^2) ，但在一般情况下仍能保持 O(nlogn) 的时间复杂度。

3. 并行快速排序

3.1 为什么需要并行？

现代 CPU 具有多核架构，如果我们能将排序任务分配给多个线程并行执行，将能显著提升性能。Java 提供的 Fork/Join 框架非常适合用于分治和递归任务的并行化处理。

而快速排序就是一种基于分治思想的排序算法，它在每次分治将当前排序任务拆分成为两个小的排序任务的时候都可以使用多线程并行技术对其进行优化。让两个小排序任务可以并行计算。

3.2 Fork/Join 框架

Fork/Join 框架是 Java 7 引入的一个 工作窃取（Work Stealing）线程池，适用于将大任务拆分为多个子任务，并行执行，然后合并结果。

Fork（拆分任务）： 任务大于阈值时，拆分为多个子任务并行执行。
Join（合并结果）： 等待子任务完成后，合并结果。

3.3 并行快速排序实现

完整代码如下：

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

static class Task extends RecursiveAction {
    int[] array;
    int left;
    int right;

    public Task(int[] array, int left, int right) {
        this.array = array;
        this.left = left;
        this.right = right;
    }

    public int partition(int[] array, int left, int right) {
        int pivot = array[left];
        while (left < right) {
            while (left < right && array[right] >= pivot) right--;
            array[left] = array[right];
            while (left < right && array[left] <= pivot) left++;
            array[right] = array[left];
        }
        array[left] = pivot;
        return left;
    }

    @Override
    protected void compute() {
        if (right <= left) return;
        int mid = partition(array, left, right);
        Task leftTask = new Task(array, left, mid - 1);
        Task rightTask = new Task(array, mid + 1, right);
        invokeAll(leftTask, rightTask);
    }
}

继承 RecursiveAction，实现任务分解

在 Fork/Join 框架中，我们需要继承 RecursiveAction（无返回值任务）或 RecursiveTask<T>（有返回值任务）。这里，我们使用 RecursiveAction，因为快速排序的操作只是在数组上进行排序，不需要返回任何值。

static class Task extends RecursiveAction {
    int[] array;
    int left;
    int right;

    public Task(int[] array, int left, int right) {
        this.array = array;
        this.left = left;
        this.right = right;
    }

Task 类表示一个子任务，它接受待排序的数组和当前处理的区间 left 到 right。当 Task 被执行时，它会递归地拆分子任务，直到满足递归终止条件。

分区（partition）

快速排序的关键步骤是分区（partition），即选择一个基准元素（pivot），然后调整数组，使得：

所有小于 pivot 的元素位于左侧；
所有大于 pivot 的元素位于右侧；
pivot 最终落在正确的位置。

public int partition(int[] array, int left, int right) {
    int pivot = array[left];  // 选择最左边的元素作为基准
    while (left < right) {
        while (left < right && array[right] >= pivot) right--;  // 从右向左找小于 pivot 的元素
        array[left] = array[right];  // 交换到左侧
        while (left < right && array[left] <= pivot) left++;  // 从左向右找大于 pivot 的元素
        array[right] = array[left];  // 交换到右侧
    }
    array[left] = pivot;  // 放置 pivot 到正确的位置
    return left;  // 返回 pivot 的最终索引
}

我每次选取 arrayleft 作为基准值，并利用 双指针（left 和 right）进行交换。循环终止后，pivot 被放置到最终位置，并返回它的索引 mid，以便后续递归排序。

递归拆分任务

compute() 方法是 RecursiveAction 任务的核心执行逻辑：

@Override
protected void compute() {
    if (right <= left) return;  // 递归终止条件

    int mid = partition(array, left, right);  // 进行分区
    Task leftTask = new Task(array, left, mid - 1);  // 处理左半部分
    Task rightTask = new Task(array, mid + 1, right);  // 处理右半部分

    invokeAll(leftTask, rightTask);  // 并行执行两个子任务
}

递归终止条件：如果 left >= right，说明子数组只有一个或零个元素，直接返回。
分区：调用 partition() 方法，找到 pivot 的索引 mid。
创建子任务： leftTask 负责对 left, mid-1 进行排序。undefined rightTask 负责对 mid+1, right 进行排序.
并行执行任务：使用 invokeAll(leftTask, rightTask)，Fork/Join 框架会自动管理线程调度。3.4 启动并行快速排序

ForkJoinPool pool = new ForkJoinPool();  // 创建线程池
Task task = new Task(array, 0, array.length - 1);  // 创建任务
pool.invoke(task);  // 执行任务

ForkJoinPool 是Fork/Join框架中的线程池，能够自动管理任务分配和线程调度。

4.单线程 vs. 多线程性能对比

4.1 测试代码

public static void main(String[] args) {
    ForkJoinPool pool = new ForkJoinPool();
    Random random = new Random();
    int size = 10_000_000;

    int[] array1 = new int[size];
    int[] array2 = new int[size];

    for (int i = 0; i < size; i++) {
        int randomValue = random.nextInt();
        array1[i] = randomValue;
        array2[i] = randomValue;
    }

    long start = System.nanoTime();
    pool.invoke(new Task(array1, 0, array1.length - 1));
    long duration = System.nanoTime() - start;
    System.out.println("并行快速排序耗时：" + duration / 1e6 + "ms");

    start = System.nanoTime();
    quickSort(array2, 0, array2.length - 1);
    duration = System.nanoTime() - start;
    System.out.println("单线程快速排序耗时：" + duration / 1e6 + "ms");
}

4.2 测试结果

数组大小	单线程	多线程
1000	0.2437ms	9.9459ms
10000	1.7561ms	14.001ms
100000	13.4926ms	30.2836ms
1000000	93.7132ms	64.5085ms
10000000	985.7065ms	343.8639ms
100000000	10856.8635ms	1986.0832ms

可以看出，数据规模在较小的时候，单线程的性能优于多线程，这时因为在数据较小的时候，多线程的创建和管理的开销比快速排序本身的开销还要大。

但随着数据规模的增大，多线程并行计算的优势逐渐显现出来，充分利用了多核 CPU 的计算能力。

5.结论

5.1 何时使用并行快速排序？

数据量大（> 1,000,000）时，并行排序能显著提升性能。
CPU 核心数较多（如 8 核以上）时，多线程排序效果更明显。

5.2 并行排序的限制

线程管理开销： 小数据量时，多线程的创建与管理可能比排序本身更耗时。

分区不均衡： 若数据本身有序，可能导致负载不均，影响性能。

5.3 总结

本篇文章介绍了 快速排序 的原理，并通过 Fork/Join 框架 实现了并行快速排序。通过实验对比，我们发现 并行计算 在大规模数据集上具有显著优势，是高性能数据处理中的重要优化手段。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

排序算法

线程池

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

排序算法

线程池

登录后参与评论

0 条评论

热度