前言

• Fork/Join框架是Java 7提供的一个用于并发执行任务的框架，其主要思想就是把大任务分割成若干的小任务，最终汇总每个小任务结果后得到大任务结果的框架。
• 熟悉数据结构的朋友可能立刻可以想到其中归并排序也是也是一样的思想，所以自然而然就想是否可以用fork/join框架实现并行（单CPU下为并发）的归并排序，基于这个考虑，就随手写了一个排序算法。

归并排序

• 下面是代码

public class MergeSortTask extends RecursiveTask<Void>{
    //不需要返回值的task继承RecursiveAction更好
    private int[] array;
    private int left;
    private int right;

    public static void main(String[] args) {
        int[] a = {4,2,1,4,7,5,3,8,2,7,1,78,89,6,5,4,8,5};
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        MergeSortTask task = new MergeSortTask(a, 0, a.length-1);
        Future<Void> result = forkJoinPool.submit(task);
        try {
            result.get();
            for (int n : a) {
                System.out.print(n + " ");
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }

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

    @Override
    protected Void compute() {
        boolean isNeedSplit = right - left >= 1;
        if (isNeedSplit) {
            int mid = (left + right)/2;
            MergeSortTask mergeSortTask1 = new MergeSortTask(array, left, mid);
            MergeSortTask mergeSortTask2 = new MergeSortTask(array, mid+1, right);
            mergeSortTask1.fork();
            mergeSortTask2.fork();
            mergeSortTask1.join();
            mergeSortTask2.join();
            merge(array, left, mid, right);
        }else {
            int mid = (left+right)/2;
            merge(array, left, mid, right);
        }
        return null;
    }

    public static void merge(int a[], int left, int mid, int right) {
        int len = right - left + 1;
        int temp[] = new int[len];
        int i = left;
        int j = mid + 1;
        int index = 0;
        while(i<=mid && j <= right) {
            temp[index++] = a[i] <= a[j] ? a[i++] : a[j++];
        }
        while (i <= mid) {
            temp[index++] = a[i++];
        }
        while (j<=right) {
            temp[index++] = a[j++];
        }
        for (int k = 0; k<temp.length; k++) {
            a[left++] = temp[k];
        }
    }
}

• 其实上面的这段代码还是有很多问题的，比如用于没有返回结果的任务，继承RecursiveAction更好，但是由于是第一次尝试，就放着吧。

快速排序

• 其实再想想，好像快排也可以用fork/join框架实现。
• 下面是代码

public class QuickSortTask extends RecursiveAction{

    private int[] array;
    private int left;
    private int right;

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

    @Override
    protected void compute() {
        int pivot = partition(array, left, right);
        QuickSortTask task1 = null;
        QuickSortTask task2 = null;
        if (pivot - left > 1) {
            task1 = new QuickSortTask(array, left, pivot-1);
            task1.fork();
        }
        if (right - pivot > 1) {
            task2 = new QuickSortTask(array, pivot+1, right);
            task2.fork();
        }
        if (task1 != null && !task1.isDone()) {
            task1.join();
        }
        if (task2 != null && !task2.isDone()) {
            task2.join();
        }
    }

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

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {4,2,1,4,7,5,3,8,2,7,1,78,89,6,5,4,8,5};
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        QuickSortTask task = new QuickSortTask(a, 0, a.length-1);
        Future<Void> result = forkJoinPool.submit(task);
        try {
            result.get();
            for (int n : a) {
                System.out.print(n + " ");
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }
}