算法入门:四种排序算法和对应的结构。

所有算法都有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()
  }
}

[图片上传失败...(image-30b5ab-1652091088953)]

实现swap

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

思考1.错误地实现swap
[图片上传失败...(image-5b6b18-1652091088953)]

思考2.怎么知道?处应该写什么
暴力分析
[图片上传失败...(image-fc0cb7-1652091088953)]

假设numbers的长度为n=4,推算出i最大为2。
[图片上传失败...(image-532281-1652091088953)]

重新分析代码
[图片上传失败...(image-cbe6ec-1652091088953)]

最终代码
[图片上传失败...(image-971d90-1652091088953)]

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
}

[图片上传失败...(image-a22e3f-1652091088953)]

知识点
1.JS ES6析构赋值实现交换ab值

let a=1;let b=2;
[a,b]=[b,a]
//a=2;b=1

2.交换值let temp=a; a=b; b=temp
3.JS删除数组中的某个元素默认返回的还是数组，要取数组的第[0]项
[图片上传失败...(image-c31c17-1652091088953)]
[图片上传失败...(image-326ae7-1652091088953)]

总结
所有递归都能改成循环。循环的时候有很多细节:
这些细节很难想清楚,要动手列出表格找规律,
尤其是边界条件很难确定,我们没有处理长度为0和1的数组。
学会debug

快速排序

递归思路
以某某为基准
[图片上传失败...(image-2dfa13-1652091088953)]

8个人就要指定8次。
快速排序 -阮一峰
[图片上传失败...(image-8b5895-1652091088953)]

归并排序

递归思路
不以某某为基准
[图片上传失败...(image-88880a-1652091088953)]

[图片上传失败...(image-b066c1-1652091088953)]

[图片上传失败...(image-a40f97-1652091088953)]

merge的逻辑图
[图片上传失败...(image-e6ad61-1652091088953)]

计数排序

整理扑克牌的过程就是计数排序
这就是哈希表:A有几个，2有几个，3有几个...
[图片上传失败...(image-e8716b-1652091088953)]

[图片上传失败...(image-6cfa98-1652091088953)]

最终代码:当j出现两次时(当12出现了2次时，就push2次)
[图片上传失败...(image-ee61f8-1652091088953)]

如果你的数据结构升级了，你的算法就会直接升级。
技术排序的特点
事件复杂度对比
[图片上传失败...(image-53705b-1652091088953)]

其它排序算法
冒泡排序
插入排序
希尔排序
基数排序