群经平议·周官二：分而治之，并归排序-一一网

这是我参与更文挑战的第11天，活动详情查看：更文挑战

1、什么是分而治之

分而治之是一种策略，是一种思想

把一个大问题分成相同的两个或多个小问题，而且小问题之间无关联，分别解决每个小问题，把各个小问题的解答组合起来，使之大问题得到解决
一旦小问题之间有了关联，举个例子
一个大问题A，分成了a1，a2，a3，a4，这四个问题如果都没有关联都能独立的解决，这才是分而治之的思想，如果是下面这种情况：a2的结果和a1有关联，a4的结果和a3有关联，这种就不是分而治之了，这叫做动态规划

分而治之用的多么，分而治之其实用的还是非常多的，比如计算机十大经典算法里，就有三种用到了分而治之的思想，他们分别是归并排序，快速排序，和二分查找，还有大数据技术MapReduce都是应用了分而治之的思想，所以分而治之在计算机世界里是非常非常重要的

2、归并排序

对于一个数组，利用递归和分治技术将数据序列分为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列

若将两个有序表合并成一个有序表，称为2路并归，与之对应的还有多路并归

为了提升性能有时我们再半子表的个数小于某个数的情况下，对半子表采用其他排序算法

并归排序图示

将原始数组拆分成子表

然后对子表进行排序

小问题解决完（小子表排完序之后），就开始合并子表一里的各个值和子表而二里的值分别比较并排序

以上就是并归排序的思路，也就是利用了分而治之的思想，将一个很大的一个无须数组拆成很多小数组，排序进行合并，得到一个有序的大数组

3、代码实现

 public static int[] sort(int[] array) {
        if(array.length<=49){
            return InsertionSort.sort(array);//其他排序方式插入排序
        }else{
            /*切分数组，然后递归调用*/
            int mid = array.length / 2;
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            return merge(sort(left), sort(right));
        }
    }
    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {//
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)/*左边数组已经取完，完全取右边数组的值即可*/
                result[index] = right[j++];
            else if (j >= right.length)/*右边数组已经取完，完全取左边数组的值即可*/
                result[index] = left[i++];
            else if (left[i] > right[j])/*左边数组的元素值大于右边数组，取右边数组的值*/
                result[index] = right[j++];
            else/*右边数组的元素值大于左边数组，取左边数组的值*/
                result[index] = left[i++];
        }

        return result;
    }
复制代码