双端Diff算法为Vue2采用的算法，而在Vue3中则采用了性能要更要一些的快速Diff算法（稍优）。

简单来说，快速Diff算法分为三大部分：

1. 从新旧节点的头部开始循环对比，只要碰到两个节点不一致，则跳出循环，并记录跳出位置
2. 从新旧节点的尾部开始循环对比，只要碰到两个节点不一致，则跳出循环，并记录跳出位置
3. 处理完首尾之后，剩余中间部分处理新增、删除、排序等

首尾Diff比较简单，不需要做太多说明，主要是剩下的中间的部分处理。

纯新增节点处理

如删除，diff完新旧节点后，新节点还多出为遍历完的节点（旧节点直接遍历完了），那就剩下纯新增节点逻辑了。此时判断oldEnd < j && newEnd >= j 成立，则只需要新增剩下的新子节点即可。

function patchKeyedChildren(n1, n2, container) {
  const newChildren = n2.children
  const 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)
    }
  }

}

纯删除旧子节点的情况

如上图，新子节点已经遍历完，而旧子节点仍有节点未遍历，这就是需要将旧子节点都卸载掉。判断条件为j > newEnd && j <= oldEnd 。

function patchKeyedChildren(n1, n2, container) {
  const newChildren = n2.children
  const oldChildren = n1.children
  // 更新相同的前置节点
  // 省略部分代码

  // 更新相同的后置节点
  // 省略部分代码

  if (j > oldEnd && j <= newEnd) {
    // 省略部分代码
  } else if (j > newEnd && j <= oldEnd) {
    // j -> oldEnd 之间的节点应该被卸载
    while (j <= oldEnd) {
      unmount(oldChildren[j++])
    }
  }

}

判断是否需要进行DOM移动操作

最麻烦的是，新节点与旧节点都未遍历完。这时候需要在剩余节点中做排序操作。

也就是如下图的状态：

而快速Diff算法为了降低复杂度，会先将新子节点生成一份其在旧子节点列表中的索引表。默认值为-1，实际值为其对应的元素在旧子节点里面的索引。如果其在旧子节点中没有对应的元素，则表示是新增的元素，那么索引就是默认值-1.

如下图