算法入门上

1. 用递归实现类似Math.prototype.min()方法:返回一个最小值

这是JS内置的一个方法.先从两个数实现开始,最后实现类似Math.min的方法 当我们调用Math.min()时,默认总会返回一个最小值

两个数返回一个最小值

let min = (numbers)=>numbers[0]>numbers[1]？numbers[1]:numbers[0];

min([2,3])    //2

//简化成——析构赋值
let min = ([a,b])=> a>b?b:a

min([2,3])    //2

三个数返回一个最小值

let min2 = ([a,b,c])=> min([a,min([b,c])])
min2([3,4,5])  //3

四个数返回一个最小值

let min3 = ([a,b,c,d]) => min([a,min2([b,c,d])])
min3([4,5,6,7])   //4

你会发现 min min2 min3是环环相扣的.你可以根据min min2 min3 写出min….既然每次调用都是min来计算两个数的大小,如果你学过递归的话并且用递归去写,这个代码量就少的很多

简单实例: 实现1+2+3+4…+100用for和递归做

//for
let num=0;
for(let n=1;n<=100;n++){
  num+=n;
}       //5050

//递归:总之就是不满足条件前一直去调用自身函数,满足条件后逐一释放调用自身函数.前者为递,后者为归
let num=0;
let add = (n) =>{
  if(n<=100){
    add((num+=n,++n))
  }else{
    console.log(num)
  }
}
add(1)  //5050   只要条件成立就会一直调用自身add()函数,条件满足逐一释放自身函数()

//代码优化：
let add = (n) => n<=100?add((num+=n,++n)):console.log(num)

递归实现数集合中的最小值

let min = (numbers) =>{
    if(numbers.length>2){
      return min([numbers[0],min(numbers.slice(1))])
    }else{
      return Math.min.apply(null,numbers)
    }
}

min([2,3,0,4,5])    //0

//如果不知道slice()和apply是什么意思,先去搜索弄明白

apply splice

排序算法

数组从小到大排序,最后用递归实现类似于Array.prototype.sort()方法的函数

两个数实现从小到大

let sort2 = ([a,b]) =>{
  if(a>b){
    return [b,a]
  }else{
    return [a,b]
  }
}

sort2(20,10)    //[10,20]

三个数实现从小到大

//两个数的时候很容易判断那个最小,因为只有两种情况,三个数的话还用两个数的方法显然有点笨拙.
//所以三个数的话,我们先找出最小的值.另外两个去调用sort2
let sort3 = (numbers) =>{
  let index = minIndex(numbers)     //找到最小值的索引
  let min = numbers[index]          //得到最小值
  numbers.splice(index,1)           
  return [min].concat(sort2(numbers))
}

//你可以尝试写出四个数实现从小打到.先找到最小值然后调用sort3

递归实现从小到大排序——属于算法中的选择排序

//找到最小值的索引
let minIndex = (numbers) =>{
  numbers.indexOf(min(numbers))     
}
//min()函数是上面的查找最小值递归函数.indexOf()：找到第一个给定元素的索引

let sort = (numbers) =>{
  if(numbers.length >2){
    let index = minIndex(numbers)
    let min = numbers[index]
    numbers.splice(index,1)
    return [min].concat(sort(numbers))
  }else{
    return numbers[0]<numbers[1]?numbers:numbers.reverse()
  }
}

//你会发现这个递归函数在大于2的时候上sort3差不多,在于sort3调用sort2计算余下的.
//sort调用自己本身是计算其余的.

如果不明白递归,先用纸张写一下递归1+2+3….+100的递归函数,再去推理最小值,从小到大排序的函数