minIndex

目前的minIndex

  1. let minIndex = (numbers) =>numbers.indexOf(min(mubers))
  2. let min = (numbers) => {
  3.   if(numbers.length > 2){
  4.     return min([numbers[0], min(numbers.slice(1))])
  5.   }else{
  6.     return Math.min.apply(null,numbers)
  7.   }
  8. }

indexOf()方法返回在数组中可以找到一个给定元素的第一个索引，如果不存在，则返回-1。

重写minInd

循环写法

  1. let minIdex = (numbers) => {
  2.   let index = 0
  3.   for(let i=1; i<numbers.length; i++){
  4.     if(numbers[i] < numbers[index]){
  5.        index = i
  6.     }
  7.   }
  8.   return index
  9. }

排序 sort

目前的sort 递归写法

  1. let sort = (numbers) => {
  2.   if(nubers.length > 2){
  3.     let index = minIdex(numbers)
  4.     let min = numbers[index]
  5.     numbers.splice(index,1)
  6.     return [min].concat(sort(numbers))
  7.   }else{
  8.     return numbers[0]<numbers[1] ? numbers : numbers.reverse() 
  9.   }
  10. }

思路：每次找到最小的数放在前面，然后对后面的数做同样的事情

重写sort 循环写法

思路不变：每次找到最小的数放在前面，然后对后面的数做同样的事情，然后i++

  1. let sort = (numbers) => {
  2.   for(let i=0; i<???; i++){
  3.     let index = minIndex(numbers)
  4.     //找到当前范围最小的数，为index，按范围找最小
  5.     //把最小的数放到当前循环的i处，按循序放最小
  6.     swap(numbers,index,i)//交换
  7.   }
  8. }
  9.  let swap = (array,i,j) => {
  10.    let temp = array[i]
  11.    array[i] = array[j]
  12.    array[j] = temp
  13. }
  14. //swap(numbers,1,2)
  • 分析

怎么知道i<???处因该写什么
提前写好minIndex 能有效简化问题
用swap占位能有效简化问题
错误的实现 swap

  1. let swap = (a,b) => {
  2.   let temp = a
  3.   a = b
  4.   b = temp
  5. }
  6. swap(nubers[1],numbers[2])

你会发现，numbers[1] 和 numbers[2] 的值原封不动，因为 a b 是简单数据类型，传参的时候会复制值，而上面的 numbers 是对象，传参复制地址
传值 VS 传址

  • 怎么知道 i<??? 处应该写什么

分析代码

  1. let sort = (numbers) => {
  2.   for(let i=0; i<???; i++){
  3.     let index = minIndex(numbers)
  4.     swap(number, index, i)
  5.   }
  6. }

image.png
发现了问题

  • minIndex 查找范围有问题

    let index = minIndex(numbers)

这句有问题，如果上次循环找到了第一个最小的数字，那么之后找最小数字的时候，就可忽略第一个了

let index = minIndex(numbers.slice(i)) +i

image.png

  • 为什么要 +i

因为前面的已经找到排好序了
如果不加，那么index总是从0数起
重新分析代码

  1. let sort = (numbers) => {
  2.   for(let i=0; i<???; i++){
  3.     let index = minIndex(numbers.slice(i))+i
  4.     swap(number, index, i)
  5.   }
  6. }

image.png

最终带log代码

  1. let sort = (numbers) => {
  2.   for(let i=0; i< numbers.length -1; i++){
  3.     console.log(`----`) // 这个log很精髓
  4.     console.log(`i: ${i}`)
  5.     let index = minIndex(numbers.slice(i))+ i
  6.     console.log(`index: ${index}`)
  7.     console.log(`min: ${numbers[index]}`)
  8.     if(index!==i){
  9.       swap(numbers, index, i)
  10.       console.log(`swap ${index}: ${i}`)
  11.       console.log(numbers)
  12.     }
  13.   }
  14.   return numbers
  15. }
  16. //交换
  17. let swap = (array, i, j) => {
  18.   let temp = array[i]
  19.   array[i] = array[j]
  20.   array[j] = temp
  21. }
  22. //找最小
  23. let minIndex = (numbers) => {
  24.   let index = 0
  25.   for(let i=1; i<numbers.length; i++){
  26.     if(numbers[i] < numbers[index]){
  27.       index = i
  28.     }
  29.   }
  30.   return index
  31. }

最终纯净代码

  1. let sort = (numbers) => {
  2.   for(let i=0; i< numbers.length -1; i++){
  3.     let index = minIndex(numbers.slice(i))+ i
  4.     if(index!==i){
  5.       swap(numbers, index, i)
  6.     }
  7.   }
  8.   return numbers
  9. }
  10. let swap = (array, i, j) => {
  11.   let temp = array[i]
  12.   array[i] = array[j]
  13.   array[j] = temp
  14. }
  15. let minIndex = (numbers) => {
  16.   let index = 0
  17.   for(let i=1; i<numbers.length; i++){
  18.     if(numbers[i] < numbers[index]){
  19.       index = i
  20.     }
  21.   }
  22.   return index
  23. }

总结

所有递归都能改写成循环

循环的时候有很多细节

  • 这些细节很难想清楚
  • 要动手列出表格找规律
  • 尤其是边界条件很难确定

  • 我们没有处理长度为0和1的数组

    如果debug

  • 学会看控制台

  • 学会打log
  • 打log的时候注意加标记