Vue3 Diff算法采用分层策略：先双端比对复用首尾相同节点；再批量处理新增/删除；最后用key映射+LIS优化乱序移动，将时间复杂度降至O(n log n)。
Vue3 的 Diff 算法不是单点突破，而是一套分层递进的策略组合。它把列表更新拆解为可预测、可跳过、可加速的多个阶段，最长递增子序列（LIS）只是压轴环节，专治最棘手的乱序移动问题。
前序与后序双端比对：快速收口相同结构
这是算法最先执行、也最常命中的步骤。它从新旧子节点数组的头尾同时推进，逐个比对类型和 key：
- 开头连续匹配的节点（如
[A,B,...]vs[A,B,X,...]），直接复用并递归 patch，不进入后续逻辑 - 结尾连续匹配的节点（如
[...,C,D]vs[X,...,C,D]），同样跳过，大幅压缩待处理区间 - 该阶段时间复杂度接近 O(1) 到 O(k)，k 是公共前后缀长度；多数真实场景下，增删只发生在中间，因此这一步就解决了大半工作
新增与删除节点：明确边界，一次清理
双端比对结束后，剩余未匹配的节点形成清晰的“缺口”：
- 若旧节点还有剩余（
e1 > i-1），说明这些节点在新列表中已消失，批量卸载 - 若新节点还有剩余（
e2 > i-1），说明是全新插入，按顺序挂载即可 - 这个过程不依赖 key 查找，也不触发移动，开销极低；它处理的是“存在性变化”，而非“位置重排”
Key 驱动的乱序映射：构建位置关系图
当剩余新旧节点数量相等但顺序错乱时（如 [1,3,4,2] → [1,2,3,4]），算法进入核心优化环节：
- 先建立
oldKeyToIndex哈希表：遍历旧列表，记录每个 key 对应的最后索引 - 再生成
newIndexToOldIndexMap数组：遍历新列表，对每个节点查其在旧列表中的位置，找不到则记为 0（代表新节点） - 例如新列表
[b,a,d,c]对应旧列表[a,b,c,d]，得到位置数组[1,0,3,2]（a 在旧列表索引 0，b 在索引 1，c 在 2，d 在 3）
最长递增子序列（LIS）：锁定最少移动方案
LIS 不是用来排序的，而是用来识别“天然有序、无需移动”的节点子集：
- 在
newIndexToOldIndexMap中找严格递增子序列（如[1,3]或[0,2]），这些对应的新节点在旧 DOM 中原本就保持相对顺序，可原位复用 - Vue3 使用贪心 + 二分法构造
tails数组，并通过前驱链反推出 LIS 所含的新节点下标 - 其余下标对应的新节点，则按需执行 insert 或 move 操作——移动次数 = 剩余节点数 − LIS 长度
- 该步骤将乱序更新的时间复杂度从 O(n²) 降至 O(n log n)，对长列表效果显著
