算法板块导览

算法这一块最容易「看懂了但写不出来」。所以本板块的每篇都是同一个结构：先看可视化跑起来，再读 TypeScript 实现，最后回到复杂度与边界条件。页面里的示例代码都在上面直接运行，源码与正文永远一致。

板块地图

页面	你会得到什么	关键概念
复杂度与分析方法	会算复杂度，而不是背结论	大 O/Θ/Ω、摊还、主定理、实测方法
基础排序	四种简单排序与稳定性的由来	冒泡、选择、插入、希尔、比较次数
高级排序	工程里真正在用的排序	归并、快排分区、堆排、计数/基数/桶
查找与二分	把二分写对（含三种边界）	边界模板、二分答案、三分、旋转数组
双指针、滑动窗口与前缀和	把 O(n²) 降到 O(n) 的套路	对撞/快慢指针、变长窗口、单调栈/队列
递归、分治与回溯	会写递归树与剪枝	回溯模板、剪枝、N 皇后、栈溢出
动态规划	从「想不出来」到「按模板推」	状态定义、转移方程、滚动数组、背包
图算法	会选对图算法	BFS/DFS、拓扑排序、Dijkstra、A*、MST
字符串、位运算与数论	补齐常考的零碎工具	KMP、滚动哈希、位技巧、筛法、快速幂

配套的数据结构板块

算法的实现离不开容器：想查「该用哪个容器、各操作复杂度是多少」，看 数据结构板块；例如 堆与优先队列 是 Dijkstra 的前置知识，并查集 是 Kruskal 的前置知识。

怎么用这个板块

1. 先跑示例：每页的在线示例都能交互（调规模、换数据分布、单步、暂停）。先把「算法在做什么」看明白。
2. 再读实现：示例源码就是正文展示的 TypeScript，注意看不变量与边界判断，这两处才是算法的难点。
3. 对着复杂度表自查：每页都有复杂度对照表。如果你实现的复杂度与表里不一致，先怀疑自己。
4. 最后做练习：每页结尾给同类型的变体题思路，用来检验是否真的掌握。

实测复杂度曲线同一台机器上不同增长阶的耗时曲线，暴露常数因子与 JIT 的影响

examples/algorithms/complexity-benchmark.js

/**
 * 【算法 · TypeScript】不同增长阶的实测耗时曲线
 * ------------------------------------------------------------------
 * 把 O(1) / O(log n) / O(n) / O(n log n) / O(n²) 五种增长阶放进同一张双对数图：
 * 横轴是输入规模 n（以 2 为底的对数刻度），纵轴是「单次调用的纳秒数」（以 10 为底）。
 *
 * 想说明三件事：
 *   1. 双对数坐标里的直线代表幂律增长，斜率就是增长阶的指数；
 *   2. 增长阶只在 n 足够大时才决定胜负，小规模时常数因子说了算；
 *   3. 预热（JIT 优化）会明显改变测量结果，所以关闭「预热」开关可以亲眼看到它。
 *
 * 写法要点：只用可擦除语法；顶层不访问 window / document；耗时测量放在函数体内。
 */
import { create2D, rafLoop, cleanupAll } from '../shared/runtime.js'
import { createPanel } from '../shared/ui.js'

/** 把计算结果累加到这里：JIT 一旦发现结果没人用，可能把整段计算消除掉 */
let sink = 0

/** 确定性伪随机（mulberry32），保证不同规模、不同批次用的数据分布一致 */
function mulberry32(seed: number): () => number {
  let a = seed >>> 0
  return () => {
    a = (a + 0x6d2b79f5) >>> 0
    let t = a
    t = Math.imul(t ^ (t >>> 15), t | 1)
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61)
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296
  }
}

/**
 * 一次测量所用的数据集：构造过程放在计时之外。
 * `values` 视为只读的原始数据，`scratch` / `aux` 是给算法用的可写缓冲，
 * 这样各条曲线之间不会互相污染（不会出现「上一轮把数组排好序、下一轮变成最好情况」）。
 */
interface DataSet {
  readonly n: number
  readonly values: number[]
  readonly sorted: number[]
  readonly scratch: number[]
  readonly aux: number[]
}

function makeData(n: number): DataSet {
  const rand = mulberry32(0x9e3779b9 ^ Math.imul(n, 2654435761))
  const values = new Array<number>(n)
  for (let i = 0; i < n; i++) values[i] = Math.floor(rand() * n)
  // 默认的 sort() 按字符串比较（10 < 9），必须显式传数值比较器
  const sorted = values.slice().sort((a, b) => a - b)
  return { n, values, sorted, scratch: new Array<number>(n), aux: new Array<number>(n) }
}

/** 归并排序：把 values[lo, hi) 原地排好，scratch 作为 O(n) 辅助空间 */
function mergeSort(values: number[], scratch: number[], lo: number, hi: number): void {
  if (hi - lo < 2) return
  const mid = (lo + hi) >> 1
  mergeSort(values, scratch, lo, mid)
  mergeSort(values, scratch, mid, hi)
  for (let k = lo; k < hi; k++) scratch[k] = values[k]
  let i = lo
  let j = mid
  for (let k = lo; k < hi; k++) {
    if (i >= mid) values[k] = scratch[j++]
    else if (j >= hi) values[k] = scratch[i++]
    else values[k] = scratch[i] <= scratch[j] ? scratch[i++] : scratch[j++]
  }
}

/** 插入排序：随机数据下的平均移动次数约为 n²/4 */
function insertionSort(values: number[], n: number): void {
  for (let i = 1; i < n; i++) {
    const key = values[i]
    let j = i - 1
    while (j >= 0 && values[j] > key) {
      values[j + 1] = values[j]
      j--
    }
    values[j + 1] = key
  }
}

interface Benchmark {
  /** 图上图例里的名字 */
  readonly label: string
  /** 增长阶，用纯文本写（本页不使用数学公式语法） */
  readonly order: string
  readonly color: string
  /** 一次测量内部重复的次数：把纳秒级的操作放大到计时器分辨率之上 */
  readonly repeat: number
  /** 超过这个规模会明显阻塞主线程，直接不测 */
  readonly maxN: number
  run(data: DataSet): void
}

const BENCHMARKS = [
  {
    label: '数组随机取值',
    order: 'O(1)',
    color: '#7ee7ce',
    repeat: 200000,
    maxN: Number.POSITIVE_INFINITY,
    run(data: DataSet): void {
      let acc = 0
      const k = data.n >> 1
      for (let r = 0; r < 200000; r++) acc += data.sorted[k]
      sink += acc
    }
  },
  {
    label: '二分查找',
    order: 'O(log n)',
    color: '#7aa2ff',
    repeat: 20000,
    maxN: Number.POSITIVE_INFINITY,
    run(data: DataSet): void {
      const { sorted, n } = data
      let acc = 0
      for (let r = 0; r < 20000; r++) {
        const target = sorted[(r * 7919) % n]
        let lo = 0
        let hi = n - 1
        while (lo <= hi) {
          const mid = lo + ((hi - lo) >> 1)
          const v = sorted[mid]
          if (v === target) {
            acc += mid
            break
          }
          if (v < target) lo = mid + 1
          else hi = mid - 1
        }
      }
      sink += acc
    }
  },
  {
    label: '数组求和',
    order: 'O(n)',
    color: '#ffd166',
    repeat: 100,
    maxN: Number.POSITIVE_INFINITY,
    run(data: DataSet): void {
      const { values, n } = data
      let acc = 0
      for (let r = 0; r < 100; r++) {
        for (let i = 0; i < n; i++) acc += values[i]
      }
      sink += acc
    }
  },
  {
    label: '归并排序',
    order: 'O(n log n)',
    color: '#c792ea',
    repeat: 5,
    maxN: Number.POSITIVE_INFINITY,
    run(data: DataSet): void {
      const { values, scratch, aux, n } = data
      for (let r = 0; r < 5; r++) {
        for (let i = 0; i < n; i++) scratch[i] = values[i]
        mergeSort(scratch, aux, 0, n)
        sink += scratch[n >> 1]
      }
    }
  },
  {
    label: '插入排序',
    order: 'O(n²)',
    color: '#ff8a80',
    repeat: 1,
    maxN: 2048,
    run(data: DataSet): void {
      const { values, scratch, n } = data
      for (let i = 0; i < n; i++) scratch[i] = values[i]
      insertionSort(scratch, n)
      sink += scratch[n >> 1]
    }
  }
] satisfies readonly Benchmark[]

/** 参与测量的规模：2 的幂，图上按 log2 均匀分布 */
const SIZES: readonly number[] = [128, 256, 512, 1024, 2048, 4096]

interface Cell {
  readonly n: number
  /** 单次调用的纳秒数（已经除以内部重复次数） */
  readonly nsPerCall: number
}

interface Series {
  readonly bench: Benchmark
  readonly points: (Cell | null)[]
}

function fmtNs(ns: number): string {
  if (ns < 1e3) return `${ns < 10 ? ns.toFixed(1) : ns.toFixed(0)} ns`
  if (ns < 1e6) return `${(ns / 1e3).toFixed(1)} µs`
  if (ns < 1e9) return `${(ns / 1e6).toFixed(2)} ms`
  return `${(ns / 1e9).toFixed(2)} s`
}

export default function (container: HTMLElement): () => void {
  const view = create2D(container, { width: 720, height: 420, background: '#0b1220' })
  const { ctx } = view

  const series: Series[] = BENCHMARKS.map((bench) => ({ bench, points: SIZES.map(() => null) }))
  const dataCache = new Map<number, DataSet>()

  let tasks: { si: number; ni: number }[] = []
  let cursor = 0
  let running = true
  let warmup = true
  let showGuides = true
  let samples = 5
  let status = '点击「重新测量」开始'

  function buildTasks(): void {
    tasks = []
    for (let si = 0; si < series.length; si++) {
      const maxN = series[si].bench.maxN
      for (let ni = 0; ni < SIZES.length; ni++) {
        if (SIZES[ni] <= maxN) tasks.push({ si, ni })
      }
    }
  }

  function dataFor(n: number): DataSet {
    const hit = dataCache.get(n)
    if (hit) return hit
    const made = makeData(n)
    dataCache.set(n, made)
    return made
  }

  /** 采样一次：返回「单次调用」的纳秒数 */
  function timeOnce(bench: Benchmark, data: DataSet): number {
    const t0 = performance.now()
    bench.run(data)
    const dt = performance.now() - t0
    return (dt * 1e6) / bench.repeat
  }

  /** 完整测量：可选预热 + 多次采样取中位数（中位数比平均值更抗 GC / 调度抖动） */
  function measureCell(bench: Benchmark, data: DataSet): number {
    if (warmup) bench.run(data)
    const times: number[] = []
    for (let s = 0; s < samples; s++) times.push(timeOnce(bench, data))
    times.sort((a, b) => a - b)
    return times[times.length >> 1]
  }

  function runOneTask(): void {
    const task = tasks[cursor]
    if (!task) return
    const s = series[task.si]
    const n = SIZES[task.ni]
    const ns = measureCell(s.bench, dataFor(n))
    s.points[task.ni] = { n, nsPerCall: ns }
    cursor++
    const done = cursor >= tasks.length
    status = `${s.bench.order} · n = ${n} → ${fmtNs(ns)}（${cursor}/${tasks.length}${done ? '，完成' : ''}）`
  }

  function reset(): void {
    for (const s of series) s.points.fill(null)
    buildTasks()
    cursor = 0
    running = true
    status = '测量中…'
  }

  /** 用首尾两个实测点估增长指数：t ∝ n^k，则 k = log(t1/t0) / log(n1/n0) */
  function empiricalExponent(s: Series): number | null {
    const valid = s.points.filter((c): c is Cell => c !== null)
    if (valid.length < 2) return null
    const first = valid[0]
    const last = valid[valid.length - 1]
    if (first.nsPerCall <= 0 || last.nsPerCall <= 0) return null
    return (
      Math.log(last.nsPerCall / first.nsPerCall) / Math.log(last.n / first.n)
    )
  }

  function yBounds(): { lo: number; hi: number } {
    let min = Number.POSITIVE_INFINITY
    let max = 0
    for (const s of series) {
      for (const c of s.points) {
        if (!c || c.nsPerCall <= 0) continue
        min = Math.min(min, c.nsPerCall)
        max = Math.max(max, c.nsPerCall)
      }
    }
    if (!Number.isFinite(min) || max <= 0) return { lo: 1, hi: 1e6 }
    const lo = Math.pow(10, Math.floor(Math.log10(Math.max(min * 0.5, 0.5))))
    let hi = Math.pow(10, Math.ceil(Math.log10(max * 2)))
    if (hi / lo < 100) hi = lo * 100
    return { lo, hi }
  }

  function draw(): void {
    const w = view.width
    const h = view.height
    const padL = 64
    const padR = 18
    const padT = 30
    const padB = 46
    const plotW = w - padL - padR
    const plotH = h - padT - padB

    ctx.fillStyle = '#0b1220'
    ctx.fillRect(0, 0, w, h)

    const yb = yBounds()
    const loN = SIZES[0]
    const hiN = SIZES[SIZES.length - 1]
    const lgLo = Math.log10(yb.lo)
    const lgHi = Math.log10(yb.hi)
    const xOf = (n: number): number =>
      padL + ((Math.log2(n) - Math.log2(loN)) / (Math.log2(hiN) - Math.log2(loN))) * plotW
    const yOf = (ns: number): number => {
      const v = Math.min(Math.max(ns, yb.lo), yb.hi)
      return padT + ((lgHi - Math.log10(v)) / (lgHi - lgLo)) * plotH
    }

    // 横向网格：每个数量级一条线
    ctx.font = '11px ui-monospace, monospace'
    ctx.textBaseline = 'middle'
    ctx.textAlign = 'right'
    for (let e = Math.round(lgLo); e <= Math.round(lgHi); e++) {
      const y = yOf(Math.pow(10, e))
      ctx.strokeStyle = 'rgba(122, 162, 255, 0.14)'
      ctx.lineWidth = 1
      ctx.beginPath()
      ctx.moveTo(padL, y)
      ctx.lineTo(padL + plotW, y)
      ctx.stroke()
      ctx.fillStyle = 'rgba(230, 237, 247, 0.5)'
      ctx.fillText(fmtNs(Math.pow(10, e)), padL - 8, y)
    }

    // 纵向网格：每个规模一条线
    ctx.textAlign = 'center'
    ctx.textBaseline = 'top'
    for (const n of SIZES) {
      const x = xOf(n)
      ctx.strokeStyle = 'rgba(122, 162, 255, 0.14)'
      ctx.beginPath()
      ctx.moveTo(x, padT)
      ctx.lineTo(x, padT + plotH)
      ctx.stroke()
      ctx.fillStyle = 'rgba(230, 237, 247, 0.5)'
      ctx.fillText(String(n), x, padT + plotH + 8)
    }
    ctx.fillStyle = 'rgba(230, 237, 247, 0.45)'
    ctx.textAlign = 'right'
    ctx.fillText('输入规模 n（对数刻度）', padL + plotW, padT + plotH + 26)
    ctx.textAlign = 'left'
    ctx.fillText('单次调用耗时', 8, 10)
    ctx.textBaseline = 'middle'

    // 理想斜率参考线：t = t0 · (n/n0)^k
    function guide(k: number, from: Series | null, color: string, label: string): void {
      if (!showGuides || !from) return
      const anchor = from.points.find((c): c is Cell => c !== null)
      if (!anchor || anchor.nsPerCall <= 0) return
      const t1 = anchor.nsPerCall * Math.pow(hiN / anchor.n, k)
      if (t1 > yb.hi * 10) return
      ctx.save()
      ctx.setLineDash([5, 5])
      ctx.strokeStyle = color
      ctx.lineWidth = 1.2
      ctx.beginPath()
      ctx.moveTo(xOf(anchor.n), yOf(anchor.nsPerCall))
      ctx.lineTo(xOf(hiN), yOf(t1))
      ctx.stroke()
      ctx.restore()
      ctx.fillStyle = color
      ctx.font = '10.5px ui-monospace, monospace'
      ctx.textAlign = 'left'
      ctx.textBaseline = 'bottom'
      ctx.fillText(label, xOf(hiN) - 92, yOf(t1) - 4)
      ctx.textBaseline = 'middle'
    }
    guide(1, series[2], 'rgba(255, 209, 102, 0.55)', '斜率 1（线性）')
    guide(2, series[4], 'rgba(255, 138, 128, 0.55)', '斜率 2（平方）')

    // 实测曲线
    ctx.lineJoin = 'round'
    for (const s of series) {
      const valid = s.points.filter((c): c is Cell => c !== null)
      if (!valid.length) continue
      ctx.strokeStyle = s.bench.color
      ctx.lineWidth = 2
      ctx.beginPath()
      valid.forEach((c, i) => {
        const x = xOf(c.n)
        const y = yOf(c.nsPerCall)
        if (i === 0) ctx.moveTo(x, y)
        else ctx.lineTo(x, y)
      })
      ctx.stroke()
      for (const c of valid) {
        ctx.beginPath()
        ctx.arc(xOf(c.n), yOf(c.nsPerCall), 3, 0, Math.PI * 2)
        ctx.fillStyle = s.bench.color
        ctx.fill()
      }
      // 被 maxN 截断的曲线：在停止处画一个空心标记
      const lastNi = s.points.reduce((acc, c, i) => (c ? i : acc), -1)
      if (lastNi >= 0 && lastNi < SIZES.length - 1) {
        ctx.beginPath()
        ctx.arc(xOf(SIZES[lastNi]), yOf(valid[valid.length - 1].nsPerCall), 6, 0, Math.PI * 2)
        ctx.strokeStyle = s.bench.color
        ctx.lineWidth = 1.2
        ctx.stroke()
      }
    }

    // 图例放在左下角：那里是「规模小、耗时大」的空区域
    let ly = padT + plotH - 20 - series.length * 17
    for (const s of series) {
      const k = empiricalExponent(s)
      ctx.fillStyle = s.bench.color
      ctx.fillRect(padL + 12, ly + 4, 12, 3)
      ctx.font = '11.5px ui-monospace, monospace'
      ctx.textAlign = 'left'
      ctx.fillStyle = 'rgba(230, 237, 247, 0.75)'
      const tail = k === null ? '' : `　实测斜率 ${k.toFixed(2)}`
      ctx.fillText(`${s.bench.order} ${s.bench.label}${tail}`, padL + 30, ly + 6)
      ly += 17
    }

    ctx.fillStyle = 'rgba(230, 237, 247, 0.55)'
    ctx.font = '12px ui-monospace, monospace'
    ctx.textAlign = 'left'
    ctx.fillText(status, padL, 15)
  }

  buildTasks()
  reset()

  const panel = createPanel(container, { title: '测量参数', position: 'below' })
  const progress = panel.readout('已完成 0 / 0 次测量')
  const slope = panel.readout('实测斜率：—')
  panel.checkbox({
    label: '预热一次再计时（关闭可看 JIT 影响）',
    value: true,
    onChange: (checked) => {
      warmup = checked
    }
  })
  panel.checkbox({
    label: '显示理想斜率参考线',
    value: true,
    onChange: (checked) => {
      showGuides = checked
    }
  })
  panel.slider({
    label: '每次测量采样次数',
    min: 3,
    max: 9,
    step: 2,
    value: samples,
    onInput: (v) => {
      samples = v
    }
  })
  panel.buttons([
    { label: '重新测量', onClick: () => reset() },
    {
      label: '暂停',
      onClick: () => {
        running = !running
      }
    }
  ])
  panel.note(
    '纵轴按数量级自动缩放，所以「曲线陡不陡」才是信息；图例里的实测斜率由首尾两点估算。'
  )

  function updateReadouts(): void {
    progress.set(`已完成 ${cursor} / ${tasks.length} 次测量`)
    const parts: string[] = []
    for (const s of series) {
      const k = empiricalExponent(s)
      if (k !== null) parts.push(`${s.bench.order}≈n^${k.toFixed(2)}`)
    }
    slope.set(parts.length ? `实测斜率 ${parts.join('  ')}` : '实测斜率：—')
  }
  updateReadouts()

  let frame = 0
  const loop = rafLoop(() => {
    if (running && cursor < tasks.length) runOneTask()
    if (frame++ % 15 === 0) updateReadouts()
    draw()
  })

  const offResize = view.onResize(() => draw())

  return cleanupAll(loop, offResize, view, panel)
}

复杂度速查

常见操作在各实现下的典型复杂度（n 为元素数量，k 为桶/位数，m 为值域）：

操作	数组	哈希表	平衡树/堆	链表
随机访问	O(1)	—	O(log n)	O(n)
头部插入/删除	O(n)	O(1)	O(log n)	O(1)
尾部插入	O(1) 摊还	O(1)	O(log n)	O(1)
按值查找	O(n)	O(1) 平均	O(log n)	O(n)
有序遍历	O(n log n)（需排序）	无序	O(n)	无序

排序与查找的复杂度对照：

算法	平均	最坏	空间	稳定
插入排序	O(n²)	O(n²)	O(1)	是
归并排序	O(n log n)	O(n log n)	O(n)	是
快速排序	O(n log n)	O(n²)	O(log n)	否
堆排序	O(n log n)	O(n log n)	O(1)	否
计数/基数排序	O(n + m) / O(nk)	同左	O(n + m)	是
二分查找	O(log n)	O(log n)	O(1)	—

TypeScript 代码约定

本板块示例一律用 TypeScript，并遵守 TypeScript 示例约定：

约定	写法	理由
算法做成泛型函数	function mergeSort<T>(items: readonly T[], compare: (a: T, b: T) => number): T[]	同一份实现既能排数字也能排对象
入参用只读	readonly T[]	明确「不修改调用方数据」，也避免原地改写引发的 bug
返回新数组	return [...left, ...right]	纯函数便于测试与对比；需要省内存时另给原地版本
用判别联合表示结果	type Result<T> = { ok: true; value: T } | { ok: false; reason: string }	替代 null + 魔法值，调用处强制处理失败分支
边界显式判断	if (items.length < 2) return [...items]	空数组/单元素是最高频的越界来源
复杂度写在注释里	/** O(n log n)，额外空间 O(n) */	让复杂度与实现绑在一起，重构时能立刻察觉退化

别用 enum 表示状态

本站示例运行在「剥离类型」模式下（Node 与 Vite 都是），enum 会生成运行时代码而被禁止。用 const STATE = { idle: 'idle', running: 'running' } as const + type State = (typeof STATE)[keyof typeof STATE] 表达，效果更好且可被擦除。

学习路径建议

• 准备面试：复杂度 → 基础/高级排序 → 二分 → 双指针与滑动窗口 → 回溯 → 动态规划 → 图算法 → 字符串与位运算。这条路径覆盖绝大多数考察点。
• 提升工程能力：复杂度 → 高级排序（理解内置排序为何是混合算法）→ 二分与滑动窗口（处理数据流的常见套路）→ 图算法（依赖解析、任务调度）→ 字符串（文本处理）。
• 给图形/前端做优化：先从 数据结构板块 选对容器，再回来看 算法 里的滑动窗口、单调栈与图算法——前端里真正高频的是这几类，而不是竞赛题。

常见坑（跨页面通用）

现象	原因	处理
本地跑得飞快，线上超时	只测了小规模或单一数据分布，忽略了最坏情况	用随机、有序、逆序、大量重复四种分布各测一遍
二分查找死循环	mid 取整方向与区间收缩方式不匹配	统一用 lo + ((hi - lo) >> 1)，并保证每次循环区间严格变小
递归爆栈	递归深度达到 n（如链状数据）	改成显式栈迭代，或限制深度；快排随机化枢轴
排序结果不对且只在特定输入出错	稳定性或比较器方向反了	明确比较器语义（负数表示 a 在前），需要稳定就选稳定排序
滑动窗口答案偏大/偏小	窗口收缩条件与「合法窗口」定义不一致	先写清「窗口内维护什么量」，再写左指针何时右移

相关板块

• 数据结构 —— 容器的复杂度与实现
• 图形学数学 —— 图形场景里的几何/向量算法
• 前端程序设计模式 —— 算法如何组织成可测试的模块
• TypeScript 示例约定 —— 本板块示例的写法约定