专栏第十篇-双端对比算法

上节我们说到Vue是异步批量更新的，本质上就是调用 watcher的run方法，然后调用实例上的_update方法进行重新渲染。

一、diff算法

1.1 前世今生

前世：diff 算法最初是由计算机科学家迈克尔·菲舍尔和丹尼尔·希尔伯特所发明的一种文本比较算法。

今生：伴随着前端开发的蓬勃兴起，diff 算法被引入到虚拟 DOM 当中，成为了一项用于高效更新用户界面的核心技术。其旨在高效地辨别出从一种状态转变为另一种状态所需要的最小变更集合。由于在浏览器中对 DOM 进行操作的性能消耗颇为昂贵，例如节点的添加、删除等等，所以 diff 算法能够尽可能地降低 DOM 的操作数量，避免频繁的 DOM 操作所带来的性能耗费，进而减轻浏览器的性能负担。

如上图所示。如果需要将上图中左边的DOM树更新为右边的DOM树，在不采用虚拟DOM的情况下（即无法复用DOM节点），可能需要进行6次DOM操作：

卸载所有旧子节点，需要 3 次 DOM 删除操作。
挂载所有新子节点，需要 3 次 DOM 添加操作。

但是如果采用diff算法复用DOM节点的策略进行的话，实际上只需要进行1次DOM操作：

移动旧的一组子节点的B节点到C节点的后面。

可以看出来通过复用策略可以有效的避免频繁操作DOM带来的性能开销。

1.2 diff算法的复杂度

对两棵树进行 diff 操作，其复杂度为 O(n^3) 。

这是因为每个节点都需要和另一棵树的所有节点逐一进行对比，这便形成了 n 的复杂度。

倘若找到有变化的节点，执行插入、删除、修改操作同样具有 n 的复杂度。

所有的节点均是如此，再乘以 n ，因此得出的复杂度是 O(n * n * n) 。

如此的复杂度对于前端框架而言是无法接受的，这意味着若存在 1000 个节点，渲染一次就需要处理 1000 * 1000 * 1000，总计 10 亿次。

所以前端框架的 diff 约定了两种处理原则：1.只做同层的对比 2.type 变了就不再对比子节点。

因为 DOM 节点进行跨层级移动的情形相对较少，通常情况下都是同一层级的 DOM 的增删改操作。

像这样的话，只需遍历一次，对比一下 type 就可以了，其复杂度是 O(n) 。而且一旦 type 发生变化，就不再对比子节点，能够节省下大量节点的遍历工作。另外，由于在虚拟 DOM 中记录了关联的 DOM 节点，执行 DOM 的增删改操作时也无需遍历，其复杂度是 O(1) 。整体的 diff 算法复杂度即为 O(n) 。

1.3 diff算法的核心要素

1.3.1 同层比较

如上图所示，算法会于两个虚拟 DOM 树的同一层级展开对比，而不会进行跨层级的对比。这代表着它首先会核查每个父节点是否一致，如果一致，接下来才会递归进入子树进行比较。倘若不同，则直接依据具体情况进行更新。

由之前的章节能够了解到：双端 diff 算法被设计为只有同层节点进行比较，其原因主要有以下两点：

降低 diff 算法的复杂程度。
DOM 节点进行跨层级移动的情况相对较少，通常情况下都是同一层级的 DOM 的增删改操作。

1.3.2 相同节点判断策略

如上图所示。在 Vue 中，判断新旧节点是否为相同节点的逻辑为：当节点的标签（比如 p 节点）以及节点的key相同时，即被视为同一个节点。之所以这样做，是因为一旦 type 或者 key 发生变化，就不再对比子节点，能够节省下大量节点的遍历工作，从而提升性能。

1.3.3 循环从两边向中间比较

这是一种优化策略，算法不是线性遍历每一个节点，而是从两端开始，向中间逐步靠拢，这样可以在某些情况下更早地发现差异并终止不必要的比较。

第一步：比较旧的一组子节点中的第一个子节点A与新的一组子节点中的第一个子节点C。
第二步：比较旧的一组子节点的最后一个子节点C与旧的一组子节点的最后一个子节点B。
第三步：比较旧的一组子节点的第一个子节点A与新的一组子节点中的最后一个子节点 B。
第四步：比较旧的一组子节点的最后一个子节点 C与新的一组子节点的第一个节点C。

1.3.4 节点复用

在diff算法中，节点复用是一个非常重要的优化手段。通过复用旧节点，可以大大减少DOM操作，从而提升渲染效率。

Vue.js团队通过引入key的概念，实现了节点复用的功能。key是一个唯一的标识符，它可以帮助Vue.js区分不同的节点。当新旧节点的key相同时，Vue.js就会复用旧节点，而不是创建新节点。

在没有key的情况下，判断下面的p节点属于同一个节点，直接进行子节点的对比，子节点是文字，则直接更新文字。（这里因为没有key值无法进行复用，复用的话只需要移动A节点的位置即可）。

在存在key的情况下，使用双端 diff的四步对比进行。

第一步，在有key的情况下，判断不属于同个节点，跳过
第二步，在有key的情况下，判断不属于同个节点，跳过
第三步，在有key的情况下，判断属于同个节点，进行节点复用操作（具体操作后续会说）

二、虚拟 DOM和 diff算法的关联

在专栏第六篇中，我们介绍了虚拟DOM。

我们知道虚拟DOM在 JS中就是一个普通的 JS对象，这个对象的结构是一种可以表示DOM的抽象层面的树形结构，它可以高效地更新到实际的DOM上。

在Vue中，每个组件都有一个对应的渲染函数，这个函数返回一个描述该组件视图的虚拟节点树。

在初次渲染时，会调用渲染函数生成一个虚拟节点树oldVNode。

当组件的状态发生变化时，渲染函数会被再次调用，产生一个新的虚拟节点树newVNode。

Vue的diff算法就是用来比较新旧虚拟节点树的差异，找出最小的DOM操作来更新实际的DOM。

所以 Vue的 diff只会发生在更新阶段。初次挂载直接创建并挂载节点。

// 假设有一个简单的组件
let component = {
  data: 'Hello, Vue!',
  template: `<div>{{ data }}</div>`
};
 
// 首次渲染，生成虚拟DOM
let oldVnode = Vue.render(component);
 
// 假设数据（data）更新，产生新的虚拟DOM
let newVnode = Vue.render(component);
 
// Vue的diff算法比较新旧虚拟DOM
let patches = Vue.diff(oldVnode, newVnode);
 
// 根据diff结果应用到实际DOM
Vue.patch(document.body, patches);

在这个例子中，Vue首次渲染组件时生成了一个虚拟DOM节点（oldVnode）。当组件的数据更新时，Vue再次渲染组件，生成了一个新的虚拟DOM节点（newVnode）。Vue的diff算法会比较这两个虚拟节点，找出需要执行的最小DOM操作（patches），最后这些DOM操作会被应用到实际的DOM上，以此来更新视图。

三、 snabbdom简介

Snabbdom是瑞典语单词，原意为”速度“。是一个轻量级的虚拟DOM和DOM diff算法库，它被设计用于以非常高效的方式更新真实DOM。Vue.js在2.x版本中采用了虚拟DOM的概念来提高其性能和效率，而Vue 2.x内部使用的虚拟DOM实现实际上是在Snabbdom的基础上进行了一些定制和改造的。

Vue团队选择Snabbdom作为其虚拟DOM实现的原因主要是因为Snabbdom的高性能特性和小巧的体积。它提供了一个简洁的API来创建和管理虚拟节点（vnodes），并通过高效的diff算法来计算出虚拟DOM树的最小变更集，进而只对实际DOM进行必要的更新，减少了不必要的DOM操作，提高了页面的渲染效率。

vue2源码中更新基本和snabbdom中一致，部分边角细节不一致，所以我们看一下snabbdom源码大致就可以了解Vue更新的细节。

github地址：https://github.com/snabbdom/snabbdom

import {
  init,
  h
} from "snabbdom";

// 调用 init生成 patch渲染函数
const patch = init([]);

const container = document.getElementById("container");

const myVnode = h('div',[
    h('p','苹果'),
    h('p','香蕉'),
    h('p','火龙果'),
]);

const myVnode2 = h('div',[
    h('p','苹果'),
    h('p','香蕉'),
    h('p','桃子'),
])

// 第一个参数为 DOM节点
// 第二个参数为 VNODE节点
// 表示第一次执行挂载操作
patch(container, myVnode);

document.getElementById('btn').addEventListener('click',()=>{
    // 第一个参数为 DOM节点
    // 第二个参数为 VNODE节点
    // 表示执行更新操作
    patch(myVnode, myVnode2);
})

界面上渲染效果如下所示：

点击按钮后：

由之前的diff算法可知，当点击更新以后，界面上会复用前两个元素苹果和香蕉(即没有销毁以及重新创建)，那么如何证明它复用了呢，其实很简单，只需要在浏览器中手动更改前2个元素，如果点击更新以后，更改的前2个元素没有变化，即可证明它并对dom节点进行了复用。

如上代码所示，patch即为vue中的第一次渲染，点击按钮更新新的vnode相当于vue中的更新渲染，只不过vue中将行为进行了一些封装。所以掌握snabbdom即可掌握vue2的核心双端diff算法。

四、更新渲染

在专栏第六篇中我们已经学习了首次渲染，首次渲染没有旧节点，所以不需要进行节点对比，直接创建元素并挂载就可以了。

这节会补充相同节点进行更新渲染的相关逻辑。下图是更新渲染重要函数patchVNode的关键流程图。

存在 text即为文本节点，文本节点没有 tag，只有 text。

4.1 为什么更新函数patchVNode叫做打补丁？

function patch(oldVNode,newVNode){
    // 省略代码
    if(sameVnode(oldVNode,newVNode)){
        // 进行精细化比较
        patchVnode(oldVNode, newVNode);
    }else{
        // 粗暴更新
    }
}

在新旧虚拟节点相同的情况下下，渲染器会使用新的虚拟节点与旧的虚拟节点进行比较，试图找到并更新变更点。这个过程叫做“打补丁”，英文通常用patch来表达。

“打补丁”这个词形象地描述了patchVnode函数在vue框架中的工作方式。在计算机领域，“打补丁”通常指的是对现有程序或数据进行局部修改或修复，而不必完全重写或替换整个内容。patchVnode也是基于类似的理念工作的

最小化变更：当Vue的数据变化时，它需要决定如何将这些变化反映到界面上。patchVNode通过对比新旧虚拟DOM树（VNode），仅对发生改变的部分进行操作，这就像是在原有的DOM结构上打上“补丁”，而不是重建整个DOM树。这种做法极大地减少了实际的DOM操作，提高了性能。
精确更新:就像衣服破了洞，只需要在破洞处缝上一小块布料（补丁）即可修复，而不是制作一件新衣服。同样，Vue在更新界面时，只针对有差异的部分进行精确更新，这就是“打补丁”的过程。

4.2 进行dom的复用

4.2.1 浏览器中的DOM

DOM并不是存储在硬盘上作为文件的一部分，而是作为浏览器解析HTML后在JS引擎的内存空间里创建的一个对象模型。开发者可以通过JS来访问和修改这个内存的DOM，从而实现对网页内容的动态操作，比如添加、删除、修改DOM元素或应用样式等。用户看到的页面变化，实际上是浏览器根据内存中的DOM的状态重新渲染页面的结果。

浏览器的DOM结构存储在JS的堆内存中。堆内存是用来存储复杂数据结构如对象和数组的地方，DOM树作为对象的集合，自然也被存储在这里。每当一个网页被加载，浏览器就会在堆内存中创建一个与之对应的DOM树结构。

4.2.2 旧的vnode指向内存中的真实DOM

在挂载阶段创建节点时，会将vnode中的elm属性指向内存的创建的真实DOM。如下代码所示。

function createElm(vnode){
    const tag = vnode.tag;
    const data = vnode.data;
    // 省略部分代码
    const elm = nodeOps.createElement(tag, data);

    vnode.elm = elm;
}

所以在更新渲染时，很容易通过旧的vnode中的elm属性来获取真实DOM。

4.2.3 新的vnode elm复用老的vnode elm

由上可知，老的vnode指向了真实DOM，那么如果想复用可以将新的vnode也指向内存中的真实DOM即可，具体代码如下：

function patchVnode(oldVNode,vnode){
    // 复用旧节点的 DOM
    const elm = vnode.elm = oldVNode.elm;
}

上面的代码将新的虚拟节点的elm属性也指向了内存中的真实DOM，同时也创建了一个elm变量指向真实DOM。方便后续代码中使用这个真实的DOM元素。

此时新旧虚拟节点和真实DOM的状态如下图所示。

4.3 获取新老节点的子节点

因为后续需要依据新节点和老节点的子节点信息来进行一些逻辑处理，所以要先获取他们的子节点信息方便后续处理。

function patchVnode(oldVNode,vnode){
    // 省略部分代码
    const oldCh = oldVNode.children;
    const ch = vnode.children;
}

4.4 判断新虚拟节点是文本节点

通过if判断和vnode.text === undefined可以判断出新的虚拟节点是文本节点。

如果新的虚拟节点是文本节点，则旧的虚拟节点同样也是文本节点。

所以当新旧文本节点文本不同时，直接更新即可。

function patchVnode(oldVNode,vnode){
    // 非文本节点
    if(vnode.text === undefined){
        // 省略部分代码
    }
    // 文本节点 
    else if(oldVNode.text !== vnode.text){
        // 文本变化，直接更新
        nodeOps.setTextContent(elm, vnode.text)
    }
}

通过 vnode.text === undefined 来判断不是一个文本节点。所以else就代表它是一个文本节点。
判断 oldVNode.text和vnode.text是否相等;如果想等，不需要更新。如果不相等，意味着文字发生了变化，直接调用setTextContent更新节点上的文本信息。

4.5 判断新虚拟节点是非文本节点

上小节我们说到判断新虚拟节点是非文本节点的方法是vnode.text === undefined。

4.5.1 当新旧虚拟节点都存在子节点时

当新旧节点都有子节点时，这种情况最复杂，需要使用到双端diff算法，后续我们会详细说明。

function patchVnode(oldVNode,vnode){
    // 非文本节点
    if(vnode.text === undefined){
        if(oldCh !== undefined && ch !== undefined){
            //双端diff算法 待实现
            updateChildren(elm, oldCh, ch)
        } 
    }
}

4.5.2 当新虚拟节点存在子节点 & 旧虚拟节点不存在子节点

当新虚拟节点有子节点，旧虚拟节点没有子节点时，可以将新节点的子节点创建出来的DOM直接挂载到DOM上。

function patchVnode(oldVNode,vnode){
    // 非文本节点
    if(vnode.text === undefined){
        if(oldCh !== undefined && ch !== undefined){
            // 省略部分代码
        }else if (ch !== undefined) {
            // 目前还想不到这行代码的实际应用场景
            if (oldVNode.text !== undefined) api.setTextContent(elm, "");
            // 增加子节点
            addVnodes(elm, null, ch, 0, ch.length - 1);
        }
    }
}

第一个if中判断了新旧虚拟节点中都存在子节点。
第二个if中判断了新虚拟节点存在子节点，那么可以知道这个分支判断的是新节点存在子节点，但是旧节点不存在子节点。
如果新节点中存在子节点，但是旧节点中不存在子节点，说明需要将新节点的子节点创建出来的DOM直接挂载到DOM上。这里添加了一个判断就是如果旧节点是文本节点，需要先清除DOM中的文本元素，再添加新的dom，但是目前没有发现具体的使用场景。
addVnodes 函数和removeVnodes类似，目的是将一系列虚拟节点（VNodes）添加到DOM树中的指定位置，核心依赖insertBefore api。

4.5.3 当新虚拟节点没有子节点 & 旧虚拟节点节点有子节点

当新虚拟节点没有子节点，旧虚拟节点有子节点时，需要在DOM中将旧节点的子节点清除。

function patchVnode(oldVNode,vnode){
    if(vnode === undefined){
        if (oldCh !== undefined && ch !== undefined) { 
            // 省略部分代码
        } else if(ch !== undefined){
            // 省略部分代码
        } else if(oldCh !== undefined){
            removeVnodes(elm, oldCh, 0, oldCh.length - 1);
        }
    }
}

第一个if中判断了新旧节点中都存在子节点。
第二个if中判断了新节点存在子节点，但是旧节点不存在子节点。
所以可以得出第三个if中判断了新节点不存在子节点，但是旧节点存在子节点，所以需要清除DOM元素中的旧节点中的子节点。

4.5.4 新虚拟节点没有子节点且没有文字节点 & 旧虚拟节点有文字节点

新虚拟节点没有子节点且没有文字节点，旧节点有文字节点需要清除节点。

function patchVnode(oldVNode,vnode){
    if(vnode === undefined){
        if (oldCh !== undefined && ch !== undefined) { 
            // 省略部分代码
        } else if(ch !== undefined){
            // 省略部分代码
        } else if(oldCh !== undefined){
            // 省略部分代码
        } else if(oldVNode.text !== undefined){
            api.setTextContent(elm, "");
        }
    }
}

第一个if中判断了新旧节点中都存在子节点。
第二个if中判断了新节点存在子节点，旧节点不存在子节点。
第三个if中判断了新节点没有子节点，旧节点有子节点。
所以很容易知道oldVNode.text !== undefined表示的是旧节点是文本节点，且新节点没有子节点。故直接清除节点中的文字即可。

五、双端diff核心函数-updateChildren

在新旧虚拟节点打补丁时，当遇到新虚拟节点和旧虚拟节点都有子节点时，需要进行diff对比。

双端diff算法利用虚拟节点的key属性，尽可能的复用DOM元素，并通过移动DOM的方式来完成更新，从而减少不断地创建和销毁DOM元素带来的性能开销。

5.1 双端比较的四个关键索引值

双端diff算法是一种同时对新旧两组子节点的两个端点进行比较的算法。因此，我们需要四个索引值，分别指向新旧两组子节点的端点。如下图所示：

后面的图片事例中，菱形代表新节点；方形代表老节点；圆形代表真实DOM；虚线代表当前元素已经被处理过。p代表节点的标签，1、2、3、4代表节点的key，“-“ 起连接作用。

5.1.1 头部节点和尾部节点

位置newStartIdx指向的节点代表新的一组子节点的头部节点。
同理位置oldStartIdx指向的节点代表旧的一组子节点的头部节点。
位置newEndIdx指向的节点代表新的一组子节点的尾部节点。
同理位置oldEndIdx指向的节点代表旧的一组子节点的尾部节点。

5.1.2 代码实现

定义了一些索引值以及对应的虚拟节点。

、function updateChildren(parentElm,oldCh,newCh){
        // 旧的一组子节点的头部节点索引值
        let oldStartIdx = 0;
        // 旧的一组子节点的尾部节点索引值
        let oldEndIdx = oldCh.length - 1;
        // 新的一组子节点的头部节点索引值
        let newStartIdx = 0;
        // 新的一组子节点的尾部节点索引值
        let newEndIdx = newCh.length - 1;

        // 旧的一组子节点的头部节点
        let oldStartVnode = oldCh[0];
        // 旧的一组子节点的尾部节点
        let oldEndVnode = oldCh[oldEndIdx];
        // 新的一组子节点的头部节点
        let newStartVnode = newCh[0];
        // 新的一组子节点的尾部节点
        let newEndVnode = newCh[newEndIdx]; 
}

5.2 老vnode引用真实DOM

在初次渲染完成后，所有虚拟节点中都保存了真实 DOM的引用，可以通过 elm属性获取对应的真实 DOM。

所以在更新渲染前，所有旧的一组子节点中都存储真实DOM的引用。如下图所示。

5.3 双端比较的方式

在双端比较中，每一轮都分为四个步骤，如上图中的连线所示。

第一步：比较旧的一组子节点中的头部节点P-1与新的一组子节点中的头部节点P-4，看看它们是否相同。由于两者的key值不同，因此不相同。不可复用，于是什么都不做，直接跳过。
第二步：比较旧的一组子节点中的尾部节点P-4与新的一组子节点中的尾部节点P-3，看看他们是否相同。由于两者的key值不同，因此不相同。不可复用，于是什么都不做，直接跳过。
第三步：比较旧的一组子节点中的头部节点P-1与新的一组子节点中的尾部节点P-3，看看它们是否相同。由于两者的key值不同，因此不相同。不可复用，于是什么都不做，直接跳过。
第四步：比较旧的一组子节点中的尾部节点P-4与新的一组子节点中的头部节点P-4，看看它们是否相同。由于它们的key值相同，因此可以进行DOM复用。

直至找到了相同的一组子节点，他就会对节点做相应的处理，然后将对应的指针向没有处理过的节点方向移动，再次进行上述方式的比较。比如这里就是newStartId指针向下移动，而oldEndIdx指针向上移动。如下图所示。

下图中边框虚线表示已经处理过的元素。

newStartIdx指针向下移动，所以新子节点的头部节点变成了P-2。
oldEndIdx指针向上移动，所以旧子节点的尾部节点变成了P-3。

依旧重复双端diff的四个步骤：

第一步：比较旧的一组子节点中的头部节点P-1与新的一组子节点中的头部节点P-2是否相同。由于两者的key不同，因此不相同。不可复用，于是什么都不做，直接跳过。
第二步：比较旧的一组子节点中的尾部节点P-3与新的一组子节点中的尾部节点P-3是否相同。由于它们的key相同，因此可以进行DOM复用。

因为已经在第二步中找到了，所以将newEndIdx指针向上移动，oldEndIdx向上移动。如下图所示。

newEndIdx指针向上移动，所以新子节点的尾部节点变成了P-1。
oldEndIdx指针向上移动，所以旧子节点的尾部节点变成了P-2。

由于还没有结束对比，依旧重复下面四个步骤：

第一步：比较旧的一组子节点中的头部节点P-1与新的一组子节点中的头部节点P-2是否相同。由于两者的key不同，因此不相同。不可复用，于是什么都不做，直接跳过。
第二步：比较旧的一组子节点中的尾部节点P-2与新的一组子节点中的尾部节点P-1是否相同。由于两者的key不同，因此不相同。不可复用，于是什么都不做，直接跳过。
第三步：比较旧的一组子节点中的头部节点P-1与新的一组子节点中的尾部节点P-1是否相同。由于两者的key相同，因此可以进行DOM复用。

新旧两组节点中各还有一个节点没有比完。有的人会产生疑问，为啥要对比P-1和P-1不是一样的吗？对于程序来说，还没有移动指针，所以它是不清楚是否是相同节点的，所以还需要继续对比，将newEndIdx向上移动，oldStartIdx向下移动。

newEndIdx指针向上移动和newStartIdx重合，所以新子节点的头部节点和尾部相同，都是P-1。
oldStartIdx指针向下移动和oldEndIdx重合，所以旧子节点的头部节点和尾部节点相同，都是P-1。

此时对比还没有结束，依次重复双端diff的四个步骤：

第一步：比较旧的一组子节点中的头部节点P-1与新的一组子节点中的头部节点P-1是否相同。由于两者的key相同，因此可以进行DOM复用。

至此，所有的节点已经对比完毕。（节点复用的具体操作我们后面会说）。大致来说，diff算法是基于这四步进行比较的。

5.3.1 第三步和第四步顺序容易搞混？

第三步比较和第四步比较对应的是双端中的“X”位置，很多人容易把它们的顺序给弄混淆。

你只需要记得是双端diff的逻辑是拿旧节点和新节点进行对比，所以需要先从旧节点的头部节点开始对比。

5.4 双端比较的循环条件

双端diff每一轮比较是通过不断的移动索引值来完成的。比较会持续进行，直到以下任一条件满足为止：

newStartIdx大于newEndIdx，意味着新节点列表全部遍历完成。
oldStartIdx大于oldEndIdx，意味着旧节点列表全部遍历完成。

5.4.1 代码

如下代码所示，oldStartIdx大于oldEndIdx或者newStartIdx大于newEndIdx时，需要跳出循环：

1
2
3

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 省略部分代码
}

头尾指针是从外向里进行移动，当头指针大于尾指针，说明当前列表已经处理完成。

5.5 双端比较四步匹配如何移动

我们知道双端diff存在的意义就是找到尽可能的复用节点，避免重新销毁、创建元素带来的性能损耗，这一节我们讨论下应该如何移动节点？

我们还以之前使用的四个P节点举例。如下图，此时DOM元素的顺序还是跟旧的一组节点保持一致。

5.5.1 双端对比第四步：旧节点的尾部节点和新节点的头部节点相同 - 进行移动

如上图。在双端对比第一轮比较中的第四步比较中，旧的一组子节点的尾部节点P-4和新的一组子节点的头部节点P-4一样，说明它们对应的真实DOM可以进行复用。对于可复用的DOM节点，我们只需要通过DOM移动操作完成更新即可。

那么这种情况下，我们应该如何移动节点呢？为了搞清楚这个问题，我们需要分析第四步比较过程中的细节。

我们注意到：第四步是比较旧的一组子节点的尾部节点与新的一组子节点的头部节点，发现两者相同。这说明：节点P-4原本是最后一个子节点，但在新的顺序中，它变成了第一个子节点。换句话说，节点P-4在更新之后应该是第一个节点。对应到程序中的逻辑，可以将其翻译为：将索引oldEndIdx指向的虚拟节点所对应的真实DOM（最后一个节点）移动到索引oldStartIdx指向的虚拟节点所对应的真实DOM（第一个节点）前面。

代码如下所示。

while(newStartIdx <= newEndIdx && oldStartIdx <= oldEndIdx){
    if(sameVNode(oldEndVnode, newStartVnode)){
        patchVNode(oldEndVnode, newStartVnode);
        nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
    }
}

由上面这些代码可知，在第四步这种情况下可以总结出下面几点内容。

当旧的一组节点的尾部节点对比新的一组节点的头部节点相同时，需要调用patchVNode函数对新旧对应节点进行打补丁。因为相同节点只能代表当前层级是相同的，并不能代表他的子节点信息等是相同的，所以需要对子节点继续进行比较。
oldEndVnode.elm 代表旧的一组节点的尾部节点所对应的真实节点。oldStartVnode.elm代表旧的一组节点的头部节点所对应的真实节点，insertBefore API可以将元素插入到某个元素之前。
DOM元素移动成功后，移动oldEndIdx指针以及newStartIdx指向至未处理的节点处。此时DOM和指针移动完成。

处理后的节点的状态以及真实DOM的顺序如下图所示。此时节点的顺序是P-4、P-1、P-2、P-3。

5.5.2 双端对比第一步&第二步 - 无需移动DOM

如上图所示，接着进行双端四步对比。此时在第二步中找到了相同的节点。如果在双端对比的第一步和第二步相同时，因为2者都同时处于尾部或者头部，因此不需要进行移动操作，只需要打补丁进行深度比较即可。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if(sameVNode(oldStartVnode, newStartVnode)){
        patchVNode(oldStartVnode, newStartVnode);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
    }else if(sameVNode(oldEndVnode, newEndVnode)){
        patchVNode(oldEndVnode, newEndVnode);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
    }else if(sameVNode(oldEndVnode, newStartVnode)){
        // 省略部分逻辑
    }
}

第二轮比较中新旧两组节点中的尾部节点相同，无需移动DOM节点，只需要移动相对应的指针。处理后的节点的状态以及真实DOM的顺序如下图所示。此时节点的顺序依旧是P-4、P-1、P-2、P-3。

5.5.3 双端对比第三步 - 旧节点的头部节点和新节点的尾部节点相同 - 进行移动

在上一轮循环中，我们并没有移动节点，只是对节点进行打补丁操作并移动索引。

我们再次进行新一轮的四步比较。

如上图，在第三步的比较中我们发现两者节点相同。这说明：节点P-1原本是头部节点，但在新的顺序中，它变成了尾部节点。换句话说，节点P-1在更新之后应该是最后一个节点。因此，我们需要将节点P-1对应的真实DOM移动到旧的一组子节点的尾部节点P-2所对应的真实DOM后面。

代码如下所示。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if(sameVNode(oldStartVnode, newStartVnode)){
        // 省略
    }else if(sameVNode(oldEndVnode, newEndVnode)){
        // 省略
    }else if(sameVNode(oldStartVnode, newEndVnode)){
        patchVNode(oldStartVnode, newEndVnode);
        api.insertBefore(
            parentElm,
            oldStartVnode.elm,
            api.nextSibling(oldEndVnode.elm)
        );
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];
    }else if(sameVNode(oldEndVnode, newStartVnode)){
        // 省略
    }
}

由上面这些代码可知，在第三步这种情况下可以总结出下面几点内容。

在旧的一组节点的头部节点对比新的一组节点的尾部节点相同时，需要调用patchVNode函数对新旧对应节点进行打补丁。因为相同节点只能代表当前层级是相同的，并不能代表他的子节点信息等是相同的，所以需要对子节点继续进行比较。
oldStartVnode.elm 代表旧的一组节点的头部节点所对应的真实节点。oldEndVnode.elm代表旧的一组节点的尾部节点所对应的真实节点，insertBefore API可以将元素插入到某个元素之前。因为需要将节点移至最后一位，所以这里获取到旧的一组子节点的尾部节点下一位，即空白字符。
DOM元素移动成功后，移动oldStartIdx指针以及newEndIdx指向至未处理的节点处。此时DOM和指针移动完成。

第三轮比较中旧节点的尾部节点和新节点的头部节点相同，则移动旧节点头部节点对应的DOM元素到尾部节点对应的DOM元素之后。处理后的节点的状态以及真实DOM的顺序如下图所示。此时节点的顺序是P-4、P-2、P-1、P-3。

如上图所示，其实这个时候DOM元素的顺序已经完全调整好了，但是由于还有一组数据没有对比完，所以要接着进行对比，我们可以发现，新旧节点均只存在一组子节点，我们进行对比，发现节点一样，由于这属于第一步，不需要进行DOM移动，只需要打补丁即可。这里不再赘述。

5.5.4 总结

经过上面的实践，我们可以对该现象进行总结：

在执行双端diff的第一步（新旧两组子节点的头部节点进行比较）和第二步（新旧两组子节点的尾部节点进行比较）时，如果找到相同节点，不需要移动DOM，只需要打补丁。
在执行双端diff的第三步（旧的一组子节点的头部节点与新的一组子节点的尾部节点）时，如果找到相同节点，需要将旧的一组子节点的头部节点引用的真实节点插入到旧的一组子节点的尾部节点引用的真实节点之后。同时需要打补丁。
在执行双端diff的第四步（旧的一组子节点的尾部节点与新的一组子节点的头部节点）时，如果找到相同节点，需要将旧的一组子节点的尾部节点引用的真实节点插入到旧的一组子节点的头部节点引用的真实节点之前。同时需要打补丁。

5.5.5 思考：为什么在第三步/第四步中节点移动的位置跟当前处理中的元素位置有关

不知道大家有没有质疑过，在第三步时，节点移动的位置不是插在整个DOM树的最后一个位置，而是跟当前处理中的元素位置有关。即头部节点和尾部节点有关。

因为在第三步双端diff比较的过程中，尾部节点的索引是一直向上的，所以后面处理的元素一定不会比之前处理过的元素位置要更靠后。也就是说一定会在当前处理元素的最后一位。

5.6 非理想情况下应该如何操作

之前我们举的例子一直是比较理想的情况，即每一轮diff对比都能够命中，但是实际中可能存在无法命中的情况。

如上图所示，我们使用之前的diff对比方法发现四步均无法找到可复用的节点，这个时候我们需要添加额外的处理步骤来处理这种非理想的情况。

既然两个头部和两个尾部的四个节点中都没有可复用的节点，那么我们就尝试看看非头部、非尾部的节点能否复用。、

5.6.1 拿新的一组子节点的头部节点在旧子节点中寻找可复用节点

具体做法是，拿新的一组子节点中的头部节点去旧的一组子节点中寻找。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
            if(sameVNode(oldStartVnode, newStartVnode)){
                //省略
            }else if(sameVNode(oldEndVnode, newEndVnode)){
                //省略
            }else if(sameVNode(oldStartVnode, newEndVnode)){
                //省略
            }else if(sameVNode(oldEndVnode, newStartVnode)){
                //省略
            }else {
                // 遍历旧的一组子节点，试图寻找与 newStartVNode 拥有相同 key 值的节

                // idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引
                const idxInOld = oldCh.findIndex(
                    node => node.key === newStartVnode.key
                )
            }
}

在上面这段代码中，我们遍历旧的一组子节点，尝试在其中寻找与新的一组子节点的头部节点具有相同key值的节点，并将该节点在旧的一组子节点中的索引存储到变量idxInOld中。

那么在旧的一组子节点中，找到与新的一组子节点的头部节点具有相同key值的节点意味着什么呢？

观察上图，当我们拿新的一组子节点的头部节点P-2去旧的一组子节点中查找时，会在索引为1的位置找到可复用的节点。

这意味着，节点P-2原本不是头部节点，但在更新之后，它应该变成头部节点。

所以我们需要将节点P-2对应的真实DOM节点移动到当前旧的一组子节点的头部节点P-1所对应的真实DOM之前。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
            if(sameVNode(oldStartVNode, newStartVNode)){ 
                // 省略
            }else if(sameVNode(oldEndVNode, newEndVNode)){
                // 省略
            }else if(sameVNode(oldStartVNode, newEndVNode)){
                // 省略
            }else if(sameVNode(oldEndVNode, newStartVNode)){
                // 省略
            }else {
                // 遍历旧的一组子节点，试图寻找与 newStartVNode 拥有相同 key 值的节

                // idxInOld 就是新的一组子节点的头部节点在旧的一组子节点中的索引
                const idxInOld = oldCh.findIndex(
                    node => node.key === newStartVNode.key
                )

                // idxInOld 大于 0，说明找到了可复用的节点，并且需要将其对应的真实DOM移动到头部
                if(idxInOld > 0){
                    // idxInOld 位置对应的 vnode 就是需要移动的节点
                    const vnodeToMove = oldCh[idxInOld]
                    // 不要忘记除移动操作外还应该打补丁
                    patchVNode(vnodeToMove, newStartVNode)
                    // 将 vnodeToMove.el 移动到头部节点 oldStartVNode.el 之前，因此使用后者作为锚点
                    api.insertBefore(parentElm,vnodeToMove.elm,oldStartVNode.elm);
                    // 由于位置 idxInOld 处的节点所对应的真实 DOM 已经移动到了别处，因此将其设置为 undefined
                    oldCh[idxInOld] = undefined
                    // 最后更新 newStartIdx 到下一个位置
                    newStartVNode = newCh[++newStartIdx]
                }
            }
}

在上面这段代码中，首先判断idInOld是否大于0。如果条件成立，则说明找到了可复用的节点，然后将该节点对应的真实DOM移动到头部。为此，我们先要获取需要移动的节点，这里的oldCh[idxInOld]所指向的节点就是需要移动的节点。在移动节点之前，不要忘记调用patchVNode函数打补丁。接着，调用insertBefore函数，并以现在的头部节点对应的真实DOM节点oldStartVNode.el作为锚点参数来完成节点的移动操作。当节点移动完成后，还有两步工作需要做。

由于处理idxInOld处的节点已经处理过了（对应的真实DOM移到了别处），因此我们应该将oldCh[idxInOld]设置为undefined。
新的一组子节点中的头部节点已经处理完毕，因此将newStartIdx前进到下一个位置。

第一轮比较中，在索引1处找到了可以复用的节点。需要将索引1对应的DOM节点移动到旧的一组节点对应的DOM节点之前，并且向下移动相对应的指针newStartIdx。处理后的节点的状态以及真实DOM的顺序如下图所示。此时节点的顺序是P-2、P-1、P-3、P-4。

5.6.2 处理undefined情况

如上图，我们继续接着进行diff，接着使用之前说到的双端diff比较方法进行比较。

第一步：比较旧的一组子节点的头部节点P-1与新的一组子节点的头部节点P-4，看看它们是否相同。由于两者的key不相同，因此不可以复用节点，直接跳过。
第二步：比较旧的一组子节点的尾部节点P-4与新的一组子节点的尾部节点P-3，看看它们是否相同。由于两者的key不相同，因此不可以复用节点，直接跳过。
第三步：比较旧的一组子节点的头部节点P-1与新的一组子节点的尾部节点P-3，看看它们是否相同。由于两者的key不相同，因此不可以复用节点，直接跳过。
第四步：比较旧的一组子节点的尾部节点P-4与新的一组子节点的头部节点P-4，看看它们是否相同。由于两者的key相同，因此可以复用节点。

在第四步中，我们发现旧的一组子节点的尾部节点P-4和新的一组子节点的头部节点P-4相同。根据之前学到的知识，P-1在旧的一组子节点中是在最后一位，在新的一组子节点中在第一位。因此，我们需要将旧的尾部节点所对应的DOM节点移动到旧的头部节点所对应的DOM节点之前。

处理后的节点的状态以及真实DOM的顺序如下图所示。此时节点的顺序是P-2、P-4、P-1、P-3。

由于还没有比较完成，所以我们需要继续使用之前介绍的方法进行对比。

第一步：比较旧的一组子节点的头部节点P-1与新的一组子节点的头部节点P-1，看看它们是否相同。由于两者的key为1，因此可以复用节点。

我们之前讨论过，当在双端diff的第一步和第二步比较相同时，可以复用，不需要移动节点，但是需要调用patchVNode进行打补丁，并移动oldStartIdx和newStartIdx向后一位。

处理后的节点的状态以及真实DOM的顺序如下图所示。此时节点的顺序是P-2、P-4、P-1、P-3。

由于还没有比较完成，所以我们需要继续进行下一轮的比较。这个时候我们发现，旧的一组子节点中的头部节点是undefined。这说明该节点已经被处理过了，因此不需要再处理它了，直接跳过即可，但是不要忘记移动指针oldStartIdx。

我们需要补充这部分的逻辑实现：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 增加两个判断分支，如果头尾部节点为undefined，则说明该节点已经被处理过了，直接跳到下一个位置
    if(!oldStartVNode){
        oldStartVNode = oldCh[++oldStartIdx];
    }else if(!oldEndVNode){
        oldEndVNode = oldCh[--oldEndIdx];
    }else if(sameVNode(oldStartVNode, newStartVNode)){
        // 省略代码
    }else if(sameVNode(oldEndVNode, newEndVNode)){
        // 省略代码
    }else if(sameVNode(oldStartVNode, newEndVNode)){
        // 省略代码
    }else if(sameVNode(oldEndVNode, newStartVNode)){
        // 省略代码
    }else {
        // 省略代码
    }
}

由于还没有比较完成，所以我们需要继续进行下一轮的比较。

第一步：比较旧的一组子节点的头部节点P-3和新的一组子节点的头部节点P-3，看看他们是否相同。由于两者的key为3，因此可以复用DOM节点。

第一步比较不需要移动DOM节点，但是需要调用patchVNode进行打补丁，并移动oldStartIdx和newStartIdx向后一位。

至此，双端diff所有比较已经结束，最终DOM的顺序为P-2、P-4、P-1、P-3。

5.7 添加新元素

在上一节中，我们介绍了非理想情况下（在一轮比较过程中，不会命中四个步骤中的任何一步）的处理逻辑。

如上图例子所示，这一节中我们主要讨论新增新元素的情况。

首先，我们尝试进行第一轮比较，发现在四个步骤中都找不到复用的节点。于是我们尝试拿新的一组子节点中的头部节点P-4去旧的一组子节点中寻找相同key值的节点，但是在旧的一组子节点中根本就没有P-4节点，如下图所示。

5.7.1 挂载节点到正确的位置

以上这说明节点P-4是一个新增节点，我们应该将它挂在到正确的位置。那么应该挂载到哪里呢？

因为节点P-4是新的一组子节点的头部节点，所以只需要将它挂载到当前头部节点之前即可。

“当前”头部节点指的是，旧的一组子节点中的头部节点所对应的真实DOM节点P-1。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { 
            if(!oldStartVNode){
                // 代码省略
            }else if(!oldEndVNode){
                // 代码省略
            }else if(sameVNode(oldStartVNode, newStartVNode)){
                // 代码省略
            }else if(sameVNode(oldEndVNode, newEndVNode)){
                // 代码省略
            }else if(sameVNode(oldStartVNode, newEndVNode)){
                // 代码省略
            }else if(sameVNode(oldEndVNode, newStartVNode)){
                // 代码省略
            }else {
                // 代码省略
                const idxInOld = oldCh.findIndex(
                    node => node.key === newStartVNode.key
                ) 
                if(idxInOld > 0){
                    // 代码省略
                }else{
                    // 将 newStartVNode 作为新节点挂载到头部，使用当前头部节点oldStartVNode.el 作为锚点
                    api.insertBefore(
                        parentElm,
                        createElm(newStartVNode),
                        oldStartVNode.elm
                    )
                }
                newStartVNode = newCh[++newStartIdx]
            }
}

如上面的代码所示，当条件idxInOld > 0 不成立时，说明newStartVNode节点是全新的节点。又由于newStartVNode节点是头部节点，因此我们应该将其作为新的头部节点进行挂载。

处理后的真实节点的顺序为P-4、P-1、P-2、P-3。如下图所示：

当新节点P-4挂载完成后，会进行后续的更新，直到全部更新完成为止。

5.7.2 异常情况

上一节中我们补充了新增节点时的逻辑。但是并不是完美的，我们调整一下上述例子中的新的一组子节点顺序，如下图所示：

对这个例子，我们使用双端diff算法进行第一轮的对比。

第一步：比较旧的一组子节点的头部节点P-1和新的一组子节点的头部节点P-4，看看是否相同。发现不相同，不可复用，直接跳过。
第二步：比较旧的一组子节点的尾部节点P-3和新的一组子节点的尾部节点P-3，看看是否相同。发现相同，可以复用DOM。

所以我们需要将oldEndIdx和newEndIdx都向下移动一位，并且对这2个节点进行打补丁。处理完以后节点的处理状态以及真实的DOM顺序如下图所示：

此时，真实DOM节点的顺序是：P-1、P-2、P-3。由于还没有比较完成，所以我们需要继续进行下一轮的比较。

第一步：比较旧的一组子节点的头部节点P-1和新的一组子节点的头部节点P-4，看看是否相同。发现不相同，不可复用，直接跳过。
第二步：比较旧的一组子节点的尾部节点P-2和新的一组子节点的尾部节点P-2，看看是否相同。发现相同，可以复用DOM。

所以我们需要将oldEndIdx和newEndIdx都向下移动一位，并且对这2个节点进行打补丁。处理完以后节点的处理状态以及真实的DOM顺序如下图所示：

此时，真实DOM节点的顺序是：P-1、P-2、P-3。由于还没有比较完成，所以我们需要继续进行下一轮的比较。

第一步：比较旧的一组子节点的头部节点P-1和新的一组子节点的头部节点P-4，看看是否相同。发现不相同，不可复用，直接跳过。
第二步：比较旧的一组子节点的尾部节点P-1和旧的一组子节点的尾部节点P-1，看看是否相同。发现相同，可以复用DOM。

所以我们需要将oldEndIdx和newEndIdx都向下移动一位，并且对这2个节点进行打补丁。处理完以后节点的处理状态以及真实的DOM顺序如下图所示：

当这一轮更新完毕后，由于变量oldStartIdx的值大于oldEndIdx的值，满足更新停止的条件，因此更新停止。但是我们可以观察到，节点P-4在整个更新过程中被遗漏了，没有得到任何处理，这说明我们的算法是有缺陷的。为了弥补这个缺陷，我们需要添加额外的处理逻辑。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 代码省略
}
if(newStartIdx <= newEndIdx){ 
    addVnodes(
        parentElm,
        oldStartVNode.elm,
        newCh,
        newStartIdx,
        newEndIdx
    )
}

我们在while循环结束后增加了一个if条件语句，检查新的一组子节点的头部节点和尾部节点的索引情况。如图可知，当newStartIdx <= newEndIdx成立，说明新的一组子节点中有遗留的节点需要作为新节点挂载。哪些节点是新节点呢？索引值位于newStartIdx和newEndIdx这个区间内的节点都是新节点。于是我们调用之前定义的方法addVnodes即可进行挂载。其中锚点元素为旧节点的头部节点。

5.8 移除元素

上一节中我们讨论了添加元素如何操作，现在我们讨论下如何移除元素。如下图所示：

在这个例子中，新旧两组子节点的顺序如下。

旧的一组子节点：P-1、P-2、P-3。
新的一组子节点：P-1、P-3。

可以看到，在新的一组子节点中P-2节点已经不存在了。为了弄清楚应该如何处理节点被移除的情况，我们还是按照双端Diff算法的思路执行逻辑。

第一步：比较旧的一组子节点的头部节点P-1与新的一组子节点中的头部节点P-1，看看他们是否相同。发现两者的key相同，可以复用。

在第一步的比较中找到了可复用的节点，于是执行更新。在这一轮比较过后，新旧两组子节点以及真实DOM节点的状态如下图所示：

接着，执行下一轮更新。

第一步：比较旧的一组子节点中的头部节点P-2与新的一组子节点中的头部节点P-3，两者的key值不同，不可以复用。
第二步：比较旧的一组子节点中的尾部节点P-3与新的一组子节点中的尾部节点P-3，两者的key相同，可以复用。

在第二步中找到了可复用的节点，于是进行更新。更新后的新旧两组子节点以及真实DOM节点的状态如下图所示：

此时变量newStartIdx的值大于变量newEndIdx的值，满足更新停止的条件，于是更新结束。观察上图可知，旧的一组子节点中存在未被处理的节点，应该将其移除。因此，我们需要增加额外的代码来处理它。

if(oldStartIdx <= oldEndIdx){
    removeVnodes(
        parentElm,
        oldCh,
        oldStartIdx,
        oldEndIdx
    )
}

与处理新增节点类似，我们在while循环结束后又增加了一个else…if分支，用于卸载已经不存在的节点。由图可知，索引值位于oldStartIdx和oldEndIdx这个区间内的节点都应该被卸载，于是我们需要调用之前定义的removeVnodes对他们进行逐一删除。

六、总结

这篇专栏中，我们对Vue2中双端diff算法进行了详细的解释，diff算法是在Vue更新渲染时进行节点复用的算法，通过这个算法，可以避免频繁的对节点进行删除、添加造成的性能消耗。

如果这篇文章对你有一定启发和帮助。欢迎给予打赏。

🔥Vue2双端对比

一、diff算法

1.1 前世今生

1.2 diff算法的复杂度

1.3 diff算法的核心要素

1.3.1 同层比较

1.3.2 相同节点判断策略

1.3.3 循环从两边向中间比较

1.3.4 节点复用

二、虚拟 DOM和 diff算法的关联

三、 snabbdom简介

四、更新渲染

4.1 为什么更新函数patchVNode叫做打补丁？

4.2 进行dom的复用

4.2.1 浏览器中的DOM

4.2.2 旧的vnode指向内存中的真实DOM

4.2.3 新的vnode elm复用老的vnode elm

4.3 获取新老节点的子节点

4.4 判断新虚拟节点是文本节点

4.5 判断新虚拟节点是非文本节点

4.5.1 当新旧虚拟节点都存在子节点时

4.5.2 当新虚拟节点存在子节点 & 旧虚拟节点不存在子节点

4.5.3 当新虚拟节点没有子节点 & 旧虚拟节点节点有子节点

4.5.4 新虚拟节点没有子节点且没有文字节点 & 旧虚拟节点有文字节点

五、双端diff核心函数-updateChildren

5.1 双端比较的四个关键索引值

5.1.1 头部节点和尾部节点

5.1.2 代码实现

5.2 老vnode引用真实DOM

5.3 双端比较的方式

5.3.1 第三步和第四步顺序容易搞混？

5.4 双端比较的循环条件

5.4.1 代码

5.5 双端比较四步匹配如何移动

5.5.1 双端对比第四步：旧节点的尾部节点和新节点的头部节点相同 - 进行移动

5.5.2 双端对比第一步&第二步 - 无需移动DOM

5.5.3 双端对比第三步 - 旧节点的头部节点和新节点的尾部节点相同 - 进行移动

5.5.4 总结

5.5.5 思考：为什么在第三步/第四步中 节点移动的位置跟当前处理中的元素位置有关

5.6 非理想情况下应该如何操作

5.6.1 拿新的一组子节点的头部节点在旧子节点中寻找可复用节点

5.6.2 处理undefined情况

5.7 添加新元素

5.7.1 挂载节点到正确的位置

5.7.2 异常情况

5.8 移除元素

六、总结

5.5.5 思考：为什么在第三步/第四步中节点移动的位置跟当前处理中的元素位置有关