排序算法
如何找出两个数中较小的一个
必备知识
- 数据结构
- 用数组
[a,b]
表示两个数字
- JS中没有二元组,用数组代替
- 用数组
- 编程知识:
A?B:C
表达式
minOf2 的实现
//思路
let minOf2_draft = (numbers) => {
if(numbers[0] < numbers[1]){
return number[0]
}else{
return number[1]
}
}
//优化
let minOf2_draft2 = numbers => numbers[0]<numbers[1]? numbers[0]:numbers[1]
//继续简化
let minOf2 = ([a,b]) => a<b?a:b
let minOf2 = ([a,b]) => a<b?a:b
的写法叫析构赋值,先把结构拆开,依次赋值
调用
let minOf2 = ([a,b]) => a<b?a:b
minOf2([1,2]) // 1 小白调用法
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
只是一个普通的内置对象
- 这是目前(2020)唯一的特例:首字母大写是构造函数
minOf3 的实现
把两个数升级为三个数之间的比较,从三个数找出最小的那个
// 思路
let minOf2 = ([a,b]) => a<b?a:b
let minOf3_draft = ([a,b,c]) => {
return minOf2([minOf2([a,b]),c])
}
// 先把较小的放在前面
let minOf3 = ([a,b,c]) => {
return minOf2([a,minOf2([b,c])])
}
推理
-
minOf4
let minOf4 = ([a,b,c,d]) => {
return minOf2(a,minOf3([b,c,d])) // 再次调用,并非递归
}
- minOfN -> minOf(N-1) -> ... -> minOf2([b,c])
- 推广:任意长度数组求最小值,都可以通过
minOf2
,最终实现
min 的实现
找出数组中最小值
let getMin = (numbers) => {
return getMin(
[numbers[0],getMin(number.slice(1))]
)
}
- 求最小值,最终还是两两(数组)元素之间比较大小
- 二元法分拆:取出第一个元素;去掉第一个元素后的新数组
arr.slice(1)
- 对新数组再次进行二元法分拆
- 最终只剩两个元素,返回较小值,和最近一次分拆的元素再次比较
- 直至和原始数组的第一个元素比较,最终返回的值即为数组的最小元素
-
[numbers[0], getMin(numbers.slice(1))]
- 去掉数组第一项
numbers.slice(1)
后,并经过比较大小的数比较
- 代码会死循环,不停调用自己,需要添加一个终止条件
// 设置终止条件
let getMin = (numbers) => {
if(numbers.length > 2){ // 判断是否剩余两个元素
return getMin( // 递归 调用自己
[numbers[0], getMin(numbers.slice(1))] //对传入的形参(数组)进行析构赋值
)
}else{
return Math.min.apply(null,numbers) // 已经封装好的
}
}
// 优化
let getMin = numbers => (numbers.length > 2) ? getMin([numbers[0], getMin( numbers.slice(1) )]) : (Math.min.apply(null,numbers))
getMin([4,8,76,1,0,-9]) // -9
- 用代入法理解一遍
getMin([2, 4, 3, 1])
getMin([2, getMin([4, 3, 1])])
getMin([2, getMin([4, getMin([3, 1]))]])
getMin([2, getMin([4, Math.min.apply(null,[3, 1]))]])
getMin([2, getMin([4, 1])])-->getMin([2, Math.min.apply(null, [4, 1])])
getMin([2, 1])-->Math,min.apply(null, [2, 1])
1
用循环遍历实现getMin
无需考虑终止条件,逐项比较
//循环
let getMin = numbers => {
let len = numbers.length
let min = numbers[0]
for(let i = 1; i < len; i++){
min = numbers[i] < min ? numbers[i] : min
}
return min
}
重写minIndex
永远有两种写法:「递归」和「循环」
- 目前的
minIndex
繁琐
// 递归写minIndex
let minIndex = (numbers) => { //下标
numbers.indexOf( getMin(numbers) )
let getMin = numbers => (numbers.length > 2) ? getMin([numbers[0], getMin( numbers.slice(1) )]) : (Math.min.apply(null,numbers))
// 用循环重写minIndex 易理解
let minIndex2 = numbers => {
let index = 0
for(let i = 1; i < numbers.length; i++){
if(numbers[i] < numbers[index]){
index = i
} // if
} // for
return index
} // minIndex2
minIndex2([2,1,4,5,8,9,-99])
所有递归都可以改成循环
递归
特点
- 函数不停调用自己,每次调用的参数略有不同,可能是上一次的返回值
- 当满足条件时,则实现一个简单的调用
- 确定终止条件
- 递进到终止条件,代入值,回归,
- 最终算出结果
理解
- 用代入法理解递归
- 用调用栈理解递归(压栈 弹栈)
难度升级:将正整数数组从小到大排序
实现 sort 排序
思路
- 用循环实现:容易理解,但代码复杂
- 用递归实现:代入理解,代码简洁
递归思路
- 选择排序
小试牛刀
将长度为2的数组排序
// 思路
let sort2_draft = ([a,b]) => {
if(a < b){
return [a,b]
}else{
return [b,a]
}
}
// 优化代码
let sort2 = ([a,b]) => a < b ? [a,b] : [b,a]
- 这里
sort2
为终止条件 即递归基准
将长度为3的数组排序
let sort3_draft1 = ([a,b,c]) => {
return [min(a,b,c)],sort2[(???)]
}
- 发现
???
拿不到具体的最小的值,即无法将最小值从数值从数组里排除掉
- 必须知道最小值元素的下标,根据下标删掉最小元素
let index = minIndex(numbers)
从
numbers
里删掉最小的元素numbers.splice(index,1)
,改变原数组
let min = numbers[index]
改进代码
[min].concat(numbers)
用求最小值的方法,先把三个数中最小的放到最前面的位置
然后将后面两个数用两数排序的方法排列
// 已知求最小值函数为getMin
let getMin = numbers => (numbers.length>2)?getMin([numbers[0],getMin(numbers.slice(1))]):(Math.min.apply(null,numbers))
// 获取数组最小元素下标的函数
let getMinIndex = numbers => {
// 得到最小值下标
let minValue = getMin(numbers)
return numbers.indexOf(minValue)
}
// 已知两个元素排序 这里为终止条件 即递归基准
let sort2 = ([a,b]) => a < b ? [a,b] : [b,a]
// 求排序函数
let sort3 = (numbers) => {
// 赋值最小值下标
let index = getMinIndex(numbers)
let min = numbers[index]
let number_2 = numbers.slice(0)
number_2.splice(index,1)
return [min].concat(sort2(number_2))
}
// 或者
let sort3_draft = (numbers) => {
// 赋值最小值下标
let index = getMinIndex(numbers)
let min = numbers[index]
numbers.splice(index,1) // 返回去掉的元素组成的数组,并且改变原数组numbers
return [min].concat(sort2(numbers))
}
console.log(sort3.apply(null,[[11,9,1]]))
console.log(sort3_draft.call(null,[3,2,1]))
将长度为4的数组排序
// 已知求最小值函数为getMin
let getMin = numbers => (numbers.length>2)?getMin([numbers[0],getMin(numbers.slice(1))]):(Math.min.apply(null,numbers))
// 获取数组最小元素下标的函数
let getMinIndex = numbers => {
// 得到最小值下标
let minValue = getMin(numbers)
return numbers.indexOf(minValue)
}
// 已知两个元素排序 这里为终止条件 即递归基准
let sort2 = ([a,b]) => a < b ? [a,b] : [b,a]
// 求排序函数
let sort3 = (numbers) => {
// 赋值最小值下标
let index = getMinIndex(numbers)
let min = numbers[index]
numbers.splice(index,1)
return [min].concat(sort2(numbers))
}
let sort4 = (numbers) => {
let index = getMinIndex(numbers)
let min = numbers[index]
numbers.splice(index,1)
return [min].concat(sort3(numbers))
}// sort3 -> sort2 再次调用,并非递归
}
console.log(sort4.apply(null,[[11,9,1,6]]))
推广
每次选择一个最小的数放最前面,连接剩余的元素组成的新数组
然后对后面的数做同样的事情
直到剩下最后两个互相比较排序
回归
// 已知求最小值函数为getMin
let getMin = numbers => (numbers.length>2)?getMin([numbers[0],getMin(numbers.slice(1))]):(Math.min.apply(null,numbers))
// 获取数组最小元素下标的函数
let getMinIndex = numbers => {
return numbers.indexOf(getMin(numbers))
}
let mySort = numbers => {
if(numbers.length > 2){
let index = getMinIndex(numbers)
let min = numbers[index]
numbers.splice(index,1)
return [min].concat(mySort(numbers))
}else{
return numbers[0]<numbers[1]?numbers:numbers.reverse()
}
}
console.log(mySort([12,5,8,7,9]))
- 用代入法理解一遍(SICP)
mySort([12,5,8,7,9])
= [5] + mySort([12,8,7,9])
= [5] + ([7] + mySort([12,8,9]))
= [5] + ([7] + [8] + mySort([12,9]))
= [5] + ([7] + [8] + [9,12])
= [5] + ([7] + [8,9,12])
= [5] + [7,8,9,12]
= [5,7,8,9,12]
如何调试代码
let mySort = numbers => {
if(numbers.length > 2){
let index = getMinIndex(numbers)
let min = numbers[index]
numbers.splice(index,1)
return [min].concat(mySort(numbers))
}else{
return numbers[0]<numbers[1]?numbers:numbers.reverse()
}
}
console.log(mySort([12,5,8,7,9]))
//*************************************
// Uncaught ReferenceError: getMinIndex is not defined
// at sort (<anonymous>:3:17) 2)sort发现getMinIndex不存在,调用栈,压栈
// at <anonymous>:1:1 1)匿名函数调用了sort
let getMinIndex = numbers => {
let minValue = getMin(numbers)
return numbers.indexOf(minValue)
}
console.log(mySort([12,5,8,7,9]))
//*************************************
// Uncaught ReferenceError: getMin is not defined
// at getMinIndex(<anonymous>:2:11) 3)getMinIndex发现getMin不存在
// at sort (<anonymous>:3:17) 2)sort调用了getMinIndex
// at <anonymous>:1:1> 1)匿名函数调用了sort
console.log(mySort([12,5,8,7,9]))
//*************************************
let getMin = numbers => (numbers.length>2)?getMin([numbers[0],getMin(numbers.slice(1))]):(Math.min.apply(null,numbers))
console.log(mySort([12,5,8,7,9]))
//*************************************
// 把赋值后的结果打印出来
var mySort = (numbers) => {
if(numbers.length > 2){
let index = getMinIndex(numbers)
let min = numbers[index]
console.log(`min: ${min}`)
let rest = numbers.splice(index,1)
console.log(`rest: ${rest}`)
return [min].concat(mySort(rest))
}else{
return numbers[0]<numbers[1]?numbers:numbers.reverse()
}
}
console.log(mySort([12,5,8,7,9]))
//*************************************
// > min: 5 // 符合预期
// > rest: 5 //rest 不符合预期,numbers.splice(index,1)有问题 查mdn
// > [5,5]
//*************************************
var mySort = numbers => {
if(numbers.length > 2){
let index = getMinIndex(numbers)
let min = numbers[index]
console.log(`min: ${min}`)
numbers.splice(index,1)
console.log(`rest: ${numbers}`)
return [min].concat(mySort(numbers))
}else{
return numbers[0]<numbers[1]?numbers:numbers.reverse()
}
}
console.log(mySort([12,5,8,7,9]))
//*************************************
// > min: 5 //先摘除5
// > numbers: [12,8,7,9]
// > min: 7 //再摘除7
// > numbers: [12,8,9]
// > min: 8 //再摘除8
// > numbers: [12,9] //最后剩两个数组排序
// [5,7,8,9,12] //先摘除5,再摘除7,再摘除8,最后剩两个数组排序,再依次反向捅回去
//*************************************
选择排序的循环写法
选择排序的循环思路
用循环改写递归的
sort
思路不变
每次找到最小的数,放前面
然后对后面的书做同样的事情(递归)然后 i++(循环)
//递归思路
let sort_recursion = numbers => {
if(numbers.length > 2){
let index = minIndex(numbers) // minIndex() 的实现省略
let min = numbers[index]
numbers.splice(index, 1)
return [min].concat(sort_recursion(numbers))
}else{
return numbers[0] < numbers[1]? numbers : numbers.reverse()
}
}
// 循环思路
let sort_circulation = numbers => {
for(let i = 0; i < ???; i++){
let index = minIndex(numbers) // minIndex() 的实现省略
// index 是当前最小数的下标
// index 对应的数应该放到 i 处,互换值
swap(numbers, index, i) // 还没实现swap() 把最小的和当前的交换位置
// index i 都是 index 的意思, 建议 i 改名
}
}
分析
- 如何知道
i < ???
处应该怎么写
- 提前写好
minIndex
省略实现,能有效简化问题
- 用
swap
占位能有效简化问题
实现swap
互换传值/址
let swap = (array, i, j) => {
let temp = array[i]
array[i] = array[j]
array[j] = temp
}
swap(numbers,1,2)
容易错误地实现
swap
let swap = (a,b) => {
let temp = a
a = b
b = temp
}
swap(numbers[1], numbers[2]) // 改变原数组
会发现,
numbers[1]
和numbers[2]
的值原封不动因为
a b
是简单类型,传参的时候会复制值而
numbers
是对象,传参是复制地址传值 V.S. 传址
- 用
ES6
的析构赋值
let a = 1, b = 2
[a,b] = [b,a]
let numbers = ['a','b']
// > undefined
[numbers[0],numbers[1]] = [numbers[1],numbers[0]]
// > (2) ["b", "a"]
numbers
// > (2) ["b", "a"]
思路改进:循环选择排序
分析
- 如何知道
i < ???
处应该怎么写
let sort = numbers => {
for(let i = 0; i < ???; i++){ // i < ???
let index = minIndex(numbers) // minIndex() 的实现是否符合预期?
// index 是当前最小数的下标
// index 对应的数应该放到 i 处,即每次 i 接受一次 index 的值:
swap(numbers, index, i) // swap() 已实现
// index i 都是 index 的意思, 建议 i 改名
}
}
// 用循环写minIndex
let minIndex = numbers => {
let index = 0
for(let i = 1; i < numbers.length; i++){
if(numbers[i] < numbers[index]){
index = i
} // if_end
} // for_end
return index
} // minIndex2_end
- 暴力分析,代入法:假设
numbers
的长度n = 4
1.PNG
n i
index
可能的结果
index
预期的结果
4
0
swap(numbers, index, 0)
,index
可能为0/1/2/3
1/2/3
4
1
swap(numbers, index, 1)
,index
可能为0/1/2/3
2/3
4
2
swap(numbers, index, 2)
,index
可能为0/1/2/3
3
4
3
swap(numbers, index, 3)
,index
可能为0/1/2/3
在上一次已经取完,不存在
- 发现问题:
每次
index
都在数组的所有元素中取有可能找到已经排好的第一个最小值,不再调换剩余项的位置
即
minIndex
查找index
范围有问题
-
let index = minIndex(numbers)
错误,不该在原数组里找
- 解决问题:
i
的最大值应为numbers.length - 1
即
???
里应该写numbers.length - 1
每次循环对比上一次,应该去掉上次找到的最小值
- 如果上次循环已经找到一个最小的值,那么下一次找最小值时候,就必须忽略(排除)上次那个找到的最小值
- 把本次找到的最小值提前
swap()
- 截取第
i
次之后的新数组numbers.slice(i)
,不改变原数组
- 得到截取后最小值的下标
minIndex( numbers.slice(i) )
- 将最小值序号变为
minIndex( numbers.slice(i) ) + i
- 即
let index = minIndex( numbers.slice(i) ) + i
,i
为遍历的下标范围小于numbers.length - 1
2.PNG
i 要找几个 忽略几个 0 4 0 1 3 1 2 2 2
- 每次找
minIndex(numbers.slice(i))
里面最小的
为什么要
+ i
- 如果不加,那么
index
总是从0
数起,每次都会少掉i
个
-
minIndex(numbers.slice(i))
切掉下标的要加回来
重新分析代码
let sort = numbers => {
for(let i = 0; i < ???; i++){ // i < ???
let index = minIndex( numbers.slice(i) ) + i // slice() 不改变原数组
swap(numbers, index, i) // swap()改变原数组 将每次排除 i 项的剩余最小值提前
}
}
- 代入法:假设
numbers
的长度n = 4
3.PNG
n i
index
可能的结果
4
0
swap(numbers, index, 0)
,index
可能为 1/2/3
4
1
swap(numbers, index, 1)
,index
可能为 2/3
4
2
swap(numbers, index, 2)
,index
可能为 3
4
3
swap(numbers, index, 3)
,numbers.slice(3)
是[i]
,i = 3
不行,所以i < n - 1
-
i < ???
应为numbers.length - 1
画图
[27,44,35,16]
Object.keys([27,44,35,16]) -> Array(4) [ "0", "1", "2", "3" ]
最小值
16
,最小值下标"3"
i = 0
,最小值下标"3",下标 i 和"3"的值 对换位置swap()
新数组
[16,44,35,27]
,第1项固定
i = 1
,找后面3个元素中最小值 下标"3",下标 i 和"3"的值 对换位置swap()
新数组
[16,27,35,44]
,前2项固定
i = 2
,找后面2个元素中最小值 下标"2",下标 i 和"2"的值 不用对换比较完了,不必再进行循环
i = 3
改进代码
// 试写
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: ${numbers}`)
}else{// if_end
console.log(`不交换`)
}
} // for_end
return numbers
}
// 换值/址函数
let swap = (array, i, j) => {
let temp = array[i]
array[i] = array[j]
array[j] = temp
}
// 最小值下标函数
let minIndex = (numbers) => {
let index = 0
for(let i = 1; i < numbers.length; i++){
if(numbers[i] < numbers[index]){
index = i
} // if_end
} // for_end
return index
} // minIndex_end
sort([1, 199, 27, 93, 124, 4903, 4])
最终代码
let sort = (numbers) => {
for(let i = 0; i < numbers.length - 1; i++){
let index = minIndex(numbers.slice(i)) + i
if(index !== i){
swap(numbers, index, i)
} // if_end
} // for_end
return numbers
} // sort_end
// 换值/址函数
let swap = (array, i, j) => {
let temp = array[i]
array[i] = array[j]
array[j] = temp
} // swap_end
// 最小值下标函数
let minIndex = (numbers) => {
let index = 0
for(let i = 1; i < numbers.length; i++){
if(numbers[i] < numbers[index]){
index = i
} // if_end
} // for_end
return index
} // minIndex_end
sort([1, 199, 27, 93, 124, 4903, 4])
循环选择排序小结
- 所有递归都能改成循环
- 循环的时候有很多细节
- 难以想清楚
- 代入法手动列出表格,找规律
- 难以确定边界条件,即终止条件
- 未实现处理长度为
0
和1
的数组
- 难以想清楚
- 如何
Debug
- 看控制台
- 打
log
- 打
log
同时添加标记
- 看控制台
搞定选择排序,每次选择最小/最大的,选完就排完
选择排序算法总结
- 求最小值
- 2个数
- 3个数
- N个数
- 2个数
- 排序
- 2个数
- 3个数
- 4个数
- N个数
- 2个数
- 用到的概念
- 数组(数据结构)
slice
、concat
、splice
、reverse
- 递归:代入法理解;归纳法;确定终止条件分支
- 循环写法
- 数组(数据结构)
算法心得
- 擦起键盘肝->运行调试->循环->优化
- 耐心
- 查改删 筛重排
手写题
// 手写一个递归的数组选择排序
let sort = numbers =>{
if(numbers.length <= 2){ //递归终止条件
return numbers[0] < numbers[1]? numbers:numbers.reverse()
}else{//递进条件 (numbers.length > 2)
let index = minIndex(numbers) //需要实现求最小值下标的函数
let min = numbers[index]
numbers.splice(index,1)
return [min].concat(sort(numbers)) //连接剩余部分
}
}
递归
- 递归的概念
- 递归三要素:
- 拆解寻找子问题
- 最小子问题(基本问题)
- 递归终止退出条件
- 高频题目精讲
1. 递归的概念
2. 递归三要素
3. 高频题目精讲
·未完待续·
参考链接
2020版前端体系课【方方】之【算法与数据结构】排序算法(上)
相关文章
- 无
- 作者: Joel
- 文章链接:
-
版权声明
- 非自由转载-非商用-非衍生-保持署名