排序算法(下)

2020-10-16

1 min read

所有算法都有2种写法递归和循环。
目前的minIndex,看着就繁琐。

let minIndex = (numbers) => numbers.indexOf(min(numbers))
let min = (numbers) => {
  return min( [numbers[0], min(numbers.slice(1))] )
}

minIndex重写

let minIndex = (numbers) =>
  let index=0 //默认下标为0开始
  for(let i=1;i<numbers.length;i++){//默认从第2个开始比
    if(numbers[i]<numbers[index]){
      index=i
    }
  }
  return index
}

默认返回下标为0(默认第1个数是最小的数)，然后用每个数跟它比。
哪个数字比它小就把下标置为那个小的数字。
所有递归都能改为循环

面试题
四种排序算法以及时间复杂度

改写sort:选择排序的循环写法

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

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()
  }
}

在这里插入图片描述

实现swap

let swap = (array, i, j) => {
  let temp = array[i]
  array[i] = array[j]
  array[j] = temp
}
swap(numbers, 1, 2)

思考1.错误地实现swap 在这里插入图片描述

思考2.怎么知道?处应该写什么
暴力分析在这里插入图片描述

假设numbers的长度为n=4,推算出i最大为2。在这里插入图片描述

重新分析代码 在这里插入图片描述

最终代码 在这里插入图片描述

let sort = (numbers) => {
  for(let i=0; i< numbers.length -1; i++){
    console.log(`----`) //这个log很精髓
    console.log(`i: ${i}`)
    let index = minIndex(numbers.slice(i))+ i
    console.log(`index: ${index}`)
    console.log(`min: ${numbers[index]}`)
    if(index!==i){
      swap(numbers, index, i)
      console.log(`swap ${index}: ${i}`)
      console.log(numbers)
    }
}
  return numbers
}

在这里插入图片描述