分而治之思想

分而治之不是数据结构而是算法设计中的一种方法或者说是一种思想。它的思想是将一个大问题分成多个和原问题相似的小问题,递归解决小问题,再将结果合并来解决原来的问题。排序算法中的快速排序和归并排序就用到了分而治之的思想。

分而治之的三个通用步骤：

1. 分 ----将问题分解成两个或者多个小问题

2. 递归 -------递归解决小问题

3. 合 -----将结果合并解决原来的问题

场景一:归并排序

按照思路:

1. 分: 数组从中间一分为二
2. 递归: 递归进行归并排序,将小数组变成有序数组
3. 合:合并为有序数组

function mergeSort(arr){
  if(arr.length<2)return arr;
  let length =arr.length;
  //分
  let left = arr.slice(0,Math.floor(length/2))
  let right = arr.slice(Math.floor(length/2))
  //递归
  let a = mergeSort(left),b=mergeSort(right)
  //合
  return merge(a,b) 
}
function merge(left,right){
  let arr= [];
  
  while(left.length&&right.length){
    left[0]<right[0]?
    arr.push(left.shift()):
    arr.push(right.shift())
  }
  while(left.length){
    arr.push(left.shift())
  }
  while(right.length){
    arr.push(right.shift())
  }
  return arr
}

归并排序就体现了分而治之的思想,按照思路分解数组,递归然后合并,就完成了归并排序,它的时间复杂度是nlogn,空间复杂度是O(n)。

场景二:快速排序

按照思路:

1. 分: 数组选取基准分成两个子数组,基准可以任意选取比如取开头或者结尾
2. 递归: 递归进行快速排序,将小数组变成有序数组,和归并一样,分解到数组长度为1就是有序的然后再合并,但归并是从小到大,快速排序是从大到小。快排是将大数组选基准分到左右两边再继续分,但归并是先分到最小长度的数组再合并,仔细思考
3. 合:合并为有序数组

function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

function quick1(arr, left, right) {
  // console.log(left,right)
  if (left < right) {
    let i = left,
      j = left;
    let pivot = arr[right]
    for (j = left; j < arr.length; j++) { 
    //保证了i左边的数都比privor小(这同时也是右边的数比privor大),这就够了,到时候privor放到i就行
      if (arr[j] < pivot) {
        swap(arr, i, j)
        i++
      }
    }
    // 交换基准点
    arr[right] = arr[i]
    arr[i] = pivot
    quick1(arr, left, i - 1)
    quick1(arr, i + 1, right)
  }
}

总结: 请牢记分而治之的思路,想好怎么将大问题分解成小问题(难),然后递归再合并就可以解决了。