黄申老师的标题实在是太好了,找不到更好的标题来描述今天学习的内容.啊哈哈~

归并排序中的分治思想

问题: 对一堆杂乱无序的数字，按照从小到大或者从大到小的规则进行排序

有序情况

尝试合并有序数组{1, 2, 5, 8}和{3, 4, 6}的过程。

乱序情况

尝试把问题不断简化，也就是把数列不断简化，一直简化到只剩 1 个数。1 个数本身就是有序的，

把将长度为 n 的数列，每次简化为长度为 n-1 的数列，直至长度为 1。不过，这样的处理没有并行性，要进行 n-1 次的归并操作，但是效率会很低.

引入分而治之（Divide and Conquer）的思想

分而治之，我们通常简称为分治。它的思想就是，将一个复杂的问题，分解成两个甚至多个规模相同或类似的子问题，然后对这些子问题再进一步细分，直到最后的子问题变得很简单，很容易就能被求解出来，这样这个复杂的问题就求解出来了。

一个数组的排序

两个数组排序后合并

最重要的思想在于如何拆解问题

归并排序的不同阶段

使用递归的方式来实现已上思路

      // 递归拆分数组
      function merge_sort(to_sort) {
        // 非法数据,直接返回[]
        if (!to_sort) return [];
        
        // 如果分解到只剩一个数，返回该数
        if (to_sort.length == 1) return to_sort;
        
        // 将数组分解成左右两半
        let mid = to_sort.length / 2;

        // js中的splice会操作原数组内容,
        // 前半段取出来之后,后半段直接取原数组的变量应用就好了
        let left = [].concat(to_sort.splice(0,mid))
        let right = [].concat(to_sort)

        // 嵌套调用，对两半分别进行排序
        left = merge_sort(left);
        right = merge_sort(right);
        
        // 合并排序后的两半
        let merged = merge(left, right);
        
        return merged;
      }


// 数组合并排序
function merge(a, b) {
    if (!a) a = [];
    if (!b) b = [];
    
    // 后续会降结果push到这个数组中来
    let merged_one = []
    
    // a,b数组的index
    let ai = 0;
    let bi = 0;
    
    // 轮流从两个数组中取出较小的值，放入合并后的数组中
    while (ai < a.length && bi < b.length) {
     if (a[ai] <= b[bi]) {
        merged_one.push(a[ai])
      ai ++;
     } else {
        merged_one.push(b[bi])
      bi ++;
     }
    }
    
    // 将某个数组内剩余的数字放入合并后的数组中
    if (ai < a.length) {
     for (let i = ai; i < a.length; i++) {
      merged_one.push(a[i])
     }
    } else {
     for (let i = bi; i < b.length; i++) {
      merged_one.push(b[i])
     }
    }
    
    return merged_one;
   }


let arr = [2,5,3,1,4,6,7,8,9]

console.log('排序结果',merge_sort(arr))
// 排序结果 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

分而治之思想在分布式系统中

当需要排序的数组很大（比如达到 1024GB 的时候），我们没法把这些数据都塞入一台普通机器的内存里。该怎么办呢？有一个办法，我们可以把这个超级大的数据集，分解为多个更小的数据集（比如 16GB 或者更小），然后分配到多台机器，让它们并行地处理。

MapReduce 架构

有三个步骤用到了分治的思想

数据分割和映射分割

是指将数据源进行切分，并将分片发送到 Mapper 上。映射是指 Mapper 根据应用的需求，将内容按照键 - 值的匹配，存储到哈希结构中。

归约

归约是指接受到的一组键值配对，如果是键内容相同的配对，就将它们的值归并。这和本机的递归调用后返回结果的过程类似

合并

为了提升洗牌阶段的效率，可以选择减少发送到归约阶段的键 - 值配对。具体做法是在数据映射和洗牌之间，加入合并的过程，在每个 Mapper 节点上先进行一次本地的归约。然后只将合并的结果发送到洗牌和归约阶段。这和本机的递归调用后返回结果的过程类似

尾巴

递归,将复杂问题拆分程简单问题,

再预设自己能想到的所有出现故障的情况(锦囊),加以处理.

一个递归方式的算法就出来了.

微信公众号

本文链接：