一、可能性（常见）：
1.
旧的：a b c新的：a b c d2.
旧的： a b c新的：d a b c3.
旧的：a b c d新的：a b c4.
旧的：d a b c新的： a b c5.
旧的：a b c d e i f g新的：a b e c d h f g对应的实在虚构节点（为不便了解，文中用字母代替）：
// vnode对象const a = { type: 'div', // 标签 props: {style: {color: 'red'}}, // 属性 children: [], // 子元素 key: 'key1', // key el: '<div style="color: 'red'"></div>', // 实在dom节点 ...}二、找法则
去掉后面和前面雷同的局部
// c1示意旧的子节点，c2示意新的子节点const patchKeyedChildren = (c1, c2) => { let i = 0 let e1 = c1.length - 1 let e2 = c2.length - 1 // 从后面比 while (i <= e1 && i <= e2) { const n1 = c1[i] const n2 = c2[i] // 标签和key是否雷同 // if (n1.type === n2.type && n1.key === n2.key) if (n1 === n2) { // 持续比照其属性和子节点 } else { break } i++ } // 从前面比 while (i <= e1 && i <= e2) { const n1 = c1[e1] const n2 = c2[e2] // 标签和key是否雷同 // if (n1.type === n2.type && n1.key === n2.key) if (n1 === n2) { // 持续比照其属性和子节点 } else { break } e1-- e2-- } console.log(i, e1, e2)}// 调用示例patchKeyedChildren(['a', 'b', 'c', 'd'], ['a', 'b', 'c'])通过这个函数能够失去：
1.
旧的：a b c新的：a b c di = 3 e1 = 2 e2 = 32.
旧的： a b c新的：d a b ci = 0 e1 = -1 e2 = 03.
旧的：a b c d新的：a b ci = 3 e1 = 3 e2 = 24.
旧的：d a b c新的： a b ci = 0 e1 = 0 e2 = -15.
旧的：a b c d e i f g新的：a b e c d h f gi = 2 e1 = 5 e2 = 5扩大：
旧的：a b c新的：a b c d e fi = 3 e1 = 2 e2 = 5旧的：a b c新的：a b ci = 3 e1 = 2 e2 = 2旧的：e d a b c新的： a b ci = 0 e1 = 1 e2 = -1旧的：c d e 新的：e c d hi = 0 e1 = 2 e2 = 3从下面后果中咱们能够找到法则：
- 当i大于e1时，只需增加新的子节点
- 当i大于e2时，只需删除旧的子节点
// 当i大于e1时if (i > e1) { if (i <= e2) { while (i <= e2) { const nextPos = e2 + 1 const anchor = nextPos < c2.length ? c2[nextPos].el : null // 增加新的子节点c2[i]在anchor的后面 // todo i++ } }}// 当i大于e2时else if (i > e2) { if (i <= e1) { while (i <= e1) { // 删除旧的子节点c1[i] // todo i++ } }}- 其它，非凡解决
// 其它let s1 = ilet s2 = i// 以新的子节点作为参照物const keyToNewIndexMap = new Map()for (let i = s2; i <= e2; i++) { // 节点的key做为惟一值 // keyToNewIndexMap.set(c2[i].key, i) keyToNewIndexMap.set(c2[i], i)}// 新的总个数const toBePatched = e2 - s2 + 1// 记录新子节点在旧子节点中的索引const newIndexToOldIndexMap = new Array(toBePatched).fill(0)// 循环老的子节点for (let i = s1; i <= e1; i++) { const oldChild = c1[i] // let newIndex = keyToNewIndexMap.get(oldChild.key) let newIndex = keyToNewIndexMap.get(oldChild) // 在新子节点中不存在 if (newIndex === undefined) { // 删除oldChild // todo } else { newIndexToOldIndexMap[newIndex - s2] = i + 1 // 永远不会等于0, 这样0就能够示意须要创立了 // 持续比照其属性和子节点 // todo }}console.log(newIndexToOldIndexMap)// 须要挪动地位for (let i = toBePatched - 1; i >= 0; i--) { let index = i + s2 let current = c2[index] let anchor = index + 1 < c2.length ? c2[index + 1].el : null if (newIndexToOldIndexMap[i] === 0) { // 在anchor后面插入新的节点current // todo } else { // 在anchor后面插入对应旧节点.el，current.el元素等于对应的旧节点.el（在其它代码中赋值了） // todo }}第1种和第2种比较简单，不做过多的解说，咱们来看看第3种，以上面为例
序号： 0 1 2 3 4 5 6 7旧的：(a b) c d e i (f g)新的：(a b) e c d h (f g)- 后面a b和前面f g是一样的，会去掉，只剩两头乱序局部
- 以新的节点为参照物，循环旧的节点，从旧的节点中去掉新的没有的节点，如i
- 标记旧的中没有的节点，没有就为0，示意须要创立；有就序号+1，示意能够复用
标记： 4+1 2+1 3+1 0新的：(...) e c d h (...)- 从后往前循坏，h为0，创立，放在它下一个f后面；d不为0，复用旧的中的d，放在h后面；c不为0，复用旧的中的c，放在d后面；e不为0，复用旧的中的e，放在c后面
到目标为止，新旧元素的更替曾经全副实现，但大家有没有发现一个问题，e c d h四个元素都挪动了一次，咱们能够看出如果只挪动e和创立h，c和d放弃不变，效率会更高
三、算法优化
1.序号： 0 1 2 3 4 5 6 7旧的：(a b) c d e i (f g)新的：(a b) e c d h (f g)对应的标记是[5, 3, 4, 0]2.序号：0 1 2 3 4 5旧的：c d e i f g新的：e c d f g j对应的标记是[3, 1, 2, 5, 6, 0]从下面两个例子中能够看出：
第1个的最优解是找到c d，只需挪动e，创立h
第2个的最优解是找到c d f g，只需挪动e，创立j
过程：
- 从标记中找到最长的递增子序列
- 通过最长的递增子序列找到对应的索引值
- 通过索引值找到对应的值
留神0示意间接创立，不参加计算
例子：
- [3, 1, 2, 5, 6, 0]的最长的递增子序列为[1, 2, 5, 6]，
- 对应的索引为[1, 2, 3, 4]，
- 而后咱们遍历e c d f g j，标记中为0的，比方j，间接创立；c d f g索引别离等于1 2 3 4，放弃不变；e等于0，挪动
// 须要挪动地位// 找出最长的递增子序列对应的索引值，如：[5, 3, 4, 0] -> [1, 2]let increment = getSequence(newIndexToOldIndexMap)console.log(increment)let j = increment.length - 1for (let i = toBePatched - 1; i >= 0; i--) { let index = i + s2 let current = c2[index] let anchor = index + 1 < c2.length ? c2[index + 1].el : null if (newIndexToOldIndexMap[i] === 0) { // 在anchor后面插入新的节点current // todo } else { if (i !== increment[j]) { // 在anchor后面插入对应旧节点.el，current.el元素等于对应的旧节点.el（在其它代码中赋值了） // todo } else { // 不变 j-- } }}最长的递增子序列
// 最长的递增子序列，https://en.wikipedia.org/wiki/Longest_increasing_subsequencefunction getSequence(arr) { const len = arr.length const result = [0] // 以第一项为基准 const p = arr.slice() // 标记索引，slice为浅复制一个新的数组 let resultLastIndex let start let end let middle for (let i = 0; i < len; i++) { let arrI = arr[i] if (arrI !== 0) { // vue中等于0，示意须要创立 resultLastIndex = result[result.length - 1] // 插到开端 if (arr[resultLastIndex] < arrI) { result.push(i) p[i] = resultLastIndex // 后面的那个是谁 continue } // 递增序列，二分类查找 start = 0 end = result.length - 1 while(start < end) { middle = (start + end) >> 1 // 相当于Math.floor((start + end)/2) if (arr[result[middle]] < arrI) { start = middle + 1 } else { end = middle } } // 找到最近的哪一项比它大的，替换 if (arr[result[end]] > arrI) { result[end] = i if (end > 0) { p[i] = result[end - 1] // 后面的那个是谁 } } } } let i = result.length let last = result[i - 1] while(i-- > 0) { result[i] = last last = p[last] } return result}console.log(getSequence([5, 3, 4, 0])) // [1, 2]console.log(getSequence([3, 1, 2, 5, 6, 0])) // [ 1, 2, 3, 4 ]解说后续补充...
残缺代码
// 最长的递增子序列，https://en.wikipedia.org/wiki/Longest_increasing_subsequencefunction getSequence(arr) { const len = arr.length const result = [0] // 以第一项为基准 const p = arr.slice() // 标记索引，slice为浅复制一个新的数组 let resultLastIndex let start let end let middle for (let i = 0; i < len; i++) { let arrI = arr[i] if (arrI !== 0) { // vue中等于0，示意须要创立 resultLastIndex = result[result.length - 1] // 插到开端 if (arr[resultLastIndex] < arrI) { result.push(i) p[i] = resultLastIndex // 后面的那个是谁 continue } // 递增序列，二分类查找 start = 0 end = result.length - 1 while(start < end) { middle = (start + end) >> 1 // 相当于Math.floor((start + end)/2) if (arr[result[middle]] < arrI) { start = middle + 1 } else { end = middle } } // 找到最近的哪一项比它大的，替换 if (arr[result[end]] > arrI) { result[end] = i if (end > 0) { p[i] = result[end - 1] // 后面的那个是谁 } } } } let i = result.length let last = result[i - 1] while(i-- > 0) { result[i] = last last = p[last] } return result}// c1示意旧的子节点，c2示意新的子节点const patchKeyedChildren = (c1, c2) => { let i = 0 let e1 = c1.length - 1 let e2 = c2.length - 1 // 从后面比 while (i <= e1 && i <= e2) { const n1 = c1[i] const n2 = c2[i] // 标签和key是否雷同 // if (n1.type === n2.type && n1.key === n2.key) if (n1 === n2) { // 持续比照其属性和子节点 } else { break } i++ } // 从前面比 while (i <= e1 && i <= e2) { const n1 = c1[e1] const n2 = c2[e2] // 标签和key是否雷同 // if (n1.type === n2.type && n1.key === n2.key) if (n1 === n2) { // 持续比照其属性和子节点 } else { break } e1-- e2-- } console.log(i, e1, e2) // 当i大于e1时 if (i > e1) { if (i <= e2) { while (i <= e2) { const nextPos = e2 + 1 const anchor = nextPos < c2.length ? c2[nextPos].el : null // 增加子节点c2[i]在anchor的后面 // todo i++ } } } // 当i大于e2时 else if (i > e2) { if (i <= e1) { while (i <= e1) { // 删除子节点c1[i] // todo i++ } } } // 其它 else { let s1 = i let s2 = i // 以新的子节点作为参照物 const keyToNewIndexMap = new Map() for (let i = s2; i <= e2; i++) { // 节点的key做为惟一值 // keyToNewIndexMap.set(c2[i].key, i) keyToNewIndexMap.set(c2[i], i) } // 新的总个数 const toBePatched = e2 - s2 + 1 // 记录新子节点在旧子节点中的索引 const newIndexToOldIndexMap = new Array(toBePatched).fill(0) // 循环老的子节点 for (let i = s1; i <= e1; i++) { const oldChild = c1[i] // let newIndex = keyToNewIndexMap.get(oldChild.key) let newIndex = keyToNewIndexMap.get(oldChild) // 在新子节点中不存在 if (newIndex === undefined) { // 删除oldChild // todo } else { newIndexToOldIndexMap[newIndex - s2] = i + 1 // 永远不会等于0, 这样0就能够示意须要创立了 // 持续比照其属性和子节点 // todo } } console.log(newIndexToOldIndexMap) // 须要挪动地位 // 找出最长的递增子序列对应的索引值，如：[5, 3, 4, 0] -> [1, 2] let increment = getSequence(newIndexToOldIndexMap) console.log(increment) let j = increment.length - 1 for (let i = toBePatched - 1; i >= 0; i--) { let index = i + s2 let current = c2[index] let anchor = index + 1 < c2.length ? c2[index + 1].el : null if (newIndexToOldIndexMap[i] === 0) { // 在anchor后面插入新的节点current // todo } else { if (i !== increment[j]) { // 在anchor后面插入对应旧节点.el，current.el元素等于对应的旧节点.el（在其它代码中赋值了） // todo } else { // 不变 j-- } } } }}// 调用示例patchKeyedChildren(['c', 'd', 'e', 'i', 'f', 'g'], ['e', 'c', 'd', 'f', 'g', 'j'])