摘要：方法接受對(duì)象數(shù)組作為參數(shù)，目標(biāo)是對(duì)數(shù)組進(jìn)行升序排序。創(chuàng)建一個(gè)對(duì)象，并調(diào)用方法將它提交給線程池。此排序算法不直接返回結(jié)果給調(diào)用方，因此基于類。

重點(diǎn)是那個(gè)浮點(diǎn)數(shù)數(shù)組排序的例子，從主函數(shù)展開，根據(jù)序號(hào)看

1、GitHub代碼歡迎star。你們輕輕的一點(diǎn)，對(duì)我鼓勵(lì)特大，我有一個(gè)習(xí)慣，看完別人的文章是會(huì)點(diǎn)贊的。

2、個(gè)人認(rèn)為學(xué)習(xí)語言最好的方式就是模仿、思考別人為什么這么寫。結(jié)合栗子效果更好，也能記住知識(shí)點(diǎn)。

3、只因?yàn)樽约褐R(shí)欠缺，語言組織能力不行，所以只能以這樣方式記錄。感覺效果很好。

4、過年前一天，過年中、過年第一天。聽力三遍《我們不一樣》，感謝你們的鼓勵(lì)，點(diǎn)贊。

前面的知識(shí)點(diǎn)都利用率 現(xiàn)在計(jì)算機(jī)提供的并行機(jī)制，然而我們還需要粒度更細(xì)的并行機(jī)制。例如：考慮使用遞歸計(jì)算Fibonacci數(shù)列的方法，

finonacci( n - 1) + finonacci( n - 2)

可以將這兩個(gè)子任務(wù)分配給每個(gè)新的線程，當(dāng)他們計(jì)算完成時(shí)，將結(jié)果相加。事實(shí)上，每個(gè)字問題的計(jì)算又可以分解為兩個(gè)子問題，直到不可細(xì)分位置 這類算法被稱為分治算法復(fù)雜的問題被分解為較小的問題，在根據(jù)字問題的解推導(dǎo)出原始問題的解。這樣問題就容易并行化。Java SE 7引入了新的分支/合并(Fork/Join)框架以簡(jiǎn)化這類分治算法的實(shí)現(xiàn)。

大型任務(wù)被分解為若干塊，然后放入隊(duì)列用于后續(xù)計(jì)算，在隊(duì)列中，任務(wù)還可以將自身分解為更小的部分。線程會(huì)從隊(duì)列中能夠如取出任務(wù)并執(zhí)行。當(dāng)所有線程結(jié)束后 ，將各部分結(jié)果合并得到最終結(jié)果?！胺种А笔侵溉蝿?wù)分解，“合并”是指結(jié)果合并。每個(gè)工作線程都維著任務(wù)的雙端隊(duì)列。隊(duì)列中后來的任務(wù)先執(zhí)行。當(dāng)工作中沒有任務(wù)時(shí)需要執(zhí)行的時(shí)候，會(huì)嘗試從其他線程“竊取”任務(wù)，如果”竊取失敗，沒有其他 工作可做，就會(huì)下線。“竊取”的好處是減少了工作隊(duì)列中爭(zhēng)用情況。

像Task這樣的大型任務(wù)將被分解為兩個(gè)或更多的子任務(wù)，每個(gè)子任務(wù)可以進(jìn)一步分解為新的子任務(wù)。直到子任務(wù)變得足夠簡(jiǎn)單并得到解決。子任務(wù)敵對(duì)得到解決。

ForkJoinPool類是用于執(zhí)行ForkJoinTask的ExecutorSerivce。與其他ExecutorService的不同之處在于ForkJoinPool采用了前面提到的“工作竊取”機(jī)制。在構(gòu)造過程中，可以在構(gòu)造函中指定線程池的大小。如果使用的是默認(rèn)無參構(gòu)造函數(shù)，那么會(huì)創(chuàng)建大小等于可用處理器數(shù)量的線程池。盡管已之地功能線程池的大小，但線程還會(huì)在嘗試維護(hù)更多活躍線程的任意時(shí)刻動(dòng)態(tài)調(diào)整自身大小。ForkJoinPool提供了相應(yīng)方法用于管理和監(jiān)控那些提交的任務(wù)。ForkJoinPool與其他ExecutorService的另一個(gè)重大區(qū)別在于：線程池需要在程序結(jié)束時(shí)顯示停止,因?yàn)槠渲兴械木€程都處于守護(hù)狀態(tài)

有三種不同的方式可以將任務(wù)提交給ForkJoinPool。在異步執(zhí)行模式下，可以調(diào)用execute方法，并將ForkJoinTask作為參數(shù)。至于任務(wù)本身需要調(diào)用fork方法將任務(wù)在多個(gè)線程間分解。如果需要等待計(jì)算結(jié)果，可以調(diào)用ForkJoinPool的invoke方法。在ForkJoinTask中，可以接著調(diào)用invoke方法。invoke方法開始執(zhí)行任務(wù)并在任務(wù)結(jié)束后返回結(jié)果。如果底層失敗就會(huì)拋出異?；蝈e(cuò)誤。最后可以通過調(diào)用ForkJoinPool的submit方法將任務(wù)提交給線程池，submit會(huì)返回一個(gè)Future對(duì)象，可以使用該對(duì)象檢查任務(wù)狀態(tài)和獲取執(zhí)行任務(wù)的結(jié)果。

ForkJoinTask類是運(yùn)行在前面提到的ForkJoinPool中，用來創(chuàng)建任務(wù)的抽象類，RecursiveAction和RecursiveTask僅有兩個(gè)直接子類。任務(wù)在做提交給ForkJoinPool后，便開始執(zhí)行。ForkJoinTask僅包含兩個(gè)操作---分支和合并一旦開始執(zhí)行，就會(huì)啟動(dòng)其他子任務(wù)。合并操作會(huì)等待子操作結(jié)束并在結(jié)果后提取運(yùn)行結(jié)果。ForkJoinTask實(shí)現(xiàn)類Future接口，是Fiture輕量級(jí)形式。Future接口的get方法實(shí)現(xiàn)，可用于等待任務(wù)結(jié)束并取得結(jié)果。還可以通過invoke方法執(zhí)行任務(wù)。該方法會(huì)在任務(wù)結(jié)束后返回結(jié)果，invokeAl方法可以接受任務(wù)集合作為參數(shù)，該方法會(huì)分解出指定集合中的所有任務(wù)，并在每個(gè)人物結(jié)束后返回，或異常時(shí)。

ForkJoinTask類提供若干檢查任務(wù)執(zhí)行狀態(tài)的方法，只要任務(wù)結(jié)束，不管什么方法，isDone方法都用于檢查任務(wù)是否結(jié)束，返回true表示任務(wù)結(jié)束。isCompleledAbnormally方法用于檢測(cè)任務(wù)是否在被取消并且沒有異常的情況下正常結(jié)束。返回true表示正常結(jié)束。
isCancelled方法用于檢查任務(wù)是否被取消，返回true表示正常取消。

通常情況下不會(huì)直接繼承ForkJoinTask類，相反，會(huì)創(chuàng)建基于RecursiveTask或RecursiveAction的類。兩者均為ForkJoinTask的抽象子類。RucursiveTask用于返回結(jié)果的任務(wù)， 而RecursiveAction用于不返回結(jié)果的任務(wù)。無論使用哪一種，都要在子類中實(shí)現(xiàn)compute方法，并在其中執(zhí)行任務(wù)的主要計(jì)算。

/**
 * Created by guo on 16/2/2018.
 * 大型浮點(diǎn)數(shù)數(shù)組排序
 * 需求：
 *      1、假設(shè)有一些數(shù)目非常大的浮點(diǎn)數(shù)(一百萬個(gè))，需要編寫一個(gè)程序?qū)⑦@些數(shù)字按升序排序，
 *      2、針對(duì)單線程的常用排序算法需要消耗過長(zhǎng)的時(shí)間才能生成排好序的數(shù)組。
 *      3、這類問題恰好與分治模式相契合。我們將數(shù)組分解成多個(gè)較小的數(shù)組，并在每個(gè)數(shù)組中獨(dú)立進(jìn)行排序。
 *      4、最后將不斷歸并排好序的數(shù)組合并成更大的數(shù)組以創(chuàng)建最終排好序的數(shù)組。
 */
public class ParallelMergeSort {
    private static ForkJoinPool threadPool;
    private static final int THRESHOLD = 16;

    /**
     * 4、1 sort方法接受對(duì)象數(shù)組作為參數(shù)，目標(biāo)是對(duì)數(shù)組進(jìn)行升序排序。
     * @param objectArray
     */
    private static void sort(Comparable[] objectArray) {
        //4、2 聲明臨時(shí)目標(biāo)數(shù)組用于存儲(chǔ)排序結(jié)果，大小等同于輸入數(shù)組。
        Comparable[] destArray = new Comparable[objectArray.length];
        //4、3 創(chuàng)建一個(gè)SortTask對(duì)象，并調(diào)用invoke方法將它提交給線程池。
        //4、4 SortTask接受4個(gè)參數(shù)，待排序的數(shù)組，已經(jīng)用于存儲(chǔ)排序后的對(duì)象目標(biāo)數(shù)組，源數(shù)組中待排序元素的開始索引與結(jié)束索引。
        threadPool.invoke(new SortTask(objectArray, destArray, 0, objectArray.length - 1));
    }

    /**
     * 重點(diǎn)：
     *    --5、SortTask其功能繼承自RecursiveAction類。
     *      a、此排序算法不直接返回結(jié)果給調(diào)用方，因此基于RecursiveAction類。
     *      b、如果算法具有返回值，比如計(jì)算 finonacci( n - 1) + finonacci( n - 2) ，那么就應(yīng)該繼承RecursiveTask類哦。
     *      c、作為SortTask類的具體實(shí)現(xiàn)的一部分，需要重寫compute抽象方法，
     */
    static class SortTask extends RecursiveAction {
        private Comparable[] sourceArray;
        private Comparable[] destArray;
        private int lowerIndex, upperIndex;

        public SortTask(Comparable[] sourceArray, Comparable[] destArray, int lowerIndex, int upperIndex) {
            this.sourceArray = sourceArray;
            this.destArray = destArray;
            this.lowerIndex = lowerIndex;
            this.upperIndex = upperIndex;
        }

        /**
         * 6、compute方法用于檢查帶排序原色的大小。
         */
        @Override
        protected void compute() {
              //6、1 如果小于預(yù)定義的值THRESHOLD(16),就調(diào)用insertSort方法進(jìn)行排序 。
            if (upperIndex - lowerIndex < THRESHOLD) {
                insertionSort(sourceArray, lowerIndex, upperIndex);
                return;
            }

            //6、2 如果沒有超過，就創(chuàng)建兩個(gè)子任務(wù)并遞歸進(jìn)行調(diào)用。
            //6、3 每個(gè)子任務(wù)接收原有數(shù)組的一半作為自己的源數(shù)組，
            //6、3 minIndex定義了原有數(shù)組的中心點(diǎn)。調(diào)用invokeAll，將這兩個(gè)人物提交給線程池
            //6、4 分解任務(wù)為子任務(wù)的過程會(huì)一直遞歸執(zhí)行，直到每個(gè)子任務(wù)變得足夠小位置。
            //6、5 所有分解得到的子任務(wù)都被遞交給線程池，當(dāng)它們結(jié)束時(shí)，compute方法會(huì)調(diào)用merge方法
            int minIndex = (lowerIndex + upperIndex >>> 1);
            invokeAll(new SortTask(sourceArray, destArray, lowerIndex, minIndex), new SortTask(sourceArray, destArray, minIndex + 1, upperIndex));
            merge(sourceArray, destArray, lowerIndex, minIndex, upperIndex);
        }
    }

    /**
     *歸并算法
     */
    public static void merge(Comparable[] sourceArray, Comparable[] destArray, int lowerIndex, int mindIndex, int upperIndex) {
        //1、 如果源數(shù)組中間索引小于等于右邊的則直接返回。
        if (sourceArray[mindIndex].compareTo(sourceArray[mindIndex + 1]) <= 0) {
            return;
        }
        /**
         * 2、調(diào)用底層實(shí)現(xiàn)的數(shù)組拷貝，是一個(gè)本地方法
         * void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);
         *  src      the source array.
         * srcPos   starting position in the source array.
         * dest     the destination array.
         * destPos  starting position in the destination data.
         * length   the number of array elements to be copied.
         */
        System.arraycopy(sourceArray, lowerIndex, destArray, lowerIndex, mindIndex - lowerIndex + 1);
        int i = lowerIndex;
        int j = mindIndex + 1;
        int k = lowerIndex;
         //3、 將兩個(gè)數(shù)組進(jìn)行歸并，
        while (k < j && j < upperIndex) {
            if (destArray[i].compareTo(sourceArray[j]) <= 0) {
                sourceArray[k++] = destArray[i++];
            } else {
                sourceArray[k++] = sourceArray[j++];
            }
        }
        System.arraycopy(destArray, i, sourceArray, k, j - k);
    }

    /**
     * 插入排序 (得好好研究下算法了)
     * 1、從后向前找到格式的位置插入，
     * 2、 每步將一個(gè)待排序的記錄，按其順序大小插入到前面已經(jīng)排好的子序列合適的位置。
     * 3、直到全部插入位置。
     */
    private static void insertionSort(Comparable[] objectArray, int lowerIndex, int upperIndex) {
        //1、控制比較的輪數(shù)，
        for (int i = lowerIndex + 1; i <= upperIndex; i++) {
            int j = i;
            Comparable tempObject = objectArray[j];
            //2、后一個(gè)和前面一個(gè)比較，如果前面的小，則把前面的賦值到后面。
            while (j > lowerIndex && tempObject.compareTo(objectArray[j - 1]) < 0) {
                objectArray[j] = objectArray[j - 1];
                --j;
            }
            objectArray[j] = tempObject;
        }
    }

    /**
     * 3、1 使用Random類生成范圍在0-1000之間的數(shù)據(jù)點(diǎn)，并使用這些隨機(jī)生成的數(shù)據(jù)初始化數(shù)組每一個(gè)元素。
     * 3、2 創(chuàng)建好的數(shù)據(jù)點(diǎn)的數(shù)目等同于函數(shù)參數(shù)的數(shù)目，這個(gè)例子是1000，增大該數(shù)字，可以驗(yàn)證并行排序算法的效率。
     * @param length
     * @return
     */
    public static Double[] createRandomData(int length) {
        Double[] data = new Double[length];
        for (int i = 0; i < data.length; i++) {
            data[i] = length * Math.random();
        }
        return data;
    }
}

    /**
     * 主函數(shù)
     *
     * @param args
     */
    public static void main(String[] args) {
        //1、獲取當(dāng)前運(yùn)行代碼所在機(jī)器上的可以用處理器數(shù)目
        int processors = Runtime.getRuntime().availableProcessors();
        System.out.println("no of processors:" + processors);
        //2、1創(chuàng)建大小等同于處理器數(shù)目的線程池，這一數(shù)目是運(yùn)行在可用硬件最佳數(shù)目
        //2、2如果創(chuàng)建更大的線程池，就會(huì)有CPU競(jìng)爭(zhēng)的情況發(fā)生，
        //2、3通過實(shí)例化ForkJoinPool，并將線程池大小作為參數(shù)傳入構(gòu)造函數(shù)以創(chuàng)建線程池
        threadPool = new ForkJoinPool(processors);
        //3、構(gòu)造隨機(jī)數(shù)據(jù)的數(shù)組，并輸入以方便嚴(yán)重
        Double[] data = createRandomData(100000);
        System.out.println("original unsorted data：");
        for (Double d : data) {
            System.out.printf("%3.2f ", (double) d);
        }
        //4、調(diào)用sort方法對(duì)生成的數(shù)據(jù)進(jìn)行排序，并再次輸出數(shù)組，以驗(yàn)證數(shù)組已經(jīng)排好序。
        sort(data);

        System.out.println("

 Sorted Array ");
        for (double d : data) {
            System.out.printf("%3.2f ", d);
        }
    }