## 排序算法 > 如何找出两个数中较小的一个必备知识 - 数据结构 - 用数组`[a,b]`表示两个数字 - JS中没有二元组，用数组代替 - 编程知识：`A?B:C`表达式 ### minOf2 的实现 ```JavaScript //思路 let minOf2_draft = (numbers) => { if(numbers[0] < numbers[1]){ return number[0] }else{ return number[1] } } //优化 let minOf2_draft2 = numbers => numbers[0] a `let minOf2 = ([a,b]) => a a 算法就是把你解决问题的思路用代码表示出来 #### 现成的API ##### JS内置`Math.min` ```JavaScript Math.min(1,2) Math.min.call(null,1,2) Math.min.apply(null,[1,2]) ``` ##### 关于`Math` - 看起来`Math`像`Object`一样是构造函数，但不是，没有函数的共用属性 - 实际上`Math`只是一个普通的内置对象 - 这是目前（2020）唯一的特例：首字母大写是构造函数 ### minOf3 的实现 > 把两个数升级为三个数之间的比较，从三个数找出最小的那个 ```JavaScript // 思路 let minOf2 = ([a,b]) => a { return minOf2([minOf2([a,b]),c]) } // 先把较小的放在前面 let minOf3 = ([a,b,c]) => { return minOf2([a,minOf2([b,c])]) } ``` #### 推理 - `minOf4` ```JavaScript let minOf4 = ([a,b,c,d]) => { return minOf2(a,minOf3([b,c,d])) // 再次调用，并非递归 } ``` - minOfN -> minOf(N-1) -> ... -> minOf2([b,c]) - 推广：任意长度数组求最小值，都可以通过`minOf2`，最终实现 ### min 的实现 > 找出数组中最小值 ```JavaScript let getMin = (numbers) => { return getMin( [numbers[0],getMin(number.slice(1))] ) } ``` - 求最小值，最终还是两两（数组）元素之间比较大小 - 二元法分拆：取出第一个元素；去掉第一个元素后的新数组`arr.slice(1)` - 对新数组再次进行二元法分拆 - 最终只剩两个元素，返回较小值，和最近一次分拆的元素再次比较 - 直至和原始数组的第一个元素比较，最终返回的值即为数组的最小元素 - `[numbers[0], getMin(numbers.slice(1))]` - 去掉数组第一项`numbers.slice(1)`后，并经过比较大小的数比较 - 代码会死循环，不停调用自己，需要添加一个终止条件 ```JavaScript // 设置终止条件 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` > 无需考虑终止条件，逐项比较 ```JavaScript //循环 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`繁琐 ```JavaScript // 递归写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的数组排序 ```JavaScript // 思路 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的数组排序 ```JavaScript 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)` > > 用求最小值的方法，先把三个数中最小的放到最前面的位置 > > 然后将后面两个数用两数排序的方法排列 ```JavaScript // 已知求最小值函数为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的数组排序 ```JavaScript // 已知求最小值函数为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]])) ``` --- #### 推广 > 每次选择一个最小的数放最前面，连接剩余的元素组成的新数组 > > 然后对后面的数做同样的事情 > > 直到剩下最后两个互相比较排序 > > 回归 ```JavaScript // 已知求最小值函数为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] 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] --- ### 如何调试代码 ```JavaScript 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]:3:17) 2）sort发现getMinIndex不存在，调用栈，压栈 // at :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(:2:11) 3）getMinIndex发现getMin不存在 // at sort (:3:17) 2）sort调用了getMinIndex // at :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] 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] 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++（循环） ```JavaScript //递归思路 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` 互换传值/址 ```JavaScript let swap = (array, i, j) => { let temp = array[i] array[i] = array[j] array[j] = temp } swap(numbers,1,2) ``` > 容易错误地实现`swap` ```JavaScript 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`的析构赋值 ```JavaScript 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 < ???` 处应该怎么写 ```JavaScript 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](//static.xiedaimala.com/xdml/image/8c266e6f-55a2-4348-a180-17cb8cdb2c46/2020-3-17-2-15-28.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](//static.xiedaimala.com/xdml/image/8c266e6f-55a2-4348-a180-17cb8cdb2c46/2020-3-17-2-15-45.PNG) --- | i | 要找几个 | 忽略几个 | |:---:|:---:|:---:| | 0 | 4 | 0 | | 1 | 3 | 1 | | 2 | 2 | 2 | --- - 每次找`minIndex(numbers.slice(i))`里面最小的 > 为什么要` + i ` - 如果不加，那么`index`总是从`0`数起，每次都会少掉 `i` 个 - `minIndex(numbers.slice(i))`切掉下标的要加回来重新分析代码 ```JavaScript 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](//static.xiedaimala.com/xdml/image/8c266e6f-55a2-4348-a180-17cb8cdb2c46/2020-3-17-2-15-59.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` --- 改进代码 ```JavaScript // 试写 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]) ``` 最终代码 ```JavaScript 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个数 - 3个数 - 4个数 - N个数 - 用到的概念 - 数组（数据结构）`slice`、`concat`、`splice`、`reverse` - 递归：代入法理解；归纳法；确定终止条件分支 - 循环写法 #### 算法心得 - 擦起键盘肝->运行调试->循环->优化 - 耐心 - 查改删筛重排 #### 手写题 ```JavaScript // 手写一个递归的数组选择排序 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. 高频题目精讲 --- ### 1. 递归的概念 ### 2. 递归三要素 ### 3. 高频题目精讲 --- ·未完待续· --- #### 参考链接 [2020版前端体系课【方方】之【算法与数据结构】排序算法(上)](https://xiedaimala.com/tasks/bf31e965-ffef-45a9-936c-2b41ee577c29) [程序员的算法课递归](https://xiedaimala.com/tasks/28f651d1-6d33-4d4d-8f98-8c0ce6509c19) [伪代码与流程图.pdf](https://static.xiedaimala.com/xdml/file/3ac7c224-c23d-491f-84b5-4fabfbeab9b8/2019-10-1-10-24-6.pdf) [算法入门（上）.pdf](https://static.xiedaimala.com/xdml/file/3ac7c224-c23d-491f-84b5-4fabfbeab9b8/2020-1-9-16-20-15.pdf) [算法入门（下）.pdf](https://static.xiedaimala.com/xdml/file/3ac7c224-c23d-491f-84b5-4fabfbeab9b8/2019-10-8-11-27-48.pdf) [数据结构（上）.pdf](https://static.xiedaimala.com/xdml/file/3ac7c224-c23d-491f-84b5-4fabfbeab9b8/2019-10-9-22-25-26.pdf) #### 相关文章 - 无 --- - 作者： Joel - 文章链接： - [版权声明](http://xmasuhai.xyz/posts/版权声明链接/) - 非自由转载-非商用-非衍生-保持署名 --- ---

【算法与数据结构01】排序算法（上）