数组随机排序

问题

快速让一个数组乱序，实现随机排序。

解答

方法一：sort + Math.random()

// 简单但分布不均匀
function shuffle(arr) {
  return arr.sort(() => Math.random() - 0.5);
}

const arr = [1, 2, 3, 4, 5];
console.log(shuffle(arr)); // 随机顺序

这种方法简单，但随机性不够好。因为 sort 的排序算法不同，导致元素被交换的概率不均等。

方法二：Fisher-Yates 洗牌算法（推荐）

// 真正的随机，每个元素出现在每个位置的概率相等
function shuffle(arr) {
  const result = [...arr]; // 不修改原数组
  
  // 从后往前遍历
  for (let i = result.length - 1; i > 0; i--) {
    // 生成 0 到 i 之间的随机索引
    const j = Math.floor(Math.random() * (i + 1));
    // 交换元素
    [result[i], result[j]] = [result[j], result[i]];
  }
  
  return result;
}

const arr = [1, 2, 3, 4, 5];
console.log(shuffle(arr)); // 真正随机的顺序

方法三：Fisher-Yates 原地版本

// 直接修改原数组
function shuffleInPlace(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

验证随机性

// 统计每个位置出现各数字的次数
function testShuffle(shuffleFn, times = 100000) {
  const arr = [1, 2, 3, 4, 5];
  const count = {};
  
  for (let i = 0; i < times; i++) {
    const result = shuffleFn([...arr]);
    result.forEach((num, index) => {
      const key = `位置${index}-数字${num}`;
      count[key] = (count[key] || 0) + 1;
    });
  }
  
  // 理想情况：每个数字在每个位置出现 times/5 次
  console.log(count);
}

testShuffle(shuffle);

关键点

• sort 方法不可靠：不同浏览器的排序算法不同，导致随机分布不均匀
• Fisher-Yates 时间复杂度 O(n)：只需遍历一次数组
• 从后往前遍历：确保每个元素都有均等概率出现在任意位置
• 随机范围是 [0, i]：包含当前位置，元素可能保持原位
• 使用解构赋值交换：[a, b] = [b, a] 简洁高效