归并算法

排序问题是我们工作中的常见问题。目前也有很多现成算法是为了解决这个问题而被发明的，例如多种插值排序算法、多种交换排序算法。而归并排序算法是目前所有排序算法中，平均时间复杂度较好（O(nlgn)），算法稳定性较好的一种排序算法。它的核心算法思路将大的问题分解成多个小问题，并将结果进行合并。

归并算法逻辑图:

整个算法的拆分阶段，是将未排序的数字集合，从一个较大集合递归拆分成若干较小的集合，这些较小的集合要么包含最多两个元素，要么就认为不够小需要继续进行拆分。

那么对于一个集合中元素的排序问题就变成了两个问题：1、较小集合中最多两个元素的大小排序；2、如何将两个有序集合合并成一个新的有序集合。第一个问题很好解决，那么第二个问题是否会很复杂呢？实际上第二个问题也很简单，只需要将两个集合同时进行一次遍历即可完成。一一比较当前集合中最小的元素，将最小元素放入新的集合，它的时间复杂度为O(n)：

归并算法实现

public class Merge {
    private static int MAX = 10000*10000;

    private static int inits[] = new int[MAX];

    // 这是为了生成一个数量为MAX的随机整数集合，准备计算数据
    // 和算法本身并没有什么关系
    static {
        Random r = new Random();
        for (int index = 1; index <= MAX; index++) {
            inits[index - 1] = r.nextInt(10000000);
        }
    }

    /**
     * 拆分成较小的元素或者进行足够小的元素集合的排序
     *
     * @param source
     * @return
     */
    private static int[] forkits(int source[]) {
        int sourceLen = source.length;
        if (sourceLen > 2) {
            int midIndex = sourceLen / 2;
            int result1[] = forkits(Arrays.copyOf(source, midIndex));
            int result2[] = forkits(Arrays.copyOfRange(source, midIndex, sourceLen));
            // 将两个有序的数组，合并成一个有序的数组
            int mer[] = joinInts(result1, result2);
            return mer;
        }
        // 否则说明集合中只有一个或者两个元素，可以进行这两个元素的比较排序了
        else {
            // 如果条件成立，说明数组中只有一个元素，或者是数组中的元素都已经排列好位置了
            if (sourceLen == 1
                    || source[0] <= source[1]) {
                return source;
            } else {
                int targetp[] = new int[sourceLen];
                targetp[0] = source[1];
                targetp[1] = source[0];
                return targetp;
            }
        }
    }

    /**
     * 这个方法用于合并两个有序集合
     *
     * @param array1
     * @param array2
     */
    private static int[] joinInts(int array1[], int array2[]) {
        int destInts[] = new int[array1.length + array2.length];
        int array1Len = array1.length;
        int array2Len = array2.length;
        int destLen = destInts.length;

        // 只需要以新的集合destInts的长度为标准，遍历一次即可
        for (int index = 0, array1Index = 0, array2Index = 0; index < destLen; index++) {
            int value1 = array1Index >= array1Len ? Integer.MAX_VALUE : array1[array1Index];
            int value2 = array2Index >= array2Len ? Integer.MAX_VALUE : array2[array2Index];
            // 如果条件成立，说明应该取数组array1中的值
            if (value1 < value2) {
                array1Index++;
                destInts[index] = value1;
            }
            // 否则取数组array2中的值
            else {
                array2Index++;
                destInts[index] = value2;
            }
        }

        return destInts;
    }

    public static void main(String[] args) {
        long beginTime = System.currentTimeMillis();
        int results[] = forkits(inits);
        long endTime = System.currentTimeMillis();
        // 如果参与排序的数据非常庞大，记得把这种打印方式去掉
        System.out.println("耗时=" + (endTime - beginTime) +"ms");
        //System.out.println("Arrays = " + Arrays.toString(results));
    }
}
复制代码

通过测试，1W条随机数排序耗时：2-3ms。10W条随机数排序耗时：16-17ms。100W条随机数排序耗时：140ms。1000W条随机数排序耗时：1.5s左右。1亿条随机数排序耗时：15s-16s。当然排序耗时还和随机生成的待排序数组本身的凌乱程度有关。

ForkJoin处理归并算法

可以看到，随着随机数数组不断增大，以上的算法效率开始下降，数量级到达1亿条时，耗时为16s左右。
根据前一篇文章对ForkJoin的简单讲解。可以用ForkJoin来优化归并算法。

public class MergeForkJoin {
    private static int MAX = 100000000;
    private static int inits[] = new int[MAX];

    // 这是为了生成一个数量为MAX的随机整数集合，准备计算数据
    // 和算法本身并没有什么关系
    static {
        Random r = new Random();
        for (int index = 1; index <= MAX; index++) {
            inits[index - 1] = r.nextInt(10000000);
        }
    }

    /**
     * @Author zhou
     * @Description 单个排序的子任务
     * @Date 2021/7/12 11:18
     * @Param 
     * @return 
     **/
    static class MyTask extends RecursiveTask<int[]> {

        private int source[];

        public MyTask(int source[]) {
            this.source = source;
        }

        /* (non-Javadoc)
         * @see java.util.concurrent.RecursiveTask#compute()
         */
        @Override
        protected int[] compute() {
            int sourceLen = source.length;
            // 如果条件成立，说明任务中要进行排序的集合还不够小
            if (sourceLen > 2) {
                int midIndex = sourceLen / 2;
                // 拆分成两个子任务
                MyTask task1 = new MyTask(Arrays.copyOf(source, midIndex));
                task1.fork();
                MyTask task2 = new MyTask(Arrays.copyOfRange(source, midIndex, sourceLen));
                task2.fork();
                // 将两个有序的数组，合并成一个有序的数组
                int result1[] = task1.join();
                int result2[] = task2.join();
                int mer[] = joinInts(result1, result2);
                return mer;
            }
            // 否则说明集合中只有一个或者两个元素，可以进行这两个元素的比较排序了
            else {
                // 如果条件成立，说明数组中只有一个元素，或者是数组中的元素都已经排列好位置了
                if (sourceLen == 1
                        || source[0] <= source[1]) {
                    return source;
                } else {
                    int targetp[] = new int[sourceLen];
                    targetp[0] = source[1];
                    targetp[1] = source[0];
                    return targetp;
                }
            }
        }

        /**
         * @Author zhou
         * @Description 合并两个有序集合
         * @Date 2021/7/12 11:18
         * @Param [array1, array2]
         * @return int[]
         **/
        private int[] joinInts(int array1[], int array2[]) {
            int destInts[] = new int[array1.length + array2.length];
            int array1Len = array1.length;
            int array2Len = array2.length;
            int destLen = destInts.length;

            // 只需要以新的集合destInts的长度为标准，遍历一次即可
            for (int index = 0, array1Index = 0, array2Index = 0; index < destLen; index++) {
                int value1 = array1Index >= array1Len ? Integer.MAX_VALUE : array1[array1Index];
                int value2 = array2Index >= array2Len ? Integer.MAX_VALUE : array2[array2Index];
                // 如果条件成立，说明应该取数组array1中的值
                if (value1 < value2) {
                    array1Index++;
                    destInts[index] = value1;
                }
                // 否则取数组array2中的值
                else {
                    array2Index++;
                    destInts[index] = value2;
                }
            }

            return destInts;
        }
    }

    /**
     * @return void
     * @Author zhou
     * @Description
     * @Date 2021/7/12 10:20
     * @Param [args]
     **/
    public static void main(String[] args) throws Exception {
        // 正式开始
        long beginTime = System.currentTimeMillis();
        ForkJoinPool pool = new ForkJoinPool();
        MyTask task = new MyTask(inits);
        ForkJoinTask<int[]> taskResult = pool.submit(task);
        try {
            taskResult.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace(System.out);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("耗时=" + (endTime - beginTime) + "ms");
    }
}
复制代码