1
function diff(oldChildren, newChildren, parentEl) {
2
  // 1. 双端预处理（跳过相同前置节点）
3
  let oldStartIdx = 0
4
  let oldEndIdx = oldChildren.length - 1
5
  let newStartIdx = 0
6
  let newEndIdx = newChildren.length - 1
7
  let oldStartNode = oldChildren[oldStartIdx]
8
  let oldEndNode = oldChildren[oldEndIdx]
9
  let newStartNode = newChildren[newStartIdx]
10
  let newEndNode = newChildren[newEndIdx]
11

12
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
13
    if (!oldStartNode) {
14
      oldStartNode = oldChildren[++oldStartIdx]
15
    } else if (!oldEndNode) {
16
      oldEndNode = oldChildren[--oldEndIdx]
17
    } else if (isSameNode(oldStartNode, newStartNode)) {
18
      patchNode(oldStartNode, newStartNode)
19
      oldStartNode = oldChildren[++oldStartIdx]
20
      newStartNode = newChildren[++newStartIdx]
21
    } else if (isSameNode(oldEndNode, newEndNode)) {
22
      patchNode(oldEndNode, newEndNode)
23
      oldEndNode = oldChildren[--oldEndIdx]
24
      newEndNode = newChildren[--newEndIdx]
25
    } else {
26
      break
27
    }
28
  }
29

30
  // 2. 新旧节点完全匹配的情况
31
  if (oldStartIdx > oldEndIdx && newStartIdx <= newEndIdx) {
32
    // 新增节点
33
    const anchor = newChildren[newEndIdx + 1]?.el || null
34
    for (let i = newStartIdx; i <= newEndIdx; i++) {
35
      parentEl.insertBefore(createEl(newChildren[i]), anchor)
36
    }
37
    return
38
  } else if (newStartIdx > newEndIdx && oldStartIdx <= oldEndIdx) {
39
    // 删除节点
40
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
41
      parentEl.removeChild(oldChildren[i].el)
42
    }
43
    return
44
  }
45

46
  // 3. 处理未知序列
47
  const oldStart = oldStartIdx
48
  const oldEnd = oldEndIdx
49
  const newStart = newStartIdx
50
  const newEnd = newEndIdx
51

52
  // 构建 key 索引映射
53
  const keyIndexMap = {}
54
  for (let i = newStart; i <= newEnd; i++) {
55
    keyIndexMap[newChildren[i].key] = i
56
  }
57

58
  // 遍历旧节点序列
59
  const toMove = []
60
  const newIndexMap = new Array(oldEnd - oldStart + 1).fill(-1)
61

62
  for (let i = oldStart; i <= oldEnd; i++) {
63
    const oldNode = oldChildren[i]
64
    if (!oldNode) continue
65

66
    const newIndex = keyIndexMap[oldNode.key]
67
    if (newIndex === undefined) {
68
      // 删除不再存在的节点
69
      parentEl.removeChild(oldNode.el)
70
    } else {
71
      newIndexMap[i - oldStart] = newIndex
72
      toMove.push({ oldIndex: i, newIndex })
73

74
      if (newIndex < newStart || newIndex > newEnd) {
75
        patchNode(oldNode, newChildren[newIndex])
76
      }
77
    }
78
  }
79

80
  // 4. 计算最长递增子序列（LIS）
81
  const lis = getSequence(newIndexMap.filter(i => i !== -1))
82
  let lisIndex = lis.length - 1
83

84
  // 5. 执行移动操作
85
  for (let i = toMove.length - 1; i >= 0; i--) {
86
    const move = toMove[i]
87
    const curIndex = move.oldIndex - oldStart
88
    const newIndex = move.newIndex - newStart
89

90
    if (newIndexMap[curIndex] === -1) {
91
      // 新增节点
92
      const anchor = newChildren[newIndex + 1]?.el || null
93
      parentEl.insertBefore(createEl(newChildren[newIndex]), anchor)
94
    } else {
95
      // 移动节点
96
      if (lis[lisIndex] !== i) {
97
        const anchor = newChildren[newIndex + 1]?.el || null
98
        parentEl.insertBefore(oldChildren[move.oldIndex].el, anchor)
99
      } else {
100
        lisIndex--
101
      }
102
    }
103
  }
104
}
105

106
// 判断是否为相同节点
107
function isSameNode(a, b) {
108
  return a.key === b.key && a.type === b.type
109
}
110

111
// 更新节点属性/内容
112
function patchNode(oldNode, newNode) {
113
  const el = (newNode.el = oldNode.el)
114

115
  // 更新属性（简化实现）
116
  Object.entries(newNode.props).forEach(([key, value]) => {
117
    if (oldNode.props[key] !== value) {
118
      el.setAttribute(key, value)
119
    }
120
  })
121

122
  // 更新内容（简化实现）
123
  if (newNode.children !== oldNode.children) {
124
    el.textContent = newNode.children
125
  }
126
}
127

128
// 创建DOM元素（简化）
129
function createEl(vnode) {
130
  const el = document.createElement(vnode.type)
131

132
  // 设置属性
133
  Object.entries(vnode.props).forEach(([key, value]) => {
134
    el.setAttribute(key, value)
135
  })
136

137
  // 设置内容
138
  if (typeof vnode.children === 'string') {
139
    el.textContent = vnode.children
140
  }
141

142
  vnode.el = el
143
  return el
144
}
145

146
// 获取最长递增子序列（贪心+二分）
147
function getSequence(arr) {
148
  const p = arr.slice()
149
  const result =
150
  let i, j, u, v, c
151

152
  for (i = 0; i < arr.length; i++) {
153
    const current = arr[i]
154

155
    if (current !== -1) {
156
      j = result[result.length - 1]
157
      if (arr[j] < current) {
158
        p[i] = j
159
        result.push(i)
160
        continue
161
      }
162

163
      u = 0
164
      v = result.length - 1
165

166
      while (u < v) {
167
        c = (u + v) >> 1
168
        if (arr[result[c]] < current) {
169
          u = c + 1
170
        } else {
171
          v = c
172
        }
173
      }
174

175
      if (current < arr[result[u]]) {
176
        if (u > 0) p[i] = result[u - 1]
177
        result[u] = i
178
      }
179
    }
180
  }
181
  u = result.length
182
  v = result[u - 1]
183

184
  while (u-- > 0) {
185
    result[u] = v
186
    v = p[v]
187
  }
188

189
  return result
190
}

1
// 创建父元素
2
const container = document.createElement('div')
3

4
// 初始子节点
5
const oldVNodes = [
6
  { key: 'a', type: 'div', children: 'A', props: { class: 'item' } },
7
  { key: 'b', type: 'div', children: 'B', props: { class: 'item' } },
8
  { key: 'c', type: 'div', children: 'C', props: { class: 'item' } },
9
  { key: 'd', type: 'div', children: 'D', props: { class: 'item' } },
10
]
11

12
// 创建初始DOM
13
oldVNodes.forEach(vnode => {
14
  const el = createEl(vnode)
15
  container.appendChild(el)
16
})
17

18
// 新子节点（顺序变化 + 新增）
19
const newVNodes = [
20
  { key: 'd', type: 'div', children: 'D updated', props: { class: 'item updated' } },
21
  { key: 'a', type: 'div', children: 'A', props: { class: 'item' } },
22
  { key: 'c', type: 'div', children: 'C', props: { class: 'item' } },
23
  { key: 'e', type: 'div', children: 'E new', props: { class: 'item new' } },
24
]
25

26
// 执行Diff算法更新
27
diff(oldVNodes, newVNodes, container)
28

29
// 最终DOM顺序：
30
// D updated -> A -> C -> E new