排序算法(上)

2020-10-16
1 min read

算法里面最简单的就是排序算法,这节课主要讲选择排序。
算法入门:四种排序算法(选择、归并、快速、技术)和对应的结构。

实现minOf2:2个数找出较小的那个 在这里插入图片描述

再优化

析构赋值:把结构拆开,依次复制
let minOf2=([a,b]) => a < b ? a : b 
//调用
minOf2([1,2]) //小白调用法
minOf2.call(null,[1,2]) //高手调用法

现成API
JS内置了Math.min
Math.min(1,2)
Math.min.call(null,1,2)
Math.min.apply(null,[1,2])
关于Math
看起来Math像Object一样是构造函数
实际上Math只是普通对象,唯一一个首字母大写的对象,对象一般首字母小写

实现minOf3:3个数找出最小的那个 在这里插入图片描述

推广,任意长度数组求最小值 在这里插入图片描述

递归
特点
函数不停调用自己,每次调用的参数略有不同
当满足某个简单条件时,则实现一个简单的调用
最终算出结果
理解
可以用代入法快速理解递归
可以用调用栈快速理解递归 在这里插入图片描述

解析 代入法,先递进后回归 在这里插入图片描述

知识点
1.numbers.slice(1) 选中从下标1开始的所有数据
2.Math.min.apply(null,numbers)
apply就是把numbers一个个展开调用。call就是把numbers作为一项。

var arr = [1,3,6,8,2,10];
var minNum = Math.min.apply(null,arr);
console.log(minNum);  //1

Math.min 可以实现得到数组中最小的一项
Math.min.apply(null,arr)其中第一个参数null,这个是因为没有对象去调用这个方法,所以直接传递null过去。同理,Math.max.apply可以获得数组里面最大的值。

实现sort排序(将正整数数组从小到大排序)

排序算法
思路: 1’用递归实现、2’用循环实现

递归思路

选择排序
例1.将长度为2的数组排序 在这里插入图片描述

例2.将长度为3的数组排序
思路:先求最小值,把最小值放前面。
然后将后面2个数字进行"2个数的排序"。 在这里插入图片描述

let minIndex = (numbers) => numbers.indexOf(min(numbers)) 
//取巧:如果有2个最小数,只会返回第1个最小数的下标。

let sort3 = (numbers) => {
//获取最小数字的下标
  let index = minIndex(numbers) //minIndex函数
  let min = numbers[index]
//获取最小数下标后再将其删掉,返回被保留的数字
  numbers.splice(index, 1) 
  return [min].concat(sort2(numders))
}

知识点
1.JS中concat用于2个数组的相加,拼成一个数组
2.sort2(numders)得到的是排好序的2个数
3.numbers.indexOf求出某个数字的下标

例3.将长度为4的数组排序 在这里插入图片描述

推广,任意长度的数组排序
死循环,到2个数时不会断。

在这里插入图片描述 在这里插入图片描述 要理解递归,必须用代入法

选择排序:每次找到最小的数放前面,然后对后面的数做同样的事情。

例子:假设我没理解splice,于是我写了rest,实际上splice会返回被删除部分而不是被余下部分。

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

分析报错
当前代码属于匿名的函数,调用了sort,sort调用了minIndex,minIndex调用了min,并发现min不存在。
这个就叫做调用栈,函数调了函数,前面的函数就要压到栈里面。
它说没有定义那就一定没有定义,找原因。
1.<anonymous>,当前代码属于匿名的函数
2.at sort,调用了sort 在这里插入图片描述

结果不符合预期,把每一步的结果打出来 在这里插入图片描述

推断出rest有问题 那怎么拿到剩余的数呢? 在这里插入图片描述

总结
1.求最小值: 2个数、3个数、N个数
2.排序: 2个数、3个数、N个数
用到的东西: 数组(数据结构)、递归
1.请写一个min函数,要求min(numbers)能返回数组numbers中的最小数字。

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

2.请写出一个sort函数,要求sort(numbers)能返回一个把numbers 从小到大排列的数组

let minIndex = (numbers) => numbers.indexOf(min(numbers))
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()
  }
}
sort([21,8,44,92])