前言

• Fork/Join框架是Java 7提供的一個(gè)用于并發(fā)執(zhí)行任務(wù)的框架危喉，其主要思想就是把大任務(wù)分割成若干的小任務(wù)，最終匯總每個(gè)小任務(wù)結(jié)果后得到大任務(wù)結(jié)果的框架况凉。
• 熟悉數(shù)據(jù)結(jié)構(gòu)的朋友可能立刻可以想到其中歸并排序也是也是一樣的思想舞肆，所以自然而然就想是否可以用fork/join框架實(shí)現(xiàn)并行（單CPU下為并發(fā)）的歸并排序嚷往，基于這個(gè)考慮，就隨手寫了一個(gè)排序算法粘驰。

歸并排序

• 下面是代碼

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];
        }
    }
}

• 其實(shí)上面的這段代碼還是有很多問題的屡谐，比如用于沒有返回結(jié)果的任務(wù)，繼承RecursiveAction更好蝌数，但是由于是第一次嘗試愕掏，就放著吧。

快速排序

• 其實(shí)再想想顶伞，好像快排也可以用fork/join框架實(shí)現(xiàn)饵撑。
• 下面是代碼

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();
        }
    }
}