在做diff算法之前有个基本逻辑要明白，Vue的diff算法是同层比较，不会跨层比较，时间复杂度为O(N)。

主要使用首尾比较法（头-头，头-尾，尾-头，尾-尾）。Vue2与Vue3的diff算法主要区别是处理完首尾节点后，对剩余节点的处理方式。

Vu2简单diff算法

简单diff是基于递归来实现的，它适用于对比树形数据结构之间的差异

vue2.x就是使用的简单diff算法

实现思路是递归比较两个树的每个节点，如果两个节点相同，就比较它们的子节点，如果不同，就标记为删除或添加，并且停止递归

缺点的话就是只能比较树形数据结构，不能比较其他数据结构

Vue2 diff算法过程

新旧虚拟DOM分别创建首尾两个指针

依次头-头，头-尾，尾-头，尾-尾（startIndex1,startIndex2,endIndex1,endIndex2）比较，若在比较过程中发现指向的节点内容一致，则直接复用旧结点作为diff创建的节点。若这四种情况都不满足，则diff将创建当前新虚拟DOM的节点插入到diff队列后面，并且将新虚拟DOM的startIndex2指向下一个节点。

当其中一条虚拟DOM的endStart < startIndex，比较结束。

随后根据新老节点的数目，来进行插入或删除操作。若新节点数目大于老节点则需要把多出来的节点创建出来加入到真实 DOM中，反之若老节点数目大于新节点则需要把多出来的老节点从真实 DOM中删除。

至此整个 diff 过程就已经全部完成了。

Vue3双端diff算法

双端diff算法是简单diff算法的优化版本，是比较两个数组之间的差异，可以在不使用递归的情况下比较数组，从而提高效率。它可以处理更复杂的场景，比如移动了元素

vue3.x就是使用的双端diff算法

实现思路是从数组两端开始遍历，比较相邻元素是否相同，相同则比较下一对元素；如果不同，就标记为删除或添加，并继续遍历

缺点的话就只能比较序列类型数据结构，不能比较树形数据结构

Vue3 diff算法过程

新旧节点从头开始比较，相同直接复用执行patch，直到比较到两节点不同为止。新旧节点从尾开始比较，相同直接复用执行patch，直到比较到两节点不同为止。

处理完以上两种情况，剩下3种情况。老节点先遍历完，新节点还剩余：创建剩余新节点。新节点先遍历完，老节点还剩余：删除剩余旧节点。新老节点都有剩余：在新老剩余节点中寻找可复用节点。创建新节点剩余节点对应的映射表keyToNewIndexMap。再创建一个数组newIndexToOldIndexMap，用来存储新节点数组中的剩余节点在旧节点数组上的索引，后面将使用它计算出一个最长递增子序列，并初始化数组为0。

遍历老节点，存储新节点数组中的剩余节点在旧节点数组上的索引。

计算newIndexToOldIndexMap数组，得到最长增长子序列（贪心 + 二分）。

-

遍历新节点，根据最长增长子序列进行移动、添加、删除节点。第一个节点为h，在newIndexToOldIndexMap中值为0，说明是新增的节点，创建。第二个节点为e，索引为3，与最长增长子序列中3命中，跳过。第三个节点为d，索引为2，与最长增长子序列中2命中，跳过

第四个节点为c，索引为1，与最长增长子序列中1命中，跳过。第五个节点为f，索引为0，均不符合，进行hostInsert，将节点f的真实dom移动到节点nextChild节点c的前面。遍历结束完成 。