分而治之

分而治之算法设计中的一种方法，将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并并解决原来的问题

归并排序

• 分：把数组从中间一分为二
• 解：递归对两个子数据进行归并排序

• 合： 合并有序子数组

  /** 
  * 归并排序
  */
  Array.prototype.mergeSort = function() {
  const rec = arr => {
    if (arr.length <= 1) {
      return arr;
    }
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right =  arr.slice(mid);
    const orderLeft = rec(left);
    const orderRight = rec(right);
    const res = [];
    while(orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(orderLeft[0] > orderRight[0] ? orderRight.shift() : orderLeft.shift())
      } else if (orderLeft.length) {
        res.push(orderLeft.shift())
      } else if (orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res;
  }
  const newArr = rec(this);
  newArr.forEach((item, index) => {
    this[index] = item;
  })
  }

  
  

  快速排序

• 分：选基准，按基准把数组分成了两个子数组

• 解：递归对两个子数组进行快速排序

• 合：对两个子数组进行合并

  /** 
  * 快速排序
  */
  Array.prototype.quickSort = function() {
  const rec = (arr) => {
    if (arr.length <= 1) {
      return arr;
    }
    const left = [];
    const right = [];
    const mid = arr[0];
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] > mid) {
        right.push(arr[i])
      } else {
        left.push(arr[i])
      }
    }
    return [...rec(left), mid, ...rec(right)];
  }
  const newArr = rec(this);
  newArr.forEach((item, index) => {
    this[index] = item;
  })
  }