Vue Diff算法处理列表重排的核心是分层策略：先头尾双端比对复用节点，再识别新增/删除边界批量操作，最后用key映射与LIS算法最小化移动次数。

Vue 的 Diff 算法处理列表重排，核心不是“算出最优移动序列”，而是用分层策略快速收敛、尽量复用、最小化真实 DOM 操作。关键不在穷举，而在分阶段收口。

先稳住头尾，跳过大量重复工作

算法启动后第一件事：从新旧列表两端同步比对节点类型和 key。

• 开头连续相同（如 [A,B] → [A,B,X,Y]），直接复用并递归 patch，不进后续逻辑
• 结尾连续相同（如 [X,Y,C,D] → [C,D]），同样跳过，只留下中间待处理段
• 这一步几乎零开销，多数业务场景增删集中在中间，头尾稳定意味着大半节点不用动

明确新增/删除边界，一次清理存在性变化

头尾剪枝后，剩余区间形成清晰缺口：

• 若旧节点还有剩余（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]

用 LIS 锁定天然有序子集，只动该动的

LIS 不是用来排序的，而是识别“本来就没乱、不用动”的节点：

• 在 newIndexToOldIndexMap 中找严格递增子序列（如 [1,3] 或 [0,2]）
• 这些下标对应的新节点，在旧 DOM 中原本就保持相对顺序，可原位复用
• 其余节点才触发 insert 或 move —— 移动次数 = 剩余节点数 − LIS 长度
• Vue3 用贪心 + 二分法实现 O(n log n)，比暴力 O(n²) 更适合长列表