数据结构与算法

常见数据结构（栈 / 队列 / 链表 / 树 / 字典 / 哈希）与排序算法的笔记。

2026-05-16

复杂度分析

常见数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie、并查集。

常见算法：递归、排序、二分查找、广度 / 深度优先搜索、哈希算法、贪心、分治、回溯、动态规划、字符串匹配。

栈

后进先出（LIFO）。常见于函数调用栈、括号匹配、撤销 / 重做、表达式求值。

class Stack<T> {
  #items: T[] = []

  push(item: T): void { this.#items.push(item) }
  pop(): T | undefined { return this.#items.pop() }
  peek(): T | undefined { return this.#items.at(-1) }
  get size(): number { return this.#items.length }
  isEmpty(): boolean { return this.#items.length === 0 }
}

// 应用：括号匹配
function isBalanced(s: string): boolean {
  const stack = new Stack<string>()
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }
  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch)
    else if (ch in pairs && stack.pop() !== pairs[ch]) return false
  }
  return stack.isEmpty()
}

isBalanced('({[]})') // true
isBalanced('({[)]}') // false

链式实现（不依赖数组方法，理解原理用）：

class Node<T> {
  next: Node<T> | null = null
  constructor(public value: T) {}
}

class LinkStack<T> {
  #top: Node<T> | null = null
  #size = 0

  push(value: T): void {
    const node = new Node(value)
    node.next = this.#top
    this.#top = node
    this.#size++
  }

  pop(): T | undefined {
    if (!this.#top) return undefined
    const value = this.#top.value
    this.#top = this.#top.next
    this.#size--
    return value
  }

  peek(): T | undefined { return this.#top?.value }
  get size(): number { return this.#size }
}

队列

先进先出（FIFO）。常见于任务队列、BFS、生产者-消费者。

class Queue<T> {
  #items: T[] = []

  enqueue(item: T): void { this.#items.push(item) }
  dequeue(): T | undefined { return this.#items.shift() }
  front(): T | undefined { return this.#items[0] }
  get size(): number { return this.#items.length }
  isEmpty(): boolean { return this.#items.length === 0 }
}

const q = new Queue<string>()
q.enqueue('A'); q.enqueue('B'); q.enqueue('C')
q.dequeue() // 'A'
q.front()   // 'B'
q.size      // 2

注意：Array.prototype.shift() 是 O(n)。大队列建议用双栈摊销、链队列或双端队列。

循环队列

固定容量，用环形索引复用空间，避免大队列频繁内存搬移。

class CircularQueue<T> {
  #items: (T | undefined)[]
  #head = 0
  #tail = 0
  #count = 0

  constructor(capacity: number) {
    this.#items = new Array<T | undefined>(capacity)
  }

  enqueue(item: T): boolean {
    if (this.isFull()) return false
    this.#items[this.#tail] = item
    this.#tail = (this.#tail + 1) % this.#items.length
    this.#count++
    return true
  }

  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined
    const v = this.#items[this.#head]
    this.#items[this.#head] = undefined
    this.#head = (this.#head + 1) % this.#items.length
    this.#count--
    return v
  }

  isEmpty(): boolean { return this.#count === 0 }
  isFull(): boolean { return this.#count === this.#items.length }
  get size(): number { return this.#count }
}

链表

单向链表

class Node<T> {
  next: Node<T> | null = null
  constructor(public value: T) {}
}

class LinkedList<T> {
  #head: Node<T> | null = null
  #size = 0

  append(value: T): void {
    const node = new Node(value)
    if (!this.#head) this.#head = node
    else {
      let cur = this.#head
      while (cur.next) cur = cur.next
      cur.next = node
    }
    this.#size++
  }

  insertAt(index: number, value: T): void {
    if (index < 0 || index > this.#size) throw new Error('out of range')
    const node = new Node(value)
    if (index === 0) {
      node.next = this.#head
      this.#head = node
    } else {
      const prev = this.#nodeAt(index - 1)!
      node.next = prev.next
      prev.next = node
    }
    this.#size++
  }

  removeAt(index: number): void {
    if (index < 0 || index >= this.#size) throw new Error('out of range')
    if (index === 0) this.#head = this.#head!.next
    else {
      const prev = this.#nodeAt(index - 1)!
      prev.next = prev.next!.next
    }
    this.#size--
  }

  indexOf(value: T): number {
    let cur = this.#head, i = 0
    while (cur) {
      if (cur.value === value) return i
      cur = cur.next; i++
    }
    return -1
  }

  toArray(): T[] {
    const out: T[] = []
    for (let cur = this.#head; cur; cur = cur.next) out.push(cur.value)
    return out
  }

  get size(): number { return this.#size }

  #nodeAt(index: number): Node<T> | null {
    let cur = this.#head
    for (let i = 0; i < index && cur; i++) cur = cur.next
    return cur
  }
}

const list = new LinkedList<number>()
list.append(1); list.append(2); list.append(4)
list.insertAt(2, 3)
list.toArray() // [1, 2, 3, 4]
list.indexOf(3) // 2

双向链表

class DoublyNode<T> {
  prev: DoublyNode<T> | null = null
  next: DoublyNode<T> | null = null
  constructor(public value: T) {}
}

class DoublyLinkedList<T> {
  #head: DoublyNode<T> | null = null
  #tail: DoublyNode<T> | null = null
  #size = 0

  append(value: T): void {
    const node = new DoublyNode(value)
    if (!this.#head) this.#head = this.#tail = node
    else {
      node.prev = this.#tail
      this.#tail!.next = node
      this.#tail = node
    }
    this.#size++
  }

  prepend(value: T): void {
    const node = new DoublyNode(value)
    if (!this.#head) this.#head = this.#tail = node
    else {
      node.next = this.#head
      this.#head.prev = node
      this.#head = node
    }
    this.#size++
  }

  removeAt(index: number): T | undefined {
    if (index < 0 || index >= this.#size) throw new Error('out of range')
    let target: DoublyNode<T>
    // 优化：靠近尾部就从尾遍历
    if (index < this.#size / 2) {
      target = this.#head!
      for (let i = 0; i < index; i++) target = target.next!
    } else {
      target = this.#tail!
      for (let i = this.#size - 1; i > index; i--) target = target.prev!
    }
    if (target.prev) target.prev.next = target.next
    else this.#head = target.next
    if (target.next) target.next.prev = target.prev
    else this.#tail = target.prev
    this.#size--
    return target.value
  }

  get size(): number { return this.#size }
}

循环链表 / 环形链表检测

把尾节点的 next 指回头节点就是循环链表（双向再把 head.prev 指回 tail）。日常面试常考的是"判断链表是否有环"，Floyd 快慢指针即可。

class ListNode<T> {
  next: ListNode<T> | null = null
  constructor(public value: T) {}
}

// 是否存在环
function hasCycle<T>(head: ListNode<T> | null): boolean {
  let slow = head, fast = head
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}

// 找环的入口节点（无环则返回 null）
function detectCycle<T>(head: ListNode<T> | null): ListNode<T> | null {
  let slow = head, fast = head
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) {
      let p = head
      while (p !== slow) { p = p!.next; slow = slow!.next }
      return p
    }
  }
  return null
}

树

二叉树

每个节点最多两个子节点（left / right）。三种深度遍历：前序（根-左-右）、中序（左-根-右）、后序（左-右-根）。

class TreeNode<T> {
  constructor(
    public value: T,
    public left: TreeNode<T> | null = null,
    public right: TreeNode<T> | null = null,
  ) {}
}

function preOrder<T>(node: TreeNode<T> | null, out: T[] = []): T[] {
  if (!node) return out
  out.push(node.value)
  preOrder(node.left, out)
  preOrder(node.right, out)
  return out
}

function inOrder<T>(node: TreeNode<T> | null, out: T[] = []): T[] {
  if (!node) return out
  inOrder(node.left, out)
  out.push(node.value)
  inOrder(node.right, out)
  return out
}

function postOrder<T>(node: TreeNode<T> | null, out: T[] = []): T[] {
  if (!node) return out
  postOrder(node.left, out)
  postOrder(node.right, out)
  out.push(node.value)
  return out
}

// 迭代版前序（用栈）
function preOrderIter<T>(root: TreeNode<T> | null): T[] {
  if (!root) return []
  const stack: TreeNode<T>[] = [root]
  const out: T[] = []
  while (stack.length) {
    const node = stack.pop()!
    out.push(node.value)
    if (node.right) stack.push(node.right)
    if (node.left)  stack.push(node.left)
  }
  return out
}

// 层序遍历（BFS）
function levelOrder<T>(root: TreeNode<T> | null): T[] {
  if (!root) return []
  const queue: TreeNode<T>[] = [root]
  const out: T[] = []
  while (queue.length) {
    const node = queue.shift()!
    out.push(node.value)
    if (node.left)  queue.push(node.left)
    if (node.right) queue.push(node.right)
  }
  return out
}

//        1
//       / \
//      2   3
//     / \
//    4   5
const root = new TreeNode(
  1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3),
)

preOrder(root)   // [1, 2, 4, 5, 3]
inOrder(root)    // [4, 2, 5, 1, 3]
postOrder(root)  // [4, 5, 2, 3, 1]
levelOrder(root) // [1, 2, 3, 4, 5]

二叉搜索树 (BST)

左子树所有节点 < 根 < 右子树所有节点。平均 O(log n)，最坏退化到 O(n)（链状）。

class BSTNode {
  left: BSTNode | null = null
  right: BSTNode | null = null
  constructor(public key: number) {}
}

class BST {
  #root: BSTNode | null = null

  insert(key: number): void {
    const node = new BSTNode(key)
    if (!this.#root) { this.#root = node; return }
    let cur = this.#root
    while (true) {
      if (key < cur.key) {
        if (!cur.left)  { cur.left = node;  return }
        cur = cur.left
      } else if (key > cur.key) {
        if (!cur.right) { cur.right = node; return }
        cur = cur.right
      } else {
        return // 不允许重复
      }
    }
  }

  search(key: number): boolean {
    let cur = this.#root
    while (cur) {
      if (key === cur.key) return true
      cur = key < cur.key ? cur.left : cur.right
    }
    return false
  }

  min(): number | undefined {
    let cur = this.#root
    while (cur?.left) cur = cur.left
    return cur?.key
  }

  max(): number | undefined {
    let cur = this.#root
    while (cur?.right) cur = cur.right
    return cur?.key
  }

  inOrder(): number[] {
    const out: number[] = []
    const walk = (node: BSTNode | null): void => {
      if (!node) return
      walk(node.left)
      out.push(node.key)
      walk(node.right)
    }
    walk(this.#root)
    return out
  }
}

const bst = new BST()
;[11, 7, 15, 5, 3, 9, 8, 10, 13, 20, 6].forEach((k) => bst.insert(k))

bst.inOrder()  // [3, 5, 6, 7, 8, 9, 10, 11, 13, 15, 20]
bst.min()      // 3
bst.max()      // 20
bst.search(9)  // true
bst.search(99) // false

AVL 树

自平衡 BST：任一节点左右子树高度差 ≤ 1，保证插入 / 查找始终 O(log n)。插入后通过 4 种旋转（LL / RR / LR / RL）回到平衡。

class AVLNode {
  left: AVLNode | null = null
  right: AVLNode | null = null
  height = 1
  constructor(public key: number) {}
}

const height = (node: AVLNode | null): number => node?.height ?? 0
const balanceFactor = (node: AVLNode): number =>
  height(node.left) - height(node.right)
const updateHeight = (node: AVLNode): void => {
  node.height = 1 + Math.max(height(node.left), height(node.right))
}

function rotateRight(y: AVLNode): AVLNode {
  const x = y.left!
  const T = x.right
  x.right = y
  y.left = T
  updateHeight(y)
  updateHeight(x)
  return x
}

function rotateLeft(x: AVLNode): AVLNode {
  const y = x.right!
  const T = y.left
  y.left = x
  x.right = T
  updateHeight(x)
  updateHeight(y)
  return y
}

function avlInsert(node: AVLNode | null, key: number): AVLNode {
  if (!node) return new AVLNode(key)
  if (key < node.key)      node.left  = avlInsert(node.left, key)
  else if (key > node.key) node.right = avlInsert(node.right, key)
  else return node

  updateHeight(node)
  const bf = balanceFactor(node)

  if (bf > 1 && key < node.left!.key)   return rotateRight(node)              // LL
  if (bf < -1 && key > node.right!.key) return rotateLeft(node)               // RR
  if (bf > 1 && key > node.left!.key) {                                       // LR
    node.left = rotateLeft(node.left!)
    return rotateRight(node)
  }
  if (bf < -1 && key < node.right!.key) {                                     // RL
    node.right = rotateRight(node.right!)
    return rotateLeft(node)
  }
  return node
}

let root: AVLNode | null = null
;[10, 20, 30, 40, 50, 25].forEach((k) => { root = avlInsert(root, k) })
// 顺序插入若不平衡会退化成链；AVL 旋转后 root 为 30
root!.key // 30

Trie (前缀树)

把一组字符串按字符共享前缀压成树，单次查询 / 前缀匹配都是 O(L)（L 为字符串长度）。常见于自动补全、拼写检查。

class TrieNode {
  children = new Map<string, TrieNode>()
  end = false
}

class Trie {
  #root = new TrieNode()

  insert(word: string): void {
    let node = this.#root
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode())
      node = node.children.get(ch)!
    }
    node.end = true
  }

  search(word: string): boolean {
    const node = this.#walk(word)
    return !!node?.end
  }

  startsWith(prefix: string): boolean {
    return this.#walk(prefix) !== null
  }

  #walk(s: string): TrieNode | null {
    let node = this.#root
    for (const ch of s) {
      const next = node.children.get(ch)
      if (!next) return null
      node = next
    }
    return node
  }
}

const trie = new Trie()
;['apple', 'app', 'apricot'].forEach((w) => trie.insert(w))

trie.search('app')     // true
trie.search('apr')     // false  ← 'apr' 不是完整单词
trie.startsWith('apr') // true   ← 但有 'apricot' 以它开头

并查集 (Union-Find)

维护一组互不相交集合，支持快速判断两个元素是否同集 + 合并集合。常见于连通性、Kruskal 最小生成树。find 路径压缩 + union 按秩合并后近似 O(α(n))。

class UnionFind {
  parent: number[]
  rank: number[]

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i)
    this.rank = new Array(n).fill(0)
  }

  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]] // 路径压缩（一次跳两级）
      x = this.parent[x]
    }
    return x
  }

  union(a: number, b: number): boolean {
    const ra = this.find(a)
    const rb = this.find(b)
    if (ra === rb) return false
    if (this.rank[ra] < this.rank[rb])      this.parent[ra] = rb
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra
    else { this.parent[rb] = ra; this.rank[ra]++ }
    return true
  }

  connected(a: number, b: number): boolean { return this.find(a) === this.find(b) }
}

const uf = new UnionFind(5)
uf.union(0, 1); uf.union(1, 2)
uf.connected(0, 2) // true
uf.connected(0, 3) // false

堆 (Heap)

一棵完全二叉树，父节点始终 ≤（小顶堆）或 ≥（大顶堆）其子节点。常用于优先队列、Top-K、Dijkstra。下面是最小堆。

class MinHeap {
  #data: number[] = []

  push(value: number): void {
    this.#data.push(value)
    this.#siftUp(this.#data.length - 1)
  }

  pop(): number | undefined {
    if (!this.#data.length) return undefined
    const top = this.#data[0]
    const last = this.#data.pop()!
    if (this.#data.length) {
      this.#data[0] = last
      this.#siftDown(0)
    }
    return top
  }

  peek(): number | undefined { return this.#data[0] }
  get size(): number { return this.#data.length }

  #siftUp(i: number): void {
    while (i > 0) {
      const p = (i - 1) >> 1
      if (this.#data[p] <= this.#data[i]) break
      ;[this.#data[p], this.#data[i]] = [this.#data[i], this.#data[p]]
      i = p
    }
  }

  #siftDown(i: number): void {
    const n = this.#data.length
    while (true) {
      const l = i * 2 + 1, r = i * 2 + 2
      let s = i
      if (l < n && this.#data[l] < this.#data[s]) s = l
      if (r < n && this.#data[r] < this.#data[s]) s = r
      if (s === i) break
      ;[this.#data[s], this.#data[i]] = [this.#data[i], this.#data[s]]
      i = s
    }
  }
}

const heap = new MinHeap()
;[5, 2, 8, 1, 9, 3].forEach((v) => heap.push(v))

heap.pop() // 1
heap.pop() // 2
heap.pop() // 3

字典

键-值存储。现代 JS / TS 直接用 Map 即可（支持任意键类型、保留插入顺序、有 size）。下面是对 Map 的一个轻包装示例。

class Dictionary<K, V> {
  #items = new Map<K, V>()

  set(key: K, value: V): this { this.#items.set(key, value); return this }
  get(key: K): V | undefined  { return this.#items.get(key) }
  has(key: K): boolean        { return this.#items.has(key) }
  remove(key: K): boolean     { return this.#items.delete(key) }
  get keys(): K[]             { return [...this.#items.keys()] }
  get values(): V[]           { return [...this.#items.values()] }
  get size(): number          { return this.#items.size }
}

const dict = new Dictionary<string, string>()
dict.set('zhangsan', 'zhangsan@e.com').set('lisi', 'lisi@e.com')
dict.get('zhangsan') // 'zhangsan@e.com'
dict.keys            // ['zhangsan', 'lisi']

哈希表

通过哈希函数把键映射到数组下标，平均 O(1) 查找。冲突常见解法：拉链法（数组里挂列表）和开放寻址。

哈希函数

把字符串编码成大整数，再取余压到表长以内。这里用霍纳法则 + 质数乘数减小冲突。

function hashCode(str: string, size = 7): number {
  const PRIME = 37
  let code = 0
  for (let i = 0; i < str.length; i++) {
    code = PRIME * code + str.charCodeAt(i)
  }
  return code % size
}

hashCode('aa') // 1
hashCode('AA') // 6
hashCode('bb') // 2

拉链法实现

class HashTable<V> {
  #storage: Array<Array<[string, V]> | undefined> = []
  #limit = 7
  #count = 0

  #hash(key: string): number { return hashCode(key, this.#limit) }

  put(key: string, value: V): void {
    const idx = this.#hash(key)
    const bucket = (this.#storage[idx] ??= [])
    for (const tuple of bucket) {
      if (tuple[0] === key) { tuple[1] = value; return }
    }
    bucket.push([key, value])
    this.#count++
  }

  get(key: string): V | undefined {
    const bucket = this.#storage[this.#hash(key)]
    if (!bucket) return undefined
    for (const [k, v] of bucket) {
      if (k === key) return v
    }
    return undefined
  }

  remove(key: string): V | undefined {
    const bucket = this.#storage[this.#hash(key)]
    if (!bucket) return undefined
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        const [, v] = bucket.splice(i, 1)[0]
        this.#count--
        return v
      }
    }
    return undefined
  }

  get size(): number { return this.#count }
}

const h = new HashTable<string>()
h.put('zhangsan', '张三')
h.put('lisi', '李四')
h.get('zhangsan') // '张三'
h.remove('lisi')
h.get('lisi')     // undefined

排序

排序算法	平均时间	最好情况	最坏情况	空间	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
希尔排序	O(n log² n)	O(n log n)	O(n²)	O(1)	不稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	稳定
桶排序	O(n + k)	O(n + k)	O(n²)	O(n + k)	稳定
基数排序	O(n × k)	O(n × k)	O(n × k)	O(n + k)	稳定

冒泡排序

相邻元素两两比较交换，每轮把当前最大值"冒泡"到末尾。带 swapped 标志可在有序时提前结束。

function bubbleSort(arr: number[]): number[] {
  const a = [...arr]
  for (let i = 0; i < a.length - 1; i++) {
    let swapped = false
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        ;[a[j], a[j + 1]] = [a[j + 1], a[j]]
        swapped = true
      }
    }
    if (!swapped) break
  }
  return a
}

bubbleSort([6, 3, 8, 2, 9, 1]) // [1, 2, 3, 6, 8, 9]

插入排序

把每个新元素插入到前面已排好序列的合适位置。对接近有序的数据非常快。

function insertionSort(arr: number[]): number[] {
  const a = [...arr]
  for (let i = 1; i < a.length; i++) {
    const cur = a[i]
    let j = i - 1
    while (j >= 0 && a[j] > cur) {
      a[j + 1] = a[j]
      j--
    }
    a[j + 1] = cur
  }
  return a
}

insertionSort([6, 3, 8, 2, 9, 1]) // [1, 2, 3, 6, 8, 9]

选择排序

每轮从未排序部分选出最小值，放到已排序部分的末尾。

function selectionSort(arr: number[]): number[] {
  const a = [...arr]
  for (let i = 0; i < a.length - 1; i++) {
    let minIdx = i
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[minIdx]) minIdx = j
    }
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]]
  }
  return a
}

selectionSort([6, 3, 8, 2, 9, 1]) // [1, 2, 3, 6, 8, 9]

希尔排序

按递减的间隔 gap 做插入排序，可看作插入排序的加速版。

function shellSort(arr: number[]): number[] {
  const a = [...arr]
  for (let gap = a.length >> 1; gap > 0; gap >>= 1) {
    for (let i = gap; i < a.length; i++) {
      const cur = a[i]
      let j = i - gap
      while (j >= 0 && a[j] > cur) {
        a[j + gap] = a[j]
        j -= gap
      }
      a[j + gap] = cur
    }
  }
  return a
}

shellSort([6, 3, 8, 2, 9, 1]) // [1, 2, 3, 6, 8, 9]

快速排序

选基准值，小的左、大的右，递归。平均 O(n log n)，最坏 O(n²)（数据已有序 + 取首尾为基准）。

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr
  const pivot = arr[arr.length >> 1]
  const left: number[] = []
  const right: number[] = []
  const mid: number[] = []
  for (const x of arr) {
    if (x < pivot)      left.push(x)
    else if (x > pivot) right.push(x)
    else                mid.push(x)
  }
  return [...quickSort(left), ...mid, ...quickSort(right)]
}

quickSort([6, 3, 8, 2, 9, 1]) // [1, 2, 3, 6, 8, 9]

归并排序

分治：把数组对半分到只剩 1 个，再两两有序合并。稳定，时间稳定 O(n log n)，需要额外 O(n) 空间。

function mergeSort(arr: number[]): number[] {
  if (arr.length < 2) return arr
  const mid = arr.length >> 1
  const left  = mergeSort(arr.slice(0, mid))
  const right = mergeSort(arr.slice(mid))

  const out: number[] = []
  let i = 0, j = 0
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++])
    else                     out.push(right[j++])
  }
  return out.concat(left.slice(i), right.slice(j))
}

mergeSort([6, 3, 8, 2, 9, 1]) // [1, 2, 3, 6, 8, 9]

堆排序

把数组建成最大堆，每次把堆顶和末尾交换，再对剩余部分下沉调整。原地 O(1) 空间。

function heapSort(arr: number[]): number[] {
  const a = [...arr]
  const n = a.length

  const siftDown = (i: number, end: number): void => {
    while (true) {
      const l = i * 2 + 1, r = i * 2 + 2
      let largest = i
      if (l < end && a[l] > a[largest]) largest = l
      if (r < end && a[r] > a[largest]) largest = r
      if (largest === i) break
      ;[a[i], a[largest]] = [a[largest], a[i]]
      i = largest
    }
  }

  // 建堆
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(i, n)
  // 逐个取堆顶到末尾
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]]
    siftDown(0, end)
  }
  return a
}

heapSort([6, 3, 8, 2, 9, 1]) // [1, 2, 3, 6, 8, 9]

计数排序

用计数数组统计每个值出现次数再展开。适合值域 k 不大的场景，O(n + k)。

function countingSort(arr: number[]): number[] {
  if (arr.length === 0) return []
  const min = Math.min(...arr)
  const max = Math.max(...arr)
  const counts = new Array(max - min + 1).fill(0)
  for (const v of arr) counts[v - min]++

  const out: number[] = []
  for (let i = 0; i < counts.length; i++) {
    for (let c = 0; c < counts[i]; c++) out.push(i + min)
  }
  return out
}

countingSort([6, 3, 8, 2, 9, 1]) // [1, 2, 3, 6, 8, 9]

桶排序

把数据按值域分到若干桶，桶内单独排序后再依次拼起来。桶分布均匀时接近 O(n)。

function bucketSort(arr: number[], bucketCount = 5): number[] {
  if (arr.length === 0) return []
  const min = Math.min(...arr)
  const max = Math.max(...arr)
  const bucketSize = Math.ceil((max - min + 1) / bucketCount)
  const buckets: number[][] = Array.from({ length: bucketCount }, () => [])

  for (const v of arr) {
    const idx = Math.floor((v - min) / bucketSize)
    buckets[idx].push(v)
  }

  return buckets.flatMap((b) => b.sort((x, y) => x - y))
}

bucketSort([6, 3, 8, 2, 9, 1]) // [1, 2, 3, 6, 8, 9]

基数排序

按位排序，从最低位到最高位逐位用稳定排序（这里用 10 个桶）。只适合非负整数 / 定长字符串。

function radixSort(arr: number[]): number[] {
  if (arr.length === 0) return []
  const max = Math.max(...arr)
  const maxDigits = String(max).length
  let a = [...arr]

  for (let d = 0; d < maxDigits; d++) {
    const buckets: number[][] = Array.from({ length: 10 }, () => [])
    for (const v of a) {
      const digit = Math.floor(v / 10 ** d) % 10
      buckets[digit].push(v)
    }
    a = buckets.flat()
  }
  return a
}

radixSort([170, 45, 75, 90, 802, 24, 2, 66]) // [2, 24, 45, 66, 75, 90, 170, 802]