算法里面最简单的就是排序算法，这节课主要讲选择排序。
算法入门:四种排序算法(选择、归并、快速、技术)和对应的结构。
实现minOf2:2个数找出较小的那个
[图片上传失败...(image-257150-1652091073113)]
再优化
析构赋值:把结构拆开，依次复制
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个数找出最小的那个
[图片上传失败...(image-937285-1652091073113)]
推广，任意长度数组求最小值
[图片上传失败...(image-f37544-1652091073113)]
递归
特点
函数不停调用自己，每次调用的参数略有不同
当满足某个简单条件时，则实现一个简单的调用
最终算出结果
理解
可以用代入法快速理解递归
可以用调用栈快速理解递归
[图片上传失败...(image-ca9d77-1652091073113)]
解析 代入法，先递进后回归
[图片上传失败...(image-f898cb-1652091073113)]
知识点
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的数组排序
[图片上传失败...(image-506564-1652091073113)]
例2.将长度为3的数组排序
思路:先求最小值，把最小值放前面。
然后将后面2个数字进行"2个数的排序"。
[图片上传失败...(image-307739-1652091073113)]
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的数组排序
[图片上传失败...(image-8d82f5-1652091073113)]
推广，任意长度的数组排序
死循环，到2个数时不会断。
[图片上传失败...(image-912c9a-1652091073113)]
[图片上传失败...(image-5c265e-1652091073113)]
要理解递归，必须用代入法
选择排序:每次找到最小的数放前面，然后对后面的数做同样的事情。
例子:假设我没理解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
[图片上传失败...(image-d2568c-1652091073113)]
结果不符合预期，把每一步的结果打出来
[图片上传失败...(image-7896b9-1652091073113)]
推断出rest有问题
那怎么拿到剩余的数呢？
[图片上传失败...(image-dbef1e-1652091073113)]
总结
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])
