哪些网站能够免费做公考题,163邮箱怎么申请企业邮箱,网站推广怎么弄,做服装有哪些好的网站有哪些目录
11.1 相同的前置元素和后置元素
11.2 判断是否需要进行 DOM 移动操作
11.3 如何移动元素
11.4 总结 我们将探讨第三种用于比较新旧子节点集合的方法#xff1a;快速Diff算法。 这种算法的速度非常快#xff0c;最早应用于 ivi 和 inferno 框架#xff0c;DOM 操作方…目录
11.1 相同的前置元素和后置元素
11.2 判断是否需要进行 DOM 移动操作
11.3 如何移动元素
11.4 总结 我们将探讨第三种用于比较新旧子节点集合的方法快速Diff算法。 这种算法的速度非常快最早应用于 ivi 和 inferno 框架DOM 操作方面的性能略优于 Vue.js 2 的双端 Diff 算法Vue3 也对其进行了借鉴和扩展。
11.1 相同的前置元素和后置元素
快速 Diff 算法包含预处理步骤这实际上是借鉴了纯文本 Diff 算法的思路。在纯文本 Diff 算法中需要对两段文本进行预处理。 例如在进行 Diff 之前可以先进行全等比较
if (text1 text2) return这称为快捷路径。如果两段文本完全相等就无需进入核心Diff算法步骤。 除此之外预处理过程还会处理两段文本相同的前缀和后缀。假设有如下两段文本
I use vue for app development
I use react for app development上面两段文本的头部和尾部分别有一段相同的内容对于内容相同的问题是不需要进行核心 Diff 操作的。因此上面两句话真正需要进行 Diff 操作的部分是
vue
react这实际上是简化问题的一种方式。这样的好处是在特定情况下我们能够轻松地判断文本的插入和删除
I like you
I like you too经过预处理去掉这两段文本中相同的前缀内容和后缀内容之后它将变成 too可以看到经过预处理后第一段的内容为空。这说明第二段的内容在第一段的基础上增加了字符串 too。
快速 Diff 算法借鉴了纯文本 Diff 算法中的预处理步骤 观察发现两组子节点具有相同的前置节点 p-1以及相同的后置节点 p-2 和 p-3 对于相同的前置节点和后置节点因为它们在新旧子节点组中的相对位置不变我们无须移动它们但仍需在它们之间打补丁。 对于前置节点我们可以建立索引 j其初始值为 0用于指向两组子节点的开头 然后开启一个 while 循环让索引 j 递增直到遇到不相同的节点为止如下代码所示
function patchKeyedChildren(n1, n2, container) {const newChildren n2.childrenconst oldChildren n1.children// 处理相同的前置节点// 索引 j 指向新旧两组子节点的开头let j 0let oldVNode oldChildren[j]let newVNode newChildren[j]// while 循环向后遍历直到遇到拥有不同 key 值的节点为止while (oldVNode.key newVNode.key) {// 调用 patch 函数进行更新patch(oldVNode, newVNode, container)// 更新索引 j让其递增joldVNode oldChildren[j]newVNode newChildren[j]}
}当 while 循环终止时索引 j 的值为 1。 这样我们就完成了对前置节点的更新如图所示 接下来我们需要处理相同的后置节点。 由于新旧两组子节点的数量可能不同所以我们需要两个索引 newEnd 和 oldEnd分别指向新旧两组子节点的最后一个节点如图所示 然后再开启一个 while 循环并从后向前遍历这两组子节点直到遇到 key 值不同的节点为止
function patchKeyedChildren(n1, n2, container) {const newChildren n2.childrenconst oldChildren n1.children// 更新相同的前置节点let j 0let oldVNode oldChildren[j]let newVNode newChildren[j]while (oldVNode.key newVNode.key) {patch(oldVNode, newVNode, container)joldVNode oldChildren[j]newVNode newChildren[j]}// 更新相同的后置节点// 索引 oldEnd 指向旧的一组子节点的最后一个节点let oldEnd oldChildren.length - 1// 索引 newEnd 指向新的一组子节点的最后一个节点let newEnd newChildren.length - 1oldVNode oldChildren[oldEnd]newVNode newChildren[newEnd]// while 循环从后向前遍历直到遇到拥有不同 key 值的节点为止while (oldVNode.key newVNode.key) {// 调用 patch 函数进行更新patch(oldVNode, newVNode, container)// 递减 oldEnd 和 nextEndoldEnd--newEnd--oldVNode oldChildren[oldEnd]newVNode newChildren[newEnd]}
}处理后置节点的方式与处理前置节点一样在 while 循环内需要调用 patch 函数进行打补丁然后递减两个索引 oldEnd、newEnd 的值处理后如图所示 上图显示处理完相同的前置和后置节点后旧子节点组已全部处理而新子节点组仍有一个未处理的节点 p-4。 实际上节点 p-4 是新增节点。怎么得出节点 p-4 是新增节点结论的呢我们需要观察索引 j、newEnd 和 oldEnd 之间的关系
oldEnd j 成立说明在预处理过程中所有旧子节点都处理完毕了。newEnd j 成立说明在预处理过后在新的一组子节点中仍然有未被处理的节点而这些遗留的节点将被视作新增节点。
如果上述两个条件同时成立说明在新的一组子节点中存在遗留节点且这些节点都是新增节点。因此我们需要将它们挂载到正确的位置如图所示 在新子节点组中需要将索引值处于 j 和 newEnd 之间的所有节点作为新子节点挂载。 为了将这些节点挂载到正确的位置我们需要找到正确的锚点元素。 观察上图我们可以知道新增节点应该挂载在节点 p-2 对应的真实 DOM 前面。 因此节点 p-2 对应的真实 DOM 节点就是锚点元素
function patchKeyedChildren(n1, n2, container) {const newChildren n2.childrenconst oldChildren n1.children// 更新相同的前置节点// 省略部分代码// 更新相同的后置节点// 省略部分代码// 预处理完毕后如果满足如下条件则说明从 j -- newEnd 之间的节点应作为新节点插入if (j oldEnd j newEnd) {// 锚点的索引const anchorIndex newEnd 1// 锚点元素const anchor anchorIndex newChildren.length ? newChildren[anchorIndex].el : null// 采用 while 循环调用 patch 函数逐个挂载新增节点while (j newEnd) {patch(null, newChildren[j], container, anchor)}}
}上述代码首先计算锚点的索引值即 anchorIndex 为 newEnd 1。 如果小于新的一组子节点的数量则说明锚点元素在新的一组子节点中所以直接使 newChildren[anchorIndex].el 作为锚点元素。否则说明索引 newEnd 对应的节点已经是尾部节点了这时无须提供锚点元素。 有了 锚点元素之后我们开启了一个 while 循环用来遍历索引 j 和索引 newEnd 之间的节点并调用 patch 函数挂载它们。
我们接下来看看删除节点的情况 我们同样使用索引 j、oldEnd 和 newEnd 进行标记如图所示 接着对相同的前置节点进行预处理处理后的状态如图 然后对相同的后置节点进行预处理处理后的状态如图 当前置和后置节点全处理完了还遗留一个节点 p-2这说明应该卸载节点 p-2。实际情况可能会有多个遗留元素如图 我们需要卸载索引 j 和 oldEnd 之间的所有节点具体实现如下
function patchKeyedChildren(n1, n2, container) {const newChildren n2.childrenconst oldChildren n1.children// 更新相同的前置节点// 省略部分代码// 更新相同的后置节点// 省略部分代码if (j oldEnd j newEnd) {// 省略部分代码} else if (j newEnd j oldEnd) {// j - oldEnd 之间的节点应该被卸载while (j oldEnd) {unmount(oldChildren[j])}}
}在这段代码中我们添加了一个 else...if 分支。当满足条件 j newEnd j oldEnd 时我们启动一个 while 循环并通过调用 unmount 函数逐个卸载这些遗留节点。
11.2 判断是否需要进行 DOM 移动操作
上一节中新旧两组子节点中总会有一组子节点全部被处理完毕。后续只需要简单的挂载和卸载节点即可我们来看一下更复杂的情况 新节点组增加了一个节点 p-7同时减少了一个节点 p-6。 在这个例子中只有 p-1 是相同的前置节点而 p-5 是相同的后置节点。 经过预处理后两组子节点的状态 可以看出新旧节点组都有部分未处理节点。此时我们需要进一步处理。 所有的 Diff 算法无论是简单的双端的还是本章介绍的快速 Diff 算法都遵循同样的规则判断是否有节点需要移动以及应该如何移动找出需要被添加或移除的节点。 接下来我们的任务就是确定哪些节点需要移动以及如何移动。在这种非理想的情况下处理完相同的前置和后置节点后索引 j、newEnd 和 oldEnd 不满足以下任何一个条件
j oldEnd j newEndj newEnd j oldEnd
因此我们需要添加一个新的else分支来处理这种情况
function patchKeyedChildren(n1, n2, container) {const newChildren n2.childrenconst oldChildren n1.children// 更新相同的前置节点和后置节点代码省略if (j oldEnd j newEnd) {// 省略部分代码} else if (j newEnd j oldEnd) {// 省略部分代码} else {// 处理非理想情况的新else分支}
}接下来我们将在这个 else 分支内编写后续的处理逻辑。 首先我们需要构造一个数组 source长度等于新节点组在预处理后剩余未处理节点的数量每个元素的初始值都是 -1 我们可以通过下面的代码完成 source 数组的构造
if (j oldEnd j newEnd) {// 省略部分代码
} else if (j newEnd j oldEnd) {// 省略部分代码
} else {// 构造 source 数组// 新的一组子节点中剩余未处理节点的数量const count newEnd - j 1const source new Array(count)source.fill(-1)
}source 数组后续将存储新节点组中的节点在旧节点组中的位置索引后面我们将使用它计算出一个最长递增子序列并用于协助完成 DOM 移动的操作。 上图展示了填充 source 数组的过程由于 source 数组存储的是新子节点在旧的一组子节点中的位置索引所以有
新的一组子节点中的节点 p-3 在旧的一组子节点中的索引为 2 因此 source 数组的第一个元素值为 2。新的一组子节点中的节点 p-4 在旧的一组子节点中的索引为 3 因此 source 数组的第二个元素值为 3。新的一组子节点中的节点 p-2 在旧的一组子节点中的索引为 1 因此 source 数组的第三个元素值为 1。新的一组子节点中的节点 p-7 比较特殊因为在旧的一组子节点中没有与其 key 值相等的节点所以 source 数组的第四个元素 值保留原来的 -1。
我们可以通过两层 for 循环来完成 source 数组的填充外层循环遍历旧节点组内层循环遍历新节点组
if (j oldEnd j newEnd) {// 省略部分代码
} else if (j newEnd j oldEnd) {// 省略部分代码
} else {const count newEnd - j 1const source new Array(count)source.fill(-1)// oldStart 和 newStart 分别为起始索引即 jconst oldStart jconst newStart j// 遍历旧的一组子节点for (let i oldStart; i oldEnd; i) {const oldVNode oldChildren[i]// 遍历新的一组子节点for (let k newStart; k newEnd; k) {const newVNode newChildren[k]// 找到拥有相同 key 值的可复用节点if (oldVNode.key newVNode.key) {// 调用 patch 进行更新patch(oldVNode, newVNode, container)// 最后填充 source 数组source[k - newStart] i}}}
}注意因为 source 数组的索引从 0 开始而未处理节点的索引可能并不从 0 开始所以在填充数组时我们使用 k - newStart 作为数组的索引值。 外层循环的变量 i 就是当前节点在旧节点组中的位置索引因此直接将 i 的值赋给 source[k - newStart] 即可。 上述代码中用于填充 source 数组的部分采用了双重循环时间复杂度为 O(n^2)n1 和 n2 分别代表新旧两组子节点的数量。 当新旧两组子节点的数量较多时这种方法可能会导致性能问题。 为了优化性能我们可以创建一个索引表来映射新子节点的 key 和位置索引这样可以避免内嵌循环降低时间复杂度至O(n)。 if (j oldEnd j newEnd) {// 省略部分代码
} else if (j newEnd j oldEnd) {// 省略部分代码
} else {const count newEnd - j 1const source new Array(count)source.fill(-1)// oldStart 和 newStart 分别为起始索引即 jconst oldStart jconst newStart j// 构建索引表const keyIndex {}for (let i newStart; i newEnd; i) {keyIndex[newChildren[i].key] i}// 遍历旧的一组子节点中剩余未处理的节点for (let i oldStart; i oldEnd; i) {oldVNode oldChildren[i]// 通过索引表快速找到新的一组子节点中具有相同 key 值的节点位置const k keyIndex[oldVNode.key]if (typeof k ! undefined) {newVNode newChildren[k]// 调用 patch 函数完成更新patch(oldVNode, newVNode, container)// 填充 source 数组source[k - newStart] i} else {// 没找到unmount(oldVNode)}}
}上述代码我们首先建立了一个索引表 keyIndex用来存储节点的 key 和节点位置索引之间的映射。 然后在第一个 for 循环中遍历新的子节点并填充索引表。在第二个 for 循环中我们遍历旧的子节点并使用索引表快速找到新子节点中对应 key 的节点位置 k如果 k 存在就进行 patch 操作并填充 source 数组如果 k 不存在就卸载旧的节点。 此外我们还需要判断节点是否需要移动。快速 Diff 算法判断节点是否需要移动的方法与简单 Diff 算法类似
if (j oldEnd j newEnd) {// 省略部分代码
} else if (j newEnd j oldEnd) {// 省略部分代码
} else {// 构造 source 数组const count newEnd - j 1 // 新的一组子节点中剩余未处理节点的数量const source new Array(count)source.fill(-1)const oldStart jconst newStart j// 新增两个变量moved 和 poslet moved falselet pos 0const keyIndex {}for (let i newStart; i newEnd; i) {keyIndex[newChildren[i].key] i}for (let i oldStart; i oldEnd; i) {oldVNode oldChildren[i]const k keyIndex[oldVNode.key]if (typeof k ! undefined) {newVNode newChildren[k]patch(oldVNode, newVNode, container)source[k - newStart] i// 判断节点是否需要移动if (k pos) {moved true} else {pos k}} else {unmount(oldVNode)}}
}上述代码我们新增了两个变量 moved 和 pos。前者的初始值为 false代表是否需要移动节点后者的初始值为 0代表遍历旧的一组子节点的过程中遇到的最大索引值 k。 如果在遍历过程中遇到的索引值呈现递增趋势则说明不需要移动节点反之则需要。所以在第二个for 循环内我们通过比较变量 k 与变量 pos 的值来判断是否需要移动节点。 除此之外我们还需要一个数量标识代表已经更新过的节点数量。 我们知道已经更新过的节点数量应该小于新的一组子节点中需要更新的节点数量。一旦前者超过后者则说明有多余的节点我们应该将它们卸载如下面的代码所示
if (j oldEnd j newEnd) {// 省略部分代码
} else if (j newEnd j oldEnd) {// 省略部分代码
} else {// 构造 source 数组const count newEnd - j 1const source new Array(count)source.fill(-1)const oldStart jconst newStart jlet moved falselet pos 0const keyIndex {}for (let i newStart; i newEnd; i) {keyIndex[newChildren[i].key] i}// 新增 patched 变量代表更新过的节点数量let patched 0for (let i oldStart; i oldEnd; i) {oldVNode oldChildren[i]// 如果更新过的节点数量小于等于需要更新的节点数量则执行更新if (patched count) {const k keyIndex[oldVNode.key]if (typeof k ! undefined) {newVNode newChildren[k]patch(oldVNode, newVNode, container)// 每更新一个节点都将 patched 变量 1patchedsource[k - newStart] iif (k pos) {moved true} else {pos k}} else {// 没找到unmount(oldVNode)}} else {// 如果更新过的节点数量大于需要更新的节点数量则卸载多余的节点unmount(oldVNode)}}
}上述代码我们增加了 patched 变量其初始值为 0代表更新过的节点数量。 接着在第二个 for 循环中增加了判断 patched count如果此条件成立则正常执行更新并且每次更新后都让变量 patched 自增否则说明剩余的节点都是多余的于是调用 unmount 函数将它们卸载。
11.3 如何移动元素
在上一节我们实现了两个关键步骤判断是否需要进行 DOM 移动操作以及构建 source 数组。 当变量 moved 为真时表示需要进行 DOM 移动操作。source 数组则用于存储新子节点在旧子节点中的位置这会帮助我们计算出一个最长递增子序列以便进行DOM移动操作。 以下代码示例展示了如何进行这种移动
if (j oldEnd j newEnd) {// 省略部分代码
} else if (j newEnd j oldEnd) {// 省略部分代码
} else {// 省略部分代码for(let i oldStart; i oldEnd; i) {// 省略部分代码}if (moved) {// 如果 moved 为真则需要进行 DOM 移动操作}
}在这段代码中我们在 for 循环后增加了一个if条件判断。如果 moved 为真则表示需要进行 DOM 移动操作我们将在此 if 语句编写相关移动的逻辑。 要进行 DOM 移动操作我们首先需要计算 source 数组的最长递增子序列。 我们先要搞清楚什么是一个序列的递增子序列。 子序列中的元素在原序列中不一定连续。一个序列可能有很多个递增子序列其中最长的那一个就称为最长递增子序列。 举个例子假设给定数值序列 [ 0, 8, 4, 12 ]那么它的最长递增子序列就是 [0, 8,12]。当然对于同一个数值序列来说它的最长递增子序列可能有多个例如 [0,4, 12] 也是本例的答案之一。 例如假设 source 数组为 [2, 3, 1, -1]。如图所示 这种情况下最长递增子序列是 [2, 3]。然后我们可以用如下的代码来求解这个子序列
if (moved) {// 计算最长递增子序列const seq lis(sources) // [ 0, 1 ]
}这段代码中我们使用了 lis 函数来计算最长递增子序列。这个函数接收 source 数组作为参数并返回其中的最长递增子序列之一。值得注意的是返回结果是最长递增子序列元素在 source 数组中的索引所以没有返回 [2, 3]。如图所示 有了最长递增子序列的索引信息后我们可以开始重新对节点进行编号如图所示 在编号时我们忽略了经过预处理的节点 p-1 和 p-5。 重新编号是为了让子序列 seq 与新的索引值产生对应关系。 最长递增子序列 seq 拥有一个非常重要的意义以上例来说子序列 seq 的值为 [0, 1]。它的含义是在新的一组子节点中重新编号后索引值为 0 和 1 的这两个节点在更新前后顺序没有发生变化。换句话说重新编号后在新的一组子节点中节点 p-3 的索引为 0节点 p-4 的索引为 1 不需要移动。 所以节点 p-3 和 p-4 所对应的真实 DOM 不需要移动。只有节点 p-2 和 p-7 可能需要移动。 为了完成节点的移动我们还需要创建两个索引值 i 和 s
用索引 i 指向新的一组子节点中的最后一个节点用索引 s 指向最长递增子序列中的最后一个元素。 接下来我们将开启一个 for 循环让变量 i 和 s 按照上图中箭头的方向移动如下面的代码所示
if (moved) {const seq lis(sources)// s 指向最长递增子序列的最后一个元素let s seq.length - 1// i 指向新的一组子节点的最后一个元素let i count - 1// for 循环使得 i 递减即按照图中箭头的方向移动for (i; i 0; i--) {if (i ! seq[s]) {// 如果节点的索引 i 不等于 seq[s] 的值说明该节点需要移动} else {// 当 i seq[s] 时说明该位置的节点不需要移动// 只需要让 s 指向下一个位置s--}}
}上述代码for 循环用于逐个访问新的节点组的节点在 for 循环内判断条件 i ! seq[s]如果节点的索引 i 不等于 seq[s] 的值则说明该节点对应的真实 DOM 需要移动否则说明当前访问的节点不需要移动。 按照上述思路执行更新。初始时索引 i 指向节点 p-7。由于节点 p-7对应的 source 数组中相同位置的元素值为 -1所以我们应该将节点 p-7 作为全新的节点进行挂载如下面的代码所示
if (moved) {const seq lis(sources)// s 指向最长递增子序列的最后一个元素let s seq.length - 1// i 指向新的一组子节点的最后一个元素let i count - 1// for 循环使得 i 递减即按照图 11-24 中箭头的方向移动for (i; i 0; i--) {if (source[i] -1) {// 说明索引为 i 的节点是全新的节点应该将其挂载// 该节点在新 children 中的真实位置索引const pos i newStartconst newVNode newChildren[pos]// 该节点的下一个节点的位置索引const nextPos pos 1// 锚点const anchor nextPos newChildren.length ? newChildren[nextPos].el : null// 挂载patch(null, newVNode, container, anchor)} else if (i ! seq[s]) {// 如果节点的索引 i 不等于 seq[s] 的值说明该节点需要移动} else {// 当 i seq[s] 时说明该位置的节点不需要移动// 只需要让 s 指向下一个位置s--}}
}上述代码如果 source[i] 的值为 -1则说明索引为 i 的节点是全新的节点于是我们调用patch 函数将其挂载到容器中。 这里需要注意的是由于索引 i 是重新编号后的因此为了得到真实索引值我们需要计算表达式 i newStart 的值。
新节点创建完毕后for 循环已经执行了一次此时索引 i 向上移动一步指向了节点 p-2如图所示 接着进行下一轮 for 循环步骤如下
source[i] 是否等于 -1很明显此时索引 i 的值为 2source[2] 的值等于 1因此节点 p-2 不是全新的节点不需要挂载它进行下一步的判断。i ! seq[s] 是否成立此时索引 i 的值为 2索引 s 的值为 1。因此 2! seq[1] 成立节点 p-2 所对应的真实 DOM 需要移动。
我们知道了节点 p-2 所对应的真实 DOM 应该移动。实现代码如下
if (moved) {const seq lis(sources)// s 指向最长递增子序列的最后一个元素let s seq.length - 1let i count - 1for (i; i 0; i--) {if (source[i] -1) {// 省略部分代码} else if (i ! seq[s]) {// 说明该节点需要移动// 该节点在新的一组子节点中的真实位置索引const pos i newStartconst newVNode newChildren[pos]// 该节点的下一个节点的位置索引const nextPos pos 1// 锚点const anchor nextPos newChildren.length ? newChildren[nextPos].el : null// 移动insert(newVNode.el, container, anchor)} else {// 当 i seq[s] 时说明该位置的节点不需要移动// 并让 s 指向下一个位置s--}}
}移动节点的实现思路类似于挂载全新的节点。不同点在于移动节点是通过 insert 函数来完成的。 接着进行下一轮的循环。此时索引 i 指向节点 p-4如图所示 更新过程仍然分为三个步骤
判断表达式 source[i] 的值是否等于 -1很明显此时索引 i 的值为1表达式 source[1] 的值等于 3条件不成立。所以节点 p-4 不是全新的节点不需要挂载它。接着进行下一步判断。判断表达式 i ! seq[s] 是否成立此时索引 i 的值为 1索引 s 的值为 1。这时表达式 1 seq[1] 为真所以条件 i ! seq[s] 也不成立。由于第一步和第二步中的条件都不成立所以代码会执行最终的 else 分支。这意味着节点 p-4 所对应的真实 DOM 不需要移动但我们仍然需要让索引 s 的值递减即 s--。
经过三步判断之后我们得出结论节点 p-4 不需要移动。于是进行下一轮循环此时的状态如图 此时索引 i 指向节点 p-3。我们继续进行三个步骤的判断
判断表达式 source[i] 的值是否等于 -1很明显此时索引 i 的值为 0表达式 source[0] 的值等于 2所以节点 p-3 不是全新的节点不需要挂载它接着进行下一步判断。判断表达式 i ! seq[s] 是否成立此时索引 i 的值为 0索引 s 的值也为 0。这时表达式 0 seq[0] 为真因此条件也不成立最终将执行 else 分支的代码也就是第三步。到了这里意味着节点 p-3 所对应的真实 DOM 也不需要移动。
在这一轮更新完成之后循环将会停止更新完成。
如下是用于求解给定序列的最长递增子序列的代码取自 Vue.js 3
function getSequence(arr) {const p arr.slice()const result [0]let i, j, u, v, cconst len arr.lengthfor (i 0; i len; i) {const arrI arr[i]if (arrI ! 0) {j result[result.length - 1]if (arr[j] arrI) {p[i] jresult.push(i)continue}u 0v result.length - 1while (u v) {c ((u v) / 2) | 0if (arr[result[c]] arrI) {u c 1} else {v c}}if (arrI arr[result[u]]) {if (u 0) {p[i] result[u - 1]}result[u] i}}}u result.lengthv result[u - 1]while (u-- 0) {result[u] vv p[v]}return result
}11.4 总结
快速 Diff 算法在实测中性能最优。它借鉴了文本 Diff 中的预处理思路先处理新旧两组子节点中相同的前置节点和相同的后置节点。 当前置节点和后置节点全部处理完毕后如果无法简单地通过挂载新节点或者卸载已经不存在的节点来完成更新则需要根据节点的索引关系构造出一个最长递增子序列。最长递增子序列所指向的节点即为不需要移动的节点。
