TypeScript 算法实战全景

TypeScript 的算法实现充分利用了高阶函数（Higher-Order Functions）、比较器函数（Comparators）与类型推导：

• 强类型算法签名：通过比较器 compare: (a: T, b: T) => number 实现真正的通用泛型算法。
• 不可变状态转换：借助 filter、map、展开运算符 ... 编写纯函数风格的算法流程。

---

📊 核心算法与复杂度

算法专题	典型问题 / 算法	核心思想	时间复杂度	空间复杂度
排序	Generic QuickSort / Array.prototype.sort	泛型比较器、递归分治 / V8 TimSort	$O(n \log n)$	$O(n)$
查找	Array.prototype.indexOf / find	谓词匹配查找	$O(n)$	$O(1)$
图/树遍历	DFS / BFS	递归 / 数组队列操作	$O(V + E)$	$O(V)$

---

1. 泛型排序算法：快速排序 (QuickSort)

利用泛型类型 <T> 与自定义比较器实现不可变风格快速排序：

export function quickSort<T>(arr: T[], compare: (a: T, b: T) => number = (a, b) => (a < b ? -1 : a > b ? 1 : 0)): T[] {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter((x) => compare(x, pivot) < 0);
  const middle = arr.filter((x) => compare(x, pivot) === 0);
  const right = arr.filter((x) => compare(x, pivot) > 0);
  return [...quickSort(left, compare), ...middle, ...quickSort(right, compare)];
}

function main() {
  console.log("=== TypeScript Generic QuickSort ===");
  const numbers = [64, 25, 12, 22, 11];
  const sorted = quickSort(numbers);

  if (JSON.stringify(sorted) !== JSON.stringify([11, 12, 22, 25, 64])) {
    throw new Error("Sort failed");
  }

  console.log("Sorted result:", sorted);
  console.log("TypeScript QuickSort tests passed successfully.");
}

main();

🐳 Docker Verified📋node:20-alpine

Exit Code: 0

=== TypeScript Generic QuickSort ===
Sorted result: [ 11, 12, 22, 25, 64 ]
TypeScript QuickSort tests passed successfully.