簡述 Diff 算法的執行過程

diff算法是一種通過同層的樹節點進行比較的高效算法，避免了對樹進行逐層搜尋周遊，是以時間複雜度隻有 O(n)。

diff算法有兩個比較顯著的特點：

1、比較隻會在同層級進行, 不會跨層級比較。

2、在diff比較的過程中，循環從兩邊向中間收攏。

diff流程：

1. 首先定義 oldStartIdx、newStartIdx、oldEndIdx 以及 newEndIdx 分别是新老兩個 VNode 的兩邊的索引。

2. 接下來是一個 while 循環，在這過程中，oldStartIdx、newStartIdx、oldEndIdx 以及 newEndIdx 會逐漸向中間靠攏。while 循環的退出條件是直到老節點或者新節點的開始位置大于結束位置。

   while 循環中會遇到四種情況：

   情形一：當新老 VNode 節點的 start 是同一節點時，直接 patchVnode 即可，同時新老 VNode 節點的開始索引都加 1。

   情形二：當新老 VNode 節點的 end 是同一節點時，直接 patchVnode 即可，同時新老 VNode 節點的結束索引都減 1。

   情形三：當老 VNode 節點的 start 和新 VNode 節點的 end 是同一節點時，這說明這次資料更新後 oldStartVnode 已經跑到了 oldEndVnode 後面去了。這時候在 patchVnode 後，還需要将目前真實 dom 節點移動到 oldEndVnode 的後面，同時老 VNode 節點開始索引加 1，新 VNode 節點的結束索引減 1。

   情形四：當老 VNode 節點的 end 和新 VNode 節點的 start 是同一節點時，這說明這次資料更新後 oldEndVnode 跑到了 oldStartVnode 的前面去了。這時候在 patchVnode 後，還需要将目前真實 dom 節點移動到 oldStartVnode 的前面，同時老 VNode 節點結束索引減 1，新 VNode 節點的開始索引加 1。

3. while 循環的退出條件是直到老節點或者新節點的開始位置大于結束位置。

   情形一：如果在循環中，oldStartIdx大于oldEndIdx了，那就表示oldChildren比newChildren先循環完畢，那麼newChildren裡面剩餘的節點都是需要新增的節點，把[newStartIdx, newEndIdx]之間的所有節點都插入到DOM中

   情形二：如果在循環中，newStartIdx大于newEndIdx了，那就表示newChildren比oldChildren先循環完畢，那麼oldChildren裡面剩餘的節點都是需要删除的節點，把[oldStartIdx, oldEndIdx]之間的所有節點都删除

資料來源：拉勾教育