VUE 的 diff 算法对比

• 双端对比

需要四个索引值，分别指向新旧两组子节点的端点

1. 头头比较：首先是老的节点数组的头结点和新节点数组的头节点进行比较，如果相同（说明当前节点为发生变化，无需修改虚拟DOM），则老的节点和新的节点同时向后移动一位，再进行比较；如果不相同，则启动尾尾比较。
2. 尾尾比较：老的节点数组的尾结点和新节点数组的尾节点进行比较，如果相同，则两者都向前移动一位，之后老的节点数组右移，新节点数组左移，再进行比较；如果不相同，则进行头节点和尾节点比较。
3. 头尾比较：老的节点数组的头节点和新的节点数组的尾节点比较，如果相同，说明老的节点在新节点数组中被移动到最后一位了，就把老的头节点放到最后，再进行比较；如果如果不相同，则进行尾节点和头节点比较。
4. 尾头比较：新的节点数组的头节点和老的节点数组的尾节点比较，如果相同，说明老的节点在新节点数组中被移动到第一位了，就把老的头节点放到最开头，之后老的节点数组左移，新节点数组右移，再进行比较；如果前四步都走完还不匹配，则进入else的兜底判断。
5. 拿着新的新节点的当前的key，遍历老节点数组，找有没有相同的key，如果有，则把老数组中的对应节点放到新的数组中对应key值的Index处，如果没匹配到，就直接创建新节点。

• 快速 diff
  1. 头序比较算法，老节点数组和新节点数组的头结点相互比较，如果相同，则同时后移，直到比较到发现不同的情况为止，此时启动尾序比较算法。
  2. 尾序比较算法，即老节点数组和新节点数组的尾结点相互比较，如果相同，则同时前移，也是直到比较到发现不同的情况为止。
  3. 判断，此时如果新节点数组中有节点但老节点数组中没有节点，则创建一个新节点插入对应位置。
  4. 如果老节点数组中存在的节点在新的节点数组中不存在，则卸载掉老的节点。
  5. 上述四步结束过后就会剩下一些乱序节点，即节点既存在老的节点数组，又存在于新的节点数组，只不过节点所在的位置发生了变化，因此只需要找到老节点在新节点数组中的位置并把它移动过去就可以了，也就是在这里，vue3使用了最长递增子序列，先固定一个最长的不需要移动的数组，在把不在这个最长递增子序列中的节点外的乱序节点插入其中，以实现最小的移动消耗就能实现最终的效果。