题库/手写题/题目详解
专题深化约 3 分钟阅读

手写 Fisher–Yates 洗牌，为什么 sort(() => Math.random()-0.5) 不可靠？

先理解原理和示例，再练习完整口述与追问。

回答要点

剩余区间均匀选择；每步缩小区间；O(n)；随机源假设；原数组不变；统计检验不同于证明。

原理拆解

从末尾向前，为当前 i 在 0～i 中均匀选择 j 并交换，再固定 i。若每步随机选择独立且均匀，每一种排列的概率为 1/n!。随机比较器不满足排序要求的一致比较关系，结果依赖排序算法与调用次数，不构成均匀洗牌。

示例与推演

js
function shuffle(input, random = Math.random) {
  if (!Array.isArray(input) || typeof random !== 'function') throw new TypeError('参数不合法')
  const result = input.slice()
  for (let i = result.length - 1; i > 0; i--) {
    const value = random()
    if (!Number.isFinite(value) || value < 0 || value >= 1) throw new RangeError('随机值必须在 [0,1)')
    const j = Math.floor(value * (i + 1))
    ;[result[i], result[j]] = [result[j], result[i]]
  }
  return result
}

三项在第一步有 3 种选择，第二步有 2 种，共 6 条等概率路径。这里复制输入，时间 O(n)、额外空间 O(n)；若允许原地修改，可去掉副本但应改变函数契约。

易错点

Math.random 不是安全抽奖或密码用途随机源。传入可控 random 便于确定性测试，测试仍应检查元素多重集合不变、输入不变与边界。

参考回答可直接练习口述

我用 Fisher–Yates，每轮只从尚未固定区间均匀选位置，线性完成。均匀性依赖随机源，不能用随机 sort 替代；是否原地和是否安全随机都明确说明。