11.3 如何移动元素

if (moved) {
  // 计算最长递增子序列：返回其在 source 中的位置索引
  const seq = getSequence(source)

  // s 指向最长递增子序列的最后一个元素
  let s = seq.length - 1
  // i 指向新的一组子节点的最后一个元素
  let i = count - 1

  // 倒序遍历：从后往前匹配，锚点可以直接使用下一个节点
  for (i; i >= 0; i--) {
    if (source[i] === -1) {
      // ① source[i] 为 -1 → 全新节点，挂载
      const pos = i + newStart
      const newVNode = newChildren[pos]
      const nextPos = pos + 1
      const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null
      patch(null, newVNode, container, anchor)
    } else if (i !== seq[s]) {
      // ② 不在 seq 中 → 需要移动：插入到「下一个节点」的 DOM 之前
      const pos = i + newStart
      const newVNode = newChildren[pos]
      const nextPos = pos + 1
      const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null
      insert(newVNode.el, container, anchor)
    } else {
      // ③ i === seq[s] → 该节点不需要移动，s 指向 seq 的上一个元素
      s--
    }
  }
}

function getSequence(arr) {
  const p = arr.slice() // 记录前驱下标，用于回溯
  const result = [0] // 存递增子序列的下标
  let i, j, u, v, c
  const len = arr.length

  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        // 比末尾大，直接接在末尾之后
        p[i] = j
        result.push(i)
        continue
      }
      // 二分查找第一个值 >= arrI 的位置
      u = 0
      v = result.length - 1
      while (u < v) {
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i // 用更小的末尾替换
      }
    }
  }

  // 回溯：把 result 里的下标换成真正的前驱下标
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}