被遗忘的凉白开
文章22
标签34
分类3
群经平议·周官二:分而治之,并归排序

群经平议·周官二:分而治之,并归排序

分而治之是一种策略,是一种思想,分而治之的思想应用很多不止并归排序,还有大数据的mapreduce,线程工具类ForkJoin等等,这也是为学习ForkJoin打基础,对XDM有收获的话,三连走起!

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

1、什么是分而治之

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

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

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

2、归并排序

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

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

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

并归排序图示

将原始数组拆分成子表

image.png

然后对子表进行排序

image.png

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

image.png

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

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

这就是排序的代码

3、总结

分而治之的思想应用很多不止并归排序,还有大数据的mapreduce,线程工具类ForkJoin等等,这也是为学习ForkJoin打基础,对XDM有收获的话,三连走起!

本文作者:被遗忘的凉白开
本文链接:http://amszlk.com/2021/06/24/qun-jing-ping-yi-zhou-guan-er-fen-er-zhi-zhi-bing-gui-pai-xu/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可